Merge Sorted Array

At first glance, this problem looks like a standard merge operation from Merge Sort.

Most candidates immediately think about creating a temporary array and merging both sorted arrays into it.

While that solution works, interviewers are actually testing whether you can identify and utilize the extra space already available inside the first array.

Let's understand why.

Problem Statement

You are given two sorted arrays:

nums1 = [1,2,3,0,0,0]
m = 3

nums2 = [2,5,6]
n = 3

The first m elements of nums1 are valid.

The last n positions are empty and represented by 0.

Merge nums2 into nums1 such that the final array remains sorted.

Expected Output:

[1,2,2,3,5,6]

The catch is:

You must modify nums1 in-place.

Brute Force Approach

Interview Explanation

My first instinct would be to use the merge step from Merge Sort.

Since both arrays are already sorted, I can maintain two pointers, compare elements, and store the smaller element inside a temporary array.

Once one array is exhausted, I append the remaining elements from the other array.

Finally, I copy the merged result back into nums1.

Time Complexity

O(m + n)

Space Complexity

O(m + n)

Brute Force Java Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int[] temp = new int[m + n];

        int i = 0;
        int j = 0;
        int k = 0;

        while (i < m && j < n) {

            if (nums1[i] <= nums2[j]) {
                temp[k++] = nums1[i++];
            } else {
                temp[k++] = nums2[j++];
            }
        }

        while (i < m) {
            temp[k++] = nums1[i++];
        }

        while (j < n) {
            temp[k++] = nums2[j++];
        }

        for (int idx = 0; idx < m + n; idx++) {
            nums1[idx] = temp[idx];
        }
    }
}

Key Observation

Notice something important:

nums1 = [1,2,3,0,0,0]

The last three positions are already empty.

The interviewer intentionally gives us extra space.

So instead of creating another array, we should utilize the free space that already exists.

Why Merging From The Front Fails

Suppose we start filling values from index 0.

[1,2,3,0,0,0]
 ^

We may overwrite values that we haven't processed yet.

That's dangerous.

The Core Insight

The empty positions are located at the end.

Therefore:

Instead of placing the smallest elements at the beginning, place the largest elements at the end.

Since the last positions are unused, no important data gets overwritten.

This is the entire trick behind the optimal solution.

Optimal Approach

Maintain three pointers:

i = m - 1
j = n - 1
k = m + n - 1

Where:

• i points to the last valid element of nums1
• j points to the last element of nums2
• k points to the last position of nums1

Compare the larger element and place it at position k.

Move pointers accordingly.

Dry Run

Input

nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]

Pointers:

i = 2 (3)
j = 2 (6)
k = 5

Step 1

Compare:

3 vs 6

Place 6.

[1,2,3,0,0,6]

Step 2

Compare:

3 vs 5

Place 5.

[1,2,3,0,5,6]

Step 3

Compare:

3 vs 2

Place 3.

[1,2,3,3,5,6]

Step 4

Compare:

2 vs 2

Place either.

[1,2,2,3,5,6]

Final Output

[1,2,2,3,5,6]

Optimal Java Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int i = m - 1;
        int j = n - 1;
        int 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--;
        }
    }
}

Complexity Analysis

What Interviewers Want To Hear

A strong interview explanation would be:

Since nums1 already contains extra space at the end, I can avoid using an auxiliary array. By starting from the back and placing the larger element first, I prevent overwriting unprocessed values and achieve an in-place O(1) space solution.

Key Takeaway

Whenever you see:

• Two sorted arrays
• Extra space at the end of one array
• In-place merge requirement

Think:

Merge from the back using three pointers.

This small observation converts a standard merge solution into the optimal interview solution.

Striver SDE Sheet Challenge 🚀

Consistent effort compounds. One problem at a time.

GitHub: https://github.com/codewithjaspreet

LinkedIn: https://linkedin.com/in/jaspreetsinghsodhi

Medium: https://medium.com/@jaspreet.dev