26. Remove Duplicates from Sorted Array

Quick Identifier

• Topic: arrays-hashing
• Pattern: Two Pointers (Fast / Slow Pointers)
• Hint: The array is already sorted, meaning duplicates are perfectly adjacent. Use a "slow" pointer to track where the next unique element should go, and a "fast" pointer to scout ahead for new unique elements.
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• LeetCode: 26

Quick Sights

• Time Complexity: O(n). The fast pointer right scans through the array exactly once.
• Space Complexity: O(1). The problem explicitly demands an in-place solution. No extra data structures are allocated.
• Core Mechanism: Maintain two indices: left (the insert position for the next unique element) and right (the scanner). Start both at index 1. As right scans forward, if nums[right] is different from nums[right-1], it means we've found a new unique number. Write this new number to nums[left], and increment left.

Concept Explanation

As a senior engineer, whenever you see "Sorted Array" paired with "Remove Duplicates In-Place", your mind should immediately snap to the Fast/Slow Two-Pointer pattern.

1. The In-Place Constraint: You cannot create a new array. You must overwrite the existing array.
2. The Sorting Advantage: Because it's sorted, you don't need a Hash Set to remember what you've seen. All duplicates of the number x will be clumped together directly adjacent to the first x.
3. The Two Roles:
   • The Scanner (right): This pointer runs ahead. Its only job is to look at the number immediately behind it (right - 1). If they are the same, it's a duplicate—ignore it. If they are different, the Scanner has found a brand new number!
   • The Writer (left): This pointer is slow. It stays behind, pointing to the exact slot where the next discovered unique number must be written.
4. The Handoff: When the Scanner finds a new number, it gives it to the Writer. The Writer overwrites its current slot, steps forward one space, and waits for the Scanner to find the next new number. The array elements from 0 to left - 1 are now guaranteed to be the compacted, unique prefix.

Diagram

This flowchart traces the fast/slow pointer logic for overwriting duplicates.

Study Pattern (SDE3+)

• 0–3 min: Immediately identify the constraint: $O(1)$ space. Point out that a Hash Set is the naive solution if the array wasn't sorted, but the sorting makes the Fast/Slow pointer pattern optimal.
• Implementation pass: Initialize both left and right at 1. Why? Because the element at index 0 is always the first unique element by definition. You only need to start scanning and writing from index 1.
• 5 min extension: What if the interviewer changes the rule to "Remove duplicates such that each element appears at most twice"? (LeetCode 80). The logic remains identical, but the Scanner checks nums[right] != nums[left - 2] instead of nums[right - 1]. The left pointer still acts as the Writer.

Approaches

• Brute force — Use a Hash Set to track uniqueness, build a new array, copy it back. Time: $O(n)$, Space: $O(n)$. Fails the $O(1)$ space constraint.
• Optimal (Fast/Slow Pointers) — Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	// 'left' is the Writer. It marks where the next unique element should go.
	// We start at 1 because nums[0] is inherently unique.
	left := 1

	// 'right' is the Scanner.
	for right := 1; right < len(nums); right++ {
		// If we encounter a new number different from the previous one
		if nums[right] != nums[right-1] {
			nums[left] = nums[right] // Write the new unique number
			left++                   // Move the Writer forward
		}
	}

	// The 'left' pointer now represents the length of the unique prefix
	return left
}

JavaScript

function removeDuplicates(nums) {
	if (nums.length === 0) return 0;

	let left = 1; // Writer pointer

	for (let right = 1; right < nums.length; right++) {
		// Scanner detects a new unique element
		if (nums[right] !== nums[right - 1]) {
			nums[left] = nums[right];
			left++;
		}
	}

	return left;
}

Walkthrough

Input: nums = [0,0,1,1,1,2,2,3,3,4]

Output: 5. The array's first 5 elements are [0,1,2,3,4]. (The rest of the array is ignored by the grader).

Edge Cases

• Array length is 0 (Handled by the explicit len == 0 check).
• Array length is 1 (Loop won't execute, returns 1, which is correct).
• Array has all identical elements (Scanner never triggers, returns 1, array unchanged).
• Array is already perfectly unique (Scanner triggers every time, writes elements to their existing indices redundantly but safely).

Pitfalls

• Starting left or right at 0. You'll end up comparing nums[0] with nums[-1] (out of bounds).
• Comparing nums[right] against nums[left]. You must compare the Scanner against its own trail (nums[right-1]) to detect state changes in the sorted sequence.

Similar Problems

• 027. Remove Element — The exact same Writer/Scanner pattern, but checking against a specific target value instead of duplicates.
• 283. Move Zeroes — Another in-place array compaction using Fast/Slow pointers.
• 80. Remove Duplicates from Sorted Array II — The Medium variant allowing at most 2 duplicates.

Mind-Map Tags

#two-pointers #fast-slow #sorted-array #in-place-compaction