Merge Sorted Array

Merge Sorted Array

What is this problem about?

The "Merge Sorted Array" coding problem asks you to combine two sorted integer arrays, nums1 and nums2, into a single sorted array. The catch is that the merged result must be stored back into nums1, which is pre-allocated with enough space to accommodate all elements from both nums1 (initially m elements) and nums2 (initially n elements). The final m+n elements in nums1 should be sorted. You are typically given nums1, m (the number of initialized elements in nums1), nums2, and n (the number of elements in nums2). This Array interview question is a common introduction to Two Pointers and Sorting techniques, often appearing in interviews for a wide range of companies.

Why is this asked in interviews?

This "Merge Sorted Array" interview question is a staple at many tech companies, from Google and Microsoft to startups, primarily because it's deceptively simple yet effectively tests several fundamental skills:

1. Array Manipulation and In-place Modification: It assesses a candidate's ability to modify an array in-place, which is crucial for optimizing space complexity.
2. Two-Pointer Technique: The most efficient solution relies on the Two Pointers interview pattern, demonstrating an understanding of how to manage multiple indices effectively.
3. Edge Case Handling: Candidates must account for scenarios like empty arrays (m=0 or n=0), or one array being significantly larger than the other.
4. Logical Reasoning: It requires careful thought to avoid overwriting elements in nums1 prematurely before they have been processed. It's an excellent way to evaluate a candidate's attention to detail, efficiency, and foundational knowledge of array algorithms.

Algorithmic pattern used

The most efficient algorithmic pattern to solve the "Merge Sorted Array" coding problem is the Two Pointers technique, specifically starting from the end of the arrays and merging backward.

1. Initialize Pointers:
   • A pointer p1 for the last initialized element of nums1 (i.e., m-1).
   • A pointer p2 for the last element of nums2 (i.e., n-1).
   • A pointer write_idx for the position where the next largest element should be placed in nums1 (i.e., m+n-1).
2. Merge Backward: While p1 >= 0 and p2 >= 0:
   • Compare nums1[p1] and nums2[p2].
   • If nums1[p1] > nums2[p2], place nums1[p1] at nums1[write_idx], then decrement p1.
   • Else (if nums2[p2] >= nums1[p1]), place nums2[p2] at nums1[write_idx], then decrement p2.
   • In both cases, decrement write_idx.
3. Handle Remaining Elements: After the loop, one of the arrays might still have elements remaining.
   • If p2 >= 0, it means there are still elements in nums2 that haven't been placed (and they must be smaller than any elements already placed from nums1). Copy these remaining elements from nums2 into nums1 starting from write_idx down to 0. (No need to handle p1 >= 0 because if nums1 elements remain, they are already in their correct sorted position at the beginning of nums1 due to the backward merge.)

This backward merging strategy is crucial because it utilizes the empty space at the end of nums1 without overwriting elements that are yet to be processed.

Example explanation

Let nums1 = [1, 2, 3, 0, 0, 0], m = 3 and nums2 = [2, 5, 6], n = 3.

1. Initialize: p1 = m - 1 = 2 (points to 3 in nums1) p2 = n - 1 = 2 (points to 6 in nums2) write_idx = m + n - 1 = 5 (points to the last 0 in nums1)

2. Merge loop:

   • p1=2, p2=2: nums1[2]=3, nums2[2]=6. 6 > 3. nums1[5] = 6. nums1 becomes [1, 2, 3, 0, 0, 6]. p2-- (p2=1), write_idx-- (write_idx=4).
   • p1=2, p2=1: nums1[2]=3, nums2[1]=5. 5 > 3. nums1[4] = 5. nums1 becomes [1, 2, 3, 0, 5, 6]. p2-- (p2=0), write_idx-- (write_idx=3).
   • p1=2, p2=0: nums1[2]=3, nums2[0]=2. 3 > 2. nums1[3] = 3. nums1 becomes [1, 2, 3, 3, 5, 6]. p1-- (p1=1), write_idx-- (write_idx=2).
   • Now p2 < 0, so the loop terminates.

3. Handle remaining elements: p2 is -1, so no elements remain in nums2 to copy. (nums1 elements [1, 2] are already in place).

Final nums1: [1, 2, 3, 3, 5, 6].

Common mistakes candidates make

The most frequent mistake is attempting to merge from the beginning of nums1. If you start from the beginning, you will inevitably overwrite elements of nums1 that you still need to compare later, leading to incorrect results. Not handling the case where n > 0 and m = 0 (meaning nums1 is initially empty, and you just need to copy all of nums2 into nums1) can also be an oversight. Off-by-one errors with pointers, especially write_idx, are common, as is incorrectly assuming that nums1 will always have elements remaining to be processed.

Interview preparation tip

To master the "Merge Sorted Array" coding problem, practice the Two Pointers technique extensively. Understand why merging from the end is critical for in-place solutions. Work through examples by hand, carefully tracing the movement of p1, p2, and write_idx. Pay close attention to the conditions for the main loop and for handling any remaining elements. This Array, Sorting, Two Pointers problem is fundamental and ensures a strong grasp of basic array manipulation and optimization. It's a great stepping stone for more complex problems involving merging or array transformations.