LogoKode$word
LeetCode 88 Merge Sorted Array Explained: Brute Force to Optimal Java Solution (3 Pointer Approach)
LeetCode 88 Merge Sorted Array Explained: Brute Force to Optimal Java Solution (3 Pointer Approach)

LeetCode 88 Merge Sorted Array Explained: Brute Force to Optimal Java Solution (3 Pointer Approach)

Complete Interview Guide with Intuition, Dry Run, Multiple Approaches & Complexity Analysis

15 views
0
0
ArraysTwo PointersSortingJavaEasyLeetcode
Github icon
Github icon
Listen to articleAudio version
brillicode ad banner

Introduction

LeetCode 88 — Merge Sorted Array is one of the most important beginner-friendly array problems asked in coding interviews.

At first glance, the problem looks very easy because both arrays are already sorted. But the real challenge is:

How do we merge them efficiently without using extra space?

This question is commonly asked by companies because it tests:

  1. Array manipulation
  2. Two pointer technique
  3. In-place modification
  4. Edge case handling
  5. Space optimization

The most important learning from this problem is understanding:

Why merging from the back is the optimal strategy.

In this article, we will cover:

  1. Problem understanding
  2. Brute force approach
  3. Better approach
  4. Optimal 3-pointer solution
  5. Step-by-step dry run
  6. Time & space complexity
  7. Common mistakes
  8. Interview tips
  9. FAQs

By the end, you will completely understand the logic behind this problem.

Try This Problem

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

Problem Statement

You are given two sorted arrays:

nums1
nums2

Along with two integers:

m → valid elements in nums1
n → elements in nums2

The array nums1 has size:

m + n

The last n positions are empty spaces represented by 0.

Your task is to merge nums2 into nums1 such that the final array remains sorted.

Example

Example 1

Input

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

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

Output

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

Understanding the Problem

Let us simplify what the question is asking.

We have:

nums1 → already sorted
nums2 → already sorted

We need:

one final sorted array

But there is one important condition:

We must store the answer inside nums1 itself.

That means:

  1. No returning new array
  2. Modify nums1 directly

Why This Problem is Tricky

Many beginners immediately think:

Copy nums2 into nums1
Then sort nums1

This works.

But interviews usually expect a more optimized solution.

The challenge is:

Can we merge without sorting again?

Yes — using the Two Pointer technique.

Approach 1 — Brute Force Solution

Idea

  1. Copy all elements of nums2 into empty positions of nums1
  2. Sort the final array

Java Code


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

// Copy nums2 into nums1
for(int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}

// Sort final array
Arrays.sort(nums1);
}
}

Dry Run of Brute Force

Initial:

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

After copying:

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

After sorting:

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

Time Complexity

Copying

O(n)

Sorting

O((m+n) log(m+n))

Space Complexity

O(1)

Drawback of Brute Force

Sorting again is unnecessary because:

  1. Arrays are already sorted
  2. We can merge smarter

Approach 2 — Extra Array Merge

Idea

Use a third temporary array.

This works exactly like merge step in Merge Sort.

Steps

  1. Compare elements from both arrays
  2. Insert smaller one into temp array
  3. Copy final temp array into nums1

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(i = 0; i < m + n; i++) {
nums1[i] = temp[i];
}
}
}

Time Complexity

O(m + n)

Space Complexity

O(m + n)

Can We Do Better?

Yes.

The interview-expected solution uses:

Optimal Approach — Three Pointers from Back

Most Important Observation

The end of nums1 already contains empty spaces.

So instead of merging from front:

We merge from the back.

This avoids overwriting important elements.

Main Idea

We use 3 pointers:

left → last valid element in nums1
right → last element in nums2
insertPos → last position of nums1

We compare:

nums1[left]
nums2[right]

The larger element is placed at:

nums1[insertPos]

Then move pointers backward.

Why Backward Merging Works

Suppose:

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

If we start from front:

we overwrite existing values

But from back:

empty spaces already exist

So no data loss occurs.

Optimal Java Solution

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

int left = m - 1;
int right = n - 1;
int insertPos = m + n - 1;

for(int i = insertPos; i >= 0; i--) {

if(right < 0 ||
(left >= 0 && nums1[left] >= nums2[right])) {

nums1[i] = nums1[left];
left--;
}
else {

nums1[i] = nums2[right];
right--;
}
}
}
}

Step-by-Step Dry Run

Input

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

Initial Pointers

left = 2 → value 3
right = 2 → value 6
insertPos = 5

Step 1

Compare:

3 vs 6

6 is larger.

Place 6 at end.

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

Move:

right--
insertPos--

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 2.

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

Done.

Time Complexity

We traverse both arrays once.

O(m + n)

Space Complexity

No extra space used.

O(1)

Why This is the Best Solution

This solution is optimal because:

✅ No sorting required

✅ No extra array required

✅ Single traversal

✅ In-place merging

✅ Interview preferred solution

Common Mistakes

1. Merging from Front

This overwrites elements in nums1.

2. Forgetting Edge Cases

Example:

m = 0

or

n = 0

3. Wrong Pointer Initialization

Correct:

left = m - 1
right = n - 1

4. Array Index Out of Bounds

Always check:

left >= 0
right >= 0

Interview Tips

If interviewer asks:

“Why merge from back?”

Your answer:

Because nums1 already has empty spaces at the end. Backward traversal prevents overwriting existing sorted elements.

Frequently Asked Questions

Q1. Why not use sorting?

Because arrays are already sorted.

Sorting again wastes time.

Q2. Why start from end?

To safely place larger elements without overwriting.

Q3. Is this similar to Merge Sort?

Yes.

This is essentially the merge step of Merge Sort.

Q4. What if nums2 is empty?

Then nums1 remains unchanged.

Q5. What if nums1 has no valid elements?

Then copy all elements from nums2.

Final Takeaway

The biggest learning from this problem is:

Whenever extra space exists at the end of an array, think about backward traversal.

This pattern appears frequently in interview questions.

Conclusion

LeetCode 88 is one of the best beginner problems to master:

  1. Two pointers
  2. In-place array modification
  3. Efficient merging
  4. Space optimization

Although the brute force solution works, the optimal 3-pointer approach is the real interview solution.

Once you understand why backward merging works, this problem becomes extremely easy to solve in interviews and coding rounds.

Related Articles

LeetCode 143 Reorder List - Java Solution Explained

LeetCode 143 Reorder List - Java Solution Explained

Learn how to solve LeetCode 143 Reorder List using Fast & Slow Pointer, Reverse Linked List, and Merge techniques in Java. Includes step-by-step dry run, time & space complexity analysis.

Read Article
Maximum Twin Sum of a Linked List (LeetCode 2130) — Intuition, Dry Run & Optimal Approach

Maximum Twin Sum of a Linked List (LeetCode 2130) — Intuition, Dry Run & Optimal Approach

Learn How to Pair Nodes Efficiently Using Fast & Slow Pointer and Reverse Technique

Read Article
Reverse a Stack Without Extra Space | Java Recursive Solution

Reverse a Stack Without Extra Space | Java Recursive Solution

Learn how to reverse a stack using recursion without extra space. Step-by-step explanation, Java code, dry run, and interview tips included.

Read Article
Reverse a Stack — GFG Problem Solved (3 Approaches Explained)

Reverse a Stack — GFG Problem Solved (3 Approaches Explained)

Learn how to reverse a stack in Java with 3 different approaches — extra stack, ArrayList, and recursion. Full solution to the GFG "Reverse a Stack" problem explained step by step in easy language with code.

Read Article
Ai Assistant Kas