LeetCode 88 Explained: Four Approaches, Mistakes, Fixes & the Final Optimal Python Solution

Evolving My Solution to “Merge Sorted Array”

A practical, beginner-friendly walkthrough showing four versions of my code (from a naive approach to the optimal in-place two-pointer solution). Includes explanations, complexity and ready-to-paste code.

Problem Summary

You are given two sorted arrays:

• nums1 with size m + n (first m are valid)
• nums2 with size n

Goal: Merge nums2 into nums1 in sorted order in-place.

---

Version 1 — Beginner Approach (Extra List)

I merged into a new list then copied back. Works, but not in-place and uses extra memory.

 class Solution:
    def merge(self, nums1, m, nums2, n):
        result = []
        p1 = 0
        p2 = 0

        for _ in range(m+n):
            if p1 >= m:
                result.extend(nums2[p2:n])
                break
            elif p2 >= n:
                result.extend(nums1[p1:m])
                break
            elif nums1[p1] < nums2[p2]:
                result.append(nums1[p1])
                p1 += 1
            else:
                result.append(nums2[p2])
                p2 += 1

        for i in range(len(result)):
            nums1[i] = result[i]

Complexity: Time O(m+n), Space O(m+n) — not in-place.

---

Version 2 — First In-Place Attempt (Fixed <code>for</code> Loop)

Fills nums1 from the end. In-place but the loop always runs m+n iterations.

class Solution:
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1

        for _ in range(m+n):
            if i < 0:
                nums1[k] = nums2[j]
                j -= 1
            elif j < 0:
                break
            elif nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

Complexity: Time O(m+n) (always), Space O(1).

---

Version 3 — Improved In-Place (Early Exit)

Added an early break when nums2 is exhausted so the loop can stop early in favorable cases.

class Solution:
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1

        for _ in range(m+n):
            if j < 0:
                break
            if i < 0 or nums1[i] < nums2[j]:
                nums1[k] = nums2[j]
                j -= 1
            else:
                nums1[k] = nums1[i]
                i -= 1
            k -= 1

Complexity: Best O(n), Average O(m+n), Worst O(m+n), Space O(1).

---

Version 4 — Final Optimal (Canonical Two-Pointer)

Cleanest and most interview-friendly: loop while nums2 still has elements.

class Solution:
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1

        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

Complexity: Best O(n), Average O(m+n), Worst O(m+n), Space O(1).

---

Comparison Table

Version	In-Place?	Best	Avg	Worst	Space
1 — Extra List	No	O(m+n)	O(m+n)	O(m+n)	O(m+n)
2 — Fixed for loop	Yes	O(m+n)	O(m+n)	O(m+n)	O(1)
3 — For loop + early exit	Yes	O(n)	O(m+n)	O(m+n)	O(1)
4 — Optimal while loop	Yes	O(n)	O(m+n)	O(m+n)	O(1)

Summary — Key Takeaways

• Always read constraints — the guarantee that nums1 has m+n space unlocked the in-place approach.
• Filling from the end avoids overwriting data and enables in-place merging.
• Early-exit logic (stop when nums2 is done) improves best-case performance.
• The canonical while j >= 0 two-pointer solution is concise, efficient, and interview-ready.

Published by road2geeks