Skip to content

Volume ITechnology

4.0.19 — Merge Two Sorted Arrays ​

Classic · Easy to Medium · LeetCode 88 (Merge Sorted Array), LeetCode 349 (Intersection)

The problem ​

  1. Two arrays are each sorted. Combine them into one sorted array. [1, 4, 7] and [2, 3, 9] give [1, 2, 3, 4, 7, 9].
  2. LeetCode 88: the first array has empty space at its end, exactly big enough for the second. Merge the second into the first, in place.
  3. Find the union and the intersection of two sorted arrays.

The slow way ​

Glue the two arrays together and sort the result. sorted(a + b) is correct, but it costs O((m + n) \log (m + n)). It ignores the most useful fact we were given: both arrays are already sorted.

The idea: compare the two fronts ​

Picture two sorted piles of exam papers, smallest score on top. To make one sorted pile, look at the two top papers. Take the smaller one. Repeat. You never need to look below the top of either pile.

Why is the smaller top always the right next choice? Each pile is sorted, so its top is the smallest paper in that pile. The smaller of the two tops is therefore the smallest paper left anywhere.

1. Merge into a new list ​

python
def merge(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out = []
    while i < len(a) and j < len(b):     # (1)
        if a[i] <= b[j]:                 # (2)
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])                    # (3)
    out.extend(b[j:])
    return out

print(merge([1, 4, 7], [2, 3, 9]))     # → [1, 2, 3, 4, 7, 9]
print(merge([], [5, 6]))              # → [5, 6]
print(merge([1, 2, 2], [2, 3]))       # → [1, 2, 2, 2, 3]

(1) Keep going while both arrays still have elements.

(2) Take the smaller front. On a tie we take from a first, using <=. This keeps equal elements from a ahead of equal elements from b. That is what makes merge sort stable, as 4.0.27 explains. Using < would still give a sorted result, but it would not be stable.

(3) One array has run out. Everything left in the other is already sorted and is bigger than everything taken so far. So copy it all at once. Only one of these two lines adds anything. The other adds an empty slice.

Trace on [1, 4, 7] and [2, 3, 9]:

a[i]b[j]takeout
1211
4221 2
4331 2 3
4941 2 3 4
7971 2 3 4 7
—9leftover1 2 3 4 7 9

Each step takes one element. There are m + n elements, so it is O(m + n) time. The output list is O(m + n) memory.

2. Merge in place, from the back ​

LeetCode 88 gives nums1 with length m + n. Its first m slots hold real values. The last n slots are zeros, just placeholders. nums2 holds n values.

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

Why not merge from the front? If you put the smallest element into nums1[0], you overwrite a real value of nums1 that has not been placed yet. You would have to shift everything right to make room. That is O(n) per insert.

Merge from the back instead. The empty space is at the end of nums1. So fill the array from the end, taking the largest remaining element each time. The write position always stays at or ahead of the unread part of nums1, so nothing unread is ever overwritten.

python
def merge_in_place(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    i, j = m - 1, n - 1             # (1)
    write = m + n - 1               # (2)
    while j >= 0:                   # (3)
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

a = [1, 2, 3, 0, 0, 0]
merge_in_place(a, 3, [2, 5, 6], 3)
print(a)   # → [1, 2, 2, 3, 5, 6]

b = [4, 5, 6, 0, 0, 0]
merge_in_place(b, 3, [1, 2, 3], 3)
print(b)   # → [1, 2, 3, 4, 5, 6]

(1) Start at the last real value of each array.

(2) Start writing at the very last slot.

(3) Loop while nums2 still has values. When nums2 is used up, whatever is left of nums1 is already in the right place, at the front. There is nothing to copy. But if nums1 runs out first, the i >= 0 check sends every remaining nums2 value to the front.

Why can write never overwrite an unread nums1 value? At every moment, write equals i + j + 1. The number of free slots ahead of the unread part of nums1 is exactly the number of nums2 values still left. As long as j >= 0, that is at least one, so write is always past i.

Trace on the first example:

nums1[i]nums2[j]takenums1 after
3661 2 3 0 0 6
3551 2 3 0 5 6
3231 2 3 3 5 6
222 (from nums2, tie)1 2 2 3 5 6
—nums2 emptystop1 2 2 3 5 6

O(m + n) time and O(1) extra memory.

3. Union and intersection of sorted arrays ​

The same walk answers both.

python
def union_sorted(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out = []
    def add(x):
        if not out or out[-1] != x:     # skip repeats
            out.append(x)
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            add(a[i]); i += 1
        elif b[j] < a[i]:
            add(b[j]); j += 1
        else:                           # equal: add once, move both
            add(a[i]); i += 1; j += 1
    for x in a[i:]: add(x)
    for x in b[j:]: add(x)
    return out

def intersect_sorted(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1                      # a[i] is too small to be in b
        elif b[j] < a[i]:
            j += 1
        else:
            if not out or out[-1] != a[i]:
                out.append(a[i])
            i += 1; j += 1
    return out

print(union_sorted([1, 2, 2, 4], [2, 3, 4, 5]))      # → [1, 2, 3, 4, 5]
print(intersect_sorted([1, 2, 2, 4], [2, 3, 4, 5]))  # → [2, 4]

For the intersection, when a[i] < b[j], the value a[i] cannot appear in b at all. Everything left in b is at least b[j], which is already bigger. So it is safe to skip. That reasoning, "this element can never match anything later, so drop it", is the heart of every two-pointer proof.

For unsorted arrays, use sets instead: set(a) | set(b) and set(a) & set(b).

Complexity ​

All the merges and the union and intersection are O(m + n) time. The in-place merge uses O(1) extra memory. The others build an output list.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Why not join the two lists and sort them?" That costs O(N \log N). The two lists are already sorted, and merging uses that to finish in O(N).

"Merge the second list into the first, in place." Fill the first list from the back, taking the bigger value each time. The empty space is at the back, so you never write over a value you still need.

"What if the first list runs out first?" Copy whatever is left of the second list. If the second list runs out first, you are already done, because the rest of the first list is in place.

"Is your merge stable?" Yes, if you use <= and take from the first list when the two values are equal.

One thing to volunteer: "This merge is the core step of merge sort. Once you can merge two sorted lists in linear time, sorting in n \log n follows."

Next: 4.0.20 Sort 0s, 1s and 2s. Sorting three kinds of value in one pass, with three pointers.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet