DEV Community

Debesh P.
Debesh P.

Posted on • Edited on

88. Merge Sorted Array | LeetCode | Top Interview 150 | Coding Questions

#leetcode #programming #productivity #career

Problem Link

https://leetcode.com/problems/merge-sorted-array/

Detailed Step-by-Step Explanation

https://leetcode.com/problems/merge-sorted-array/solutions/7439477/most-optimal-solution-beats-1000-best-ti-x04k

leetcode 88

Problem in Simple Words

You are given two sorted arrays:

  • nums1 has size m + n

    • First m elements are valid
    • Last n elements are empty (filled with 0)

  • nums2 has size n and is fully valid

Your task:

  • Merge nums2 into nums1
  • Result must be sorted
  • You must modify nums1 in place
  • No extra array allowed

Important Detail People Miss

nums1 already has extra space at the end.

That space exists exactly so we can merge nums2 into it.

So the real challenge is:
“How do we merge without overwriting useful data in nums1?”

Key Insight (This Is the Trick)

If we start merging from the front, we’ll overwrite values in nums1 that we still need.

So instead:

  • We merge from the back
  • We place the largest elements first

This way, we only write into empty or already-used space.

Pointer Setup (Very Important) 

int i = m - 1;
int j = n - 1;
int k = m + n - 1;
Enter fullscreen mode Exit fullscreen mode

What each pointer means:

  • i → last valid element in nums1
  • j → last element in nums2
  • k → last position in nums1 (empty space)

All comparisons and placements happen from right to left.

Core Logic Explained Slowly

We loop while there are still elements left in nums2:

while (j >= 0) {
Enter fullscreen mode Exit fullscreen mode

Why only j?

  • If nums2 is fully placed, the job is done
  • Remaining elements in nums1 are already in correct position

Case 1: nums1 has elements and nums1[i] is bigger 

if (i >= 0 && nums1[i] > nums2[j]) {
Enter fullscreen mode Exit fullscreen mode

This means:

  • Both arrays still have elements
  • The current element in nums1 is larger

So we place it at position k:

nums1[k] = nums1[i];
i--;
k--;
Enter fullscreen mode Exit fullscreen mode

We move pointers left because that value is now placed.

Case 2: nums2[j] is bigger or nums1 is exhausted 

else {
    nums1[k] = nums2[j];
    j--;
    k--;
}
Enter fullscreen mode Exit fullscreen mode

This handles two situations:

  • nums2[j] is larger
  • nums1 has no elements left (i < 0)

So we safely place nums2[j] into nums1.

Full Code 

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 (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                k--;
                i--;
            } else {
                nums1[k] = nums2[j];
                k--;
                j--;
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Example Walkthrough (Very Slow)

Input:

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
Enter fullscreen mode Exit fullscreen mode

Start:

  • i = 2 (nums1[2] = 3)
  • j = 2 (nums2[2] = 6)
  • k = 5

Step by step:

  • Compare 3 and 6 → place 6
  • Compare 3 and 5 → place 5
  • Compare 3 and 2 → place 3
  • Compare 2 and 2 → place 2
  • Compare 1 and 2 → place 2
  • nums2 exhausted → stop

Final nums1:

[1,2,2,3,5,6]
Enter fullscreen mode Exit fullscreen mode

Why This Always Works

  • You never overwrite useful values
  • Largest elements are placed first
  • Empty space in nums1 is used correctly
  • Every element is handled exactly once

Time and Space Complexity

  • Time: O(m + n)
  • Space: O(1) (in place)

Final Takeaway

This problem is not about merging two arrays.

It’s about choosing the correct direction.

Once you realize that the extra space is at the end, merging from the back becomes the most natural and safest approach.

Top comments (0)