Merge Sorted Array

                                            
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};

                                            
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
    }
}

                                            
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None
        """
        p1 = m - 1
        p2 = n - 1
        p = m + n - 1
        
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1
        
        if p2 >= 0:
            nums1[:p2+1] = nums2[:p2+1]

                                            
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // Start merging from the end of the arrays
    int index1 = m - 1;
    int index2 = n - 1;
    int index_merged = m + n - 1;
    
    while (index1 >= 0 && index2 >= 0) {
        if (nums1[index1] > nums2[index2]) {
            nums1[index_merged] = nums1[index1];
            index1--;
        } else {
            nums1[index_merged] = nums2[index2];
            index2--;
        }
        index_merged--;
    }
    
    while (index2 >= 0) {
        nums1[index_merged] = nums2[index2];
        index2--;
        index_merged--;
    }
}

                                            
public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        int pointer1 = m - 1;
        int pointer2 = n - 1;
        int index = m + n - 1;

        while (pointer1 >= 0 && pointer2 >= 0) {
            if (nums1[pointer1] > nums2[pointer2]) {
                nums1[index] = nums1[pointer1];
                pointer1--;
            } else {
                nums1[index] = nums2[pointer2];
                pointer2--;
            }
            index--;
        }

        while (pointer2 >= 0) {
            nums1[index] = nums2[pointer2];
            pointer2--;
            index--;
        }
    }
}

                                            
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 */
const merge = (nums1, m, nums2) => {
    let p1 = m - 1;
    let p2 = nums2.length - 1;
    let p = nums1.length - 1;

    while (p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
};

                                            
/**
 Do not return anything, modify nums1 in-place 
instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;

    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }

    while (j >= 0) {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
}

                                            
class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer $m
     * @param Integer[] $nums2
     * @param Integer $n
     * @return NULL
     */
    function merge(&$nums1, $m, $nums2, $n) {
        $p1 = $m - 1;
        $p2 = $n - 1;
        $p = $m + $n - 1;
        
        while ($p1 >= 0 && $p2 >= 0) {
            if ($nums1[$p1] > $nums2[$p2]) {
                $nums1[$p] = $nums1[$p1];
                $p1--;
            } else {
                $nums1[$p] = $nums2[$p2];
                $p2--;
            }
            $p--;
        }
        
        while ($p2 >= 0) {
            $nums1[$p] = $nums2[$p2];
            $p2--;
            $p--;
        }
    }
}

                                            
class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var index1 = m - 1
        var index2 = n - 1
        var currentIndex = m + n - 1
        
        while index1 >= 0 && index2 >= 0 {
            if nums1[index1] > nums2[index2] {
                nums1[currentIndex] = nums1[index1]
                index1 -= 1
            } else {
                nums1[currentIndex] = nums2[index2]
                index2 -= 1
            }
            currentIndex -= 1
        }
        
        while index2 >= 0 {
            nums1[currentIndex] = nums2[index2]
            index2 -= 1
            currentIndex -= 1
        }
    }
}

                                            
class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        var i = m - 1
        var j = n - 1
        var k = m + n - 1
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i]
                i--
            } else {
                nums1[k] = nums2[j]
                j--
            }
            k--
        }
        
        while (j >= 0) {
            nums1[k] = nums2[j]
            j--
            k--
        }
    }
}

                                            
class Solution {
  void merge(List<int> nums1, int m, List<int> nums2, int n) {
    int index1 = m - 1;
    int index2 = n - 1;
    int currentIndex = m + n - 1;

    while (index1 >= 0 && index2 >= 0) {
      if (nums1[index1] > nums2[index2]) {
        nums1[currentIndex] = nums1[index1];
        index1--;
      } else {
        nums1[currentIndex] = nums2[index2];
        index2--;
      }
      currentIndex--;
    }

    while (index2 >= 0) {
      nums1[currentIndex] = nums2[index2];
      index2--;
      currentIndex--;
    }
  }
}

                                            
# @param {Integer[]} nums1
# @param {Integer} m
# @param {Integer[]} nums2
# @param {Integer} n
def merge(nums1, m, nums2, n)
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    while p1 >= 0 && p2 >= 0
        if nums1[p1] > nums2[p2]
            nums1[p] = nums1[p1]
            p1 -= 1
        else
            nums1[p] = nums2[p2]
            p2 -= 1
        end
        p -= 1
    end

    nums1[0...p2+1] = nums2[0..p2] if p2 >= 0
end

                                            
object Solution {
    def merge(nums1: Array[Int], m: Int, nums2: Array[Int], n: Int): Unit = {
        var i = m - 1
        var j = n - 1
        var k = m + n - 1

        while (i >= 0 && j >= 0) {
            if (nums1(i) > nums2(j)) {
                nums1(k) = nums1(i)
                i -= 1
            } else {
                nums1(k) = nums2(j)
                j -= 1
            }
            k -= 1
        }

        while (j >= 0) {
            nums1(k) = nums2(j)
            j -= 1
            k -= 1
        }
    }
}

                                            
impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let (mut m, mut n) = (m as usize, n as usize);
        let (mut p1, mut p2) = (m as i32 - 1, n as i32 - 1);
        
        for i in ((0..(m + n) as usize).rev()) {
            if p2 < 0 {
                break;
            }
            
            if p1 >= 0 && nums1[p1 as usize] > nums2[p2 as usize] {
                nums1[i] = nums1[p1 as usize];
                p1 -= 1;
            } else {
                nums1[i] = nums2[p2 as usize];
                p2 -= 1;
            }
        }
    }
}

To solve this coding challenge, we need to merge two sorted arrays,

nums1

and

nums2

, into one sorted array in-place within

nums1

. The array

nums1

has enough space to accommodate all elements from both arrays, with unused slots filled with zeros. Here's an approach and methodology to achieve this in an efficient manner.

Explanation

The challenge requires us to merge two sorted arrays in a way that the result is stored inside the first array (

nums1

). The final merged array should be sorted in non-decreasing order. Key points include:

nums1

has additional space (filled with zeros) to accommodate all elements from both arrays.
We need to consider the valid elements both in
nums1

and
nums2

.
We will do this in-place and aim for O(m + n) time complexity, which is efficient for merging sorted arrays.

Approach

Three Pointers Technique : We'll use three pointers:

p1

to track the end of the valid elements in
nums1

.
p2

to track the end of
nums2

.
p

to track the position in
nums1

where the next largest element should be placed.

Comparing from the End : Starting from the end of both arrays, compare elements from
nums1

and
nums2

:

If the element in
nums1

is greater, place it at the current position indicated by
p

and move
p1

one step back.
Otherwise, place the element from
nums2

at the current position and move
p2

one step back.
Always move the pointer
p

back after placing an element.

Remaining Elements : If any elements are left in
nums2

after we have exhausted all elements in
nums1

, copy them over to
nums1

.

This approach ensures we always place the largest remaining element at the end of the combined space, ensuring sorted order.

Detailed Steps in Pseudocode

Initialize three pointers:
p1 = m - 1

,
p2 = n - 1

, and
p = m + n - 1

.
While both
p1

and
p2

are valid (i.e., not below zero):

Compare
nums1[p1]

and
nums2[p2]

.
Place the larger element at
nums1[p]

.
Move the respective pointer (
p1

or
p2

) back.
Move pointer
p

back by one.

If any elements remain in
nums2

after
p1

is exhausted, copy them to the beginning of
nums1

.

Pseudocode with Comments

                                            
# Initialize pointers to the end of the respective regions in nums1 and nums2
p1 = m - 1   # Pointer to end of valid elements in nums1
p2 = n - 1   # Pointer to end of nums2
p = m + n - 1  # Pointer to the end of merged array in nums1

# Merge the arrays starting from the end
while p1 >= 0 and p2 >= 0:
    if nums1[p1] > nums2[p2]:
        nums1[p] = nums1[p1]  # Place the larger element at the end position
        p1 -= 1  # Move pointer p1 back
    else:
        nums1[p] = nums2[p2]  # Place the larger element at the end position
        p2 -= 1  # Move pointer p2 back
    p -= 1  # Move pointer p back

# If nums2 has remaining elements, copy them over to nums1
if p2 >= 0:
    nums1[0:p2+1] = nums2[0:p2+1]  # Copy remaining elements of nums2

Here, we ensure all elements are compared and placed in the correct position, starting from the greatest values, which helps achieve the merge efficiently without needing additional space. This method takes O(m + n) time, ensuring an efficient solution to the problem.