88. Merge Sorted Array

At a Glance

• Topic: arrays-hashing
• Pattern: Two Pointers (in-place, fill from end)
• Difficulty: Easy
• Companies: Amazon, Facebook, Microsoft, Bloomberg, Apple
• Frequency: High
• LeetCode: 88

Problem (one-liner)

Merge two sorted arrays into first: first has length totalLength with trailing slots filled with 0 for padding; the first firstLength elements are sorted. second has length secondLength sorted. Merge into first in non-decreasing order in-place.

Recognition Cues

• "Merge sorted array" with extra buffer space at end
• Backward fill avoids overwriting unmerged front part of first

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — merge into new array then copy — O(m+n) time / O(m+n) extra space.
• Better — forward merge naïvely — overwrites elements still needed.
• Optimal — three pointers from the tail — O(m+n) time / O(1) extra space.

Optimal Solution

Go

package main

func merge(first []int, firstLength int, second []int, secondLength int) {
	writeIndex := firstLength + secondLength - 1
	leftIndex := firstLength - 1
	rightIndex := secondLength - 1
	for rightIndex >= 0 {
		if leftIndex >= 0 && first[leftIndex] > second[rightIndex] {
			first[writeIndex] = first[leftIndex]
			leftIndex--
		} else {
			first[writeIndex] = second[rightIndex]
			rightIndex--
		}
		writeIndex--
	}
}

JavaScript

function merge(first, firstLength, second, secondLength) {
	let writeIndex = firstLength + secondLength - 1;
	let leftIndex = firstLength - 1;
	let rightIndex = secondLength - 1;
	while (rightIndex >= 0) {
		if (leftIndex >= 0 && first[leftIndex] > second[rightIndex]) {
			first[writeIndex] = first[leftIndex];
			leftIndex--;
		} else {
			first[writeIndex] = second[rightIndex];
			rightIndex--;
		}
		writeIndex--;
	}
}

Walkthrough

first = [1,2,3,0,0,0], firstLength = 3, second = [2,5,6], secondLength = 3

Remaining second exhausted; loop ends.

Edge Cases

• secondLength = 0 — nothing to copy.
• All of second smaller — fill entirely from second tail.
• All of first smaller — only decrement leftIndex.

Pitfalls

• Merging left-to-right without scratch space — corrupts unread portion of first.
• Off-by-one on writeIndex initialization.

Similar Problems

• 026. Remove Duplicates from Sorted Array — two-pointer write position.
• 167. Two Sum II — Input Array Is Sorted — sorted array two pointers.
• 21. Merge Two Sorted Lists — same merge discipline on lists.

Variants

• Merge k sorted arrays — heap or divide-and-conquer.
• Count inversions while merging — merge sort variant.

Mind-Map Tags

#two-pointers #merge #in-place #sorted #arrays