Remove Duplicates from Sorted Array (LeetCode

Learn how to solve Remove Duplicates from Sorted Array using brute force and the optimal two-pointer in-place approach. Includes intuition, dry runs, Java code, correctness proof, complexity analysis, edge cases, interview tips, and production applications.

Introduction

Remove Duplicates from Sorted Array (LeetCode #26) is a foundational problem for learning the in-place Two Pointer write pattern.

It is frequently asked at companies like:

Google
Amazon
Microsoft
Meta
Apple
Netflix
Adobe
Goldman Sachs

Interviewers use this problem to evaluate whether a candidate can:

Modify an array in-place without extra memory
Use a slow/fast pointer pattern correctly
Reason about in-place mutations
Write clean, production-quality Java code

The key insight is:

Use a slow pointer that tracks the position of the next unique element, and a fast pointer that scans through the array. Whenever the fast pointer finds a new unique value, write it to the slow pointer position.

If the fast element equals the slow element:

Move fast pointer right (skip duplicate)

If the fast element is different from the slow element:

Advance slow pointer, then write fast value at slow position

This achieves in-place deduplication in a single pass with O(1) extra space.

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once.

Return k — the number of unique elements.

The first k elements of nums must contain the unique elements in their original order.

The remaining elements beyond k do not matter.

You must do this with O(1) extra space.

Formula

After the algorithm completes:

nums[0..k-1] contains the unique elements in sorted order

k = number of unique elements

Example 1

Input

nums = [1, 1, 2]

Output

k = 2

nums = [1, 2, _]

Explanation:

Unique elements: 1, 2

The first two positions contain [1, 2]

The third position is irrelevant

Example 2

Input

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

Output

k = 5

nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Explanation:

Unique elements: 0, 1, 2, 3, 4

The first five positions contain [0, 1, 2, 3, 4]

Example 3

Input

nums = [1, 2, 3, 4, 5]

Output

k = 5

nums = [1, 2, 3, 4, 5]

Explanation:

No duplicates exist. Array is unchanged.

Important Problem Guarantees

The LeetCode problem guarantees:

1 <= nums.length <= 30,000
-100 <= nums[i] <= 100
The array is sorted in non-decreasing order.
The judge only checks the first k elements and the return value.
Elements beyond index k - 1 are ignored.

These guarantees mean sorting is not required, and the in-place Two Pointer approach is the expected solution.

What Is the Slow-Fast Two Pointer Pattern?

The slow-fast pattern uses two pointers moving in the same direction at different speeds.

Slow Pointer → Tracks the write position (next unique slot)

Fast Pointer → Scans through the entire array

Visual:

graph TD
    S["S"] --> F["F"]
    F["F"] --> N_0_0_1_1_1_2_2_3_3_4["0   0   1   1   1   2   2   3   3   4"]

At every step:

nums[fast] == nums[slow]  → fast++  (skip duplicate)

nums[fast] != nums[slow]  → slow++, nums[slow] = nums[fast], fast++

Why Does the Sorted Array Matter?

Because the array is sorted, all duplicates of a value are adjacent.

[0, 0, 0, 1, 1, 2]

A single forward scan is enough — there is no need to check previously seen values.

If the array were unsorted:

[0, 1, 0, 2, 1]

A HashSet would be required to track seen values, adding O(n) space.

The sorted property makes the O(1) space solution possible.

Approach 1 — Brute Force (Extra Space)

Core Idea

Copy all unique values into a new array using a HashSet or by scanning for changes.

Then overwrite the original array with the unique values.

List → Collect uniques → Write back

Java Code — Brute Force

import java.util.ArrayList;
import java.util.List;

public class RemoveDuplicatesBruteForce {

    public int removeDuplicates(int[] nums) {

        List<Integer> unique = new ArrayList<>();

        unique.add(nums[0]);

        for (int i = 1; i < nums.length; i++) {

            if (nums[i] != nums[i - 1]) {
                unique.add(nums[i]);
            }

        }

        for (int i = 0; i < unique.size(); i++) {
            nums[i] = unique.get(i);
        }

        return unique.size();

    }

}

Brute Force Complexity

Complexity	Value
Time	O(n)
Space	O(n)

The solution is linear in time but allocates an extra list proportional to the number of unique elements.

The problem explicitly requires O(1) extra space.

Why Brute Force Fails the Constraint

The extra list uses:

O(k) space

where k is the number of unique elements.

In the worst case:

k = n

(no duplicates — all elements are unique).

The extra list holds the entire array.

The Two Pointer approach avoids this by writing directly into the input array.

Approach 2 — Optimal Two Pointer Solution

Core Idea

Use a slow pointer slow that points to the last confirmed unique position.

Use a fast pointer fast that scans ahead.

When nums[fast] differs from nums[slow], it is a new unique value:

slow++;
nums[slow] = nums[fast];

Then advance fast regardless.

At the end, return slow + 1 (the count of unique elements).

Algorithm

graph TD
    slow_0["slow = 0"] --> fast_1["fast = 1"]
    fast_1["fast = 1"] --> Loop_while_fast_nums_length["Loop while fast  nums.length:"]
    Loop_while_fast_nums_length["Loop while fast  nums.length:"] --> nums_fast_nums_slow["nums(fast) == nums(slow)"]
    nums_fast_nums_slow["nums(fast) == nums(slow)"] --> No["No  →"]
    No["No  →"] --> slow["slow++"]
    slow["slow++"] --> nums_slow_nums_fast["nums(slow) = nums(fast)"]
    nums_slow_nums_fast["nums(slow) = nums(fast)"] --> fast["fast++"]
    fast["fast++"] --> Return_slow_1["Return slow + 1"]

Java Code — Optimal Solution

public class RemoveDuplicates {

    public int removeDuplicates(int[] nums) {

        int slow = 0;

        for (int fast = 1;
             fast < nums.length;
             fast++) {

            if (nums[fast] != nums[slow]) {

                slow++;
                nums[slow] = nums[fast];

            }

        }

        return slow + 1;

    }

}

LeetCode-Style Implementation

public class Solution {

    public int removeDuplicates(int[] nums) {

        int slow = 0;

        for (int fast = 1;
             fast < nums.length;
             fast++) {

            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }

        }

        return slow + 1;

    }

}

Both implementations are equivalent. The expanded version is clearer for interviews; the compact version is idiomatic for production.

Two Pointer Flow

graph TD
    Initialize_slow_0_fast_1["Initialize slow = 0, fast = 1"] --> fast_nums_length["fast  nums.length?"]
    fast_nums_length["fast  nums.length?"] --> Yes["Yes ↓"]
    Yes["Yes ↓"] --> nums_fast_nums_slow["nums(fast) == nums(slow)?"]
    nums_fast_nums_slow["nums(fast) == nums(slow)?"] --> No["No  →"]
    No["No  →"] --> slow["slow++"]
    slow["slow++"] --> nums_slow_nums_fast["nums(slow) = nums(fast)"]
    nums_slow_nums_fast["nums(slow) = nums(fast)"] --> fast["fast++"]
    fast["fast++"] --> Repeat["Repeat"]

Detailed Dry Run

Input:

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

Initial state:

slow = 0
fast = 1

Iteration 1

nums[fast] = 0
nums[slow] = 0

Equal → fast++

slow = 0
fast = 2

Iteration 2

nums[fast] = 1
nums[slow] = 0

Different → slow++ → slow = 1
            nums[1] = 1
            fast++

Array: [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
slow = 1
fast = 3

Iteration 3

nums[fast] = 1
nums[slow] = 1

Equal → fast++

slow = 1
fast = 4

Iteration 4

nums[fast] = 1
nums[slow] = 1

Equal → fast++

slow = 1
fast = 5

Iteration 5

nums[fast] = 2
nums[slow] = 1

Different → slow++ → slow = 2
            nums[2] = 2
            fast++

Array: [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
slow = 2
fast = 6

Iteration 6

nums[fast] = 2
nums[slow] = 2

Equal → fast++

slow = 2
fast = 7

Iteration 7

nums[fast] = 3
nums[slow] = 2

Different → slow++ → slow = 3
            nums[3] = 3
            fast++

Array: [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
slow = 3
fast = 8

Iteration 8

nums[fast] = 3
nums[slow] = 3

Equal → fast++

slow = 3
fast = 9

Iteration 9

nums[fast] = 4
nums[slow] = 3

Different → slow++ → slow = 4
            nums[4] = 4
            fast++

Array: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
slow = 4
fast = 10

fast = 10 = nums.length → loop ends.

Return:

slow + 1 = 5

First 5 elements:

[0, 1, 2, 3, 4]

Dry Run Table

fast	nums[fast]	nums[slow]	Action	slow	Array (first k)
1	0	0	skip	0	[0]
2	1	0	write, slow++	1	[0, 1]
3	1	1	skip	1	[0, 1]
4	1	1	skip	1	[0, 1]
5	2	1	write, slow++	2	[0, 1, 2]
6	2	2	skip	2	[0, 1, 2]
7	3	2	write, slow++	3	[0, 1, 2, 3]
8	3	3	skip	3	[0, 1, 2, 3]
9	4	3	write, slow++	4	[0, 1, 2, 3, 4]

Return slow + 1 = 5.

Visual Pointer Movement

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        S
        F→ skip (0==0)
           F→ write 1, S moves
              F→ skip (1==1)
                 F→ skip (1==1)
                    F→ write 2, S moves
                       F→ skip (2==2)
                          F→ write 3, S moves
                             F→ skip (3==3)
                                F→ write 4, S moves

Result: [0, 1, 2, 3, 4, ...]
         S at index 4
         Return 5

Why This Works

The slow pointer always points to the last confirmed unique element.

The region nums[0..slow] is always a valid, sorted unique prefix.

When fast finds a value different from nums[slow]:

It is guaranteed to be larger (array is sorted)

It is guaranteed to be new (no duplicates are adjacent in the unique prefix)

Writing it at slow+1 extends the unique prefix correctly

No element in the unique prefix [0..slow] is ever overwritten with a wrong value.

Correctness Proof

Invariant: After each iteration, nums[0..slow] contains exactly the unique elements seen so far, in sorted order.

Base case: Before the loop, slow = 0 and nums[0..0] contains exactly the first element — trivially unique.

Inductive step:

If nums[fast] == nums[slow]: the value is a duplicate. slow does not move. The prefix nums[0..slow] is unchanged. Invariant holds.
If nums[fast] != nums[slow]: since the array is sorted and fast > slow, nums[fast] > nums[slow]. It is a new unique value. Writing it at slow + 1 extends the unique prefix by one. Invariant holds.

Termination: fast advances by 1 every iteration. Loop terminates when fast == nums.length.

Conclusion: At termination, nums[0..slow] contains all unique elements. Return value slow + 1 is correct.

Loop Invariant

At every iteration:

nums[0..slow] contains all unique elements
seen so far in their original sorted order

When the loop ends:

All elements have been visited.
nums[0..slow] is the complete unique prefix.
slow + 1 is the answer.

Complexity Analysis

Complexity	Value
Time	O(n)
Space	O(1)

fast traverses the array exactly once.

slow only advances when a unique value is found — at most n times.

Total operations: proportional to n.

No extra data structures are allocated.

Why the Complexity Is Not O(n²)

Although two pointers are used, they are not nested.

Both move left to right.

fast advances every iteration.

Total iterations equal n - 1.

O(n)

not:

O(n²)

Why Use `slow = 0` and `fast = 1`?

slow = 0 seeds the unique prefix with the first element.

The first element is always unique by definition — there is no previous element to compare it against.

fast = 1 starts the scan at the second element.

This avoids a redundant comparison on the first iteration.

Production-Ready Implementation

import java.util.Objects;

public class RemoveDuplicatesSorted {

    /**
     * Removes duplicates from a sorted array in-place.
     *
     * The first k elements of nums will contain the unique
     * elements in their original sorted order.
     *
     * @param nums non-null sorted integer array, length >= 1
     * @return k, the number of unique elements
     * @throws IllegalArgumentException if nums is null or empty
     */
    public int removeDuplicates(int[] nums) {

        Objects.requireNonNull(nums,
                "nums must not be null");

        if (nums.length == 0) {
            throw new IllegalArgumentException(
                    "nums must not be empty");
        }

        int slow = 0;

        for (int fast = 1;
             fast < nums.length;
             fast++) {

            if (nums[fast] != nums[slow]) {

                slow++;
                nums[slow] = nums[fast];

            }

        }

        return slow + 1;

    }

}

Edge Cases

Single Element

Input

nums = [5]

Output

k = 1

nums = [5]

Loop never executes. Return slow + 1 = 1.

All Same Elements

Input

nums = [3, 3, 3, 3, 3]

Output

k = 1

nums = [3, _, _, _, _]

fast scans all — every element equals nums[slow]. slow never advances.

Return 1.

No Duplicates

Input

nums = [1, 2, 3, 4, 5]

Output

k = 5

nums = [1, 2, 3, 4, 5]

Every element is different. slow advances with every fast step.

Array is unchanged because every write is nums[slow] = nums[fast] where slow == fast - 1.

Two Elements — Duplicate

Input

nums = [7, 7]

Output

k = 1

nums = [7, _]

Two Elements — Unique

Input

nums = [3, 9]

Output

k = 2

nums = [3, 9]

Negative Numbers

Input

nums = [-4, -4, -2, 0, 0, 1]

Output

k = 4

nums = [-4, -2, 0, 1, _, _]

Negative values work identically — comparison is value-based.

All Unique with One Duplicate at End

Input

nums = [1, 2, 3, 4, 4]

Output

k = 4

nums = [1, 2, 3, 4, _]

Only the last duplicate is skipped.

Common Interview Mistakes

Mistake 1 — Starting slow and fast at the Same Index

❌  int slow = 0;
    int fast = 0;

Comparing nums[fast] with nums[slow] when both are 0 always finds equality on the first step. This skips the write for the second element incorrectly.

Correct:

int slow = 0;
int fast = 1;

Mistake 2 — Returning slow Instead of slow + 1

❌  return slow;

slow is a zero-based index. The count of unique elements is slow + 1.

Mistake 3 — Writing Before Advancing slow

❌  nums[slow] = nums[fast];
    slow++;

This overwrites nums[slow] (the last confirmed unique value) before advancing. The old value is lost.

Correct:

slow++;
nums[slow] = nums[fast];

Mistake 4 — Using a HashSet (Ignores the Sorted Property)

❌  Set<Integer> seen = new HashSet<>();

A HashSet uses O(n) space. The problem requires O(1) extra space.

The sorted array guarantees that duplicates are adjacent, making a HashSet unnecessary.

Mistake 5 — Using a Second Array

❌  int[] result = new int[nums.length];

This uses O(n) extra space and violates the in-place constraint.

Mistake 6 — Using nums.length - 1 as the Loop Bound

❌  for (int fast = 1; fast < nums.length - 1; fast++)

This misses the last element. Use fast < nums.length.

Mistake 7 — Not Handling a Single-Element Array

❌  // Assume length >= 2

A single-element array should return 1. The implementation must handle this.

With slow = 0 and fast = 1, the loop condition fast < 1 is false immediately — the correct value 1 is returned.

Mistake 8 — Confusing This with Remove Duplicates II

LeetCode #80 (Remove Duplicates II) allows each element to appear at most twice. The logic is different:

// LeetCode #80
if (nums[fast] != nums[slow - 1]) {
    nums[++slow] = nums[fast];
}

Do not confuse the two problems.

Follow-Up 1 — Allow Each Element at Most Twice (LeetCode #80)

Generalize to allow k occurrences:

public int removeDuplicates(int[] nums) {

    int slow = 1;  // first two positions always kept

    for (int fast = 2;
         fast < nums.length;
         fast++) {

        // Compare with two positions back
        if (nums[fast] != nums[slow - 1]) {
            nums[++slow] = nums[fast];
        }

    }

    return slow + 1;

}

For the general case of k allowed duplicates, compare nums[fast] with nums[slow - (k - 1)].

Follow-Up 2 — Remove a Specific Value In-Place (LeetCode #27)

Instead of removing duplicates, remove all occurrences of a given value:

public int removeElement(int[] nums, int val) {

    int slow = 0;

    for (int fast = 0;
         fast < nums.length;
         fast++) {

        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }

    }

    return slow;

}

The slow-fast pattern is identical — only the condition changes.

Follow-Up 3 — What If the Array Is Unsorted?

For an unsorted array, duplicates are not adjacent.

Two options:

Option A — Sort first:

Sort → O(n log n)

Apply Two Pointer → O(n)

Total → O(n log n)

Option B — Use a LinkedHashSet:

Preserve insertion order, deduplicate → O(n) time, O(n) space

For the LeetCode problem, the sorted guarantee is essential to achieving O(1) space.

Follow-Up 4 — Return the Unique Elements as a New Array

public int[] uniqueElements(int[] nums) {

    int k = removeDuplicates(nums);

    return Arrays.copyOfRange(nums, 0, k);

}

This allocates a new array of size k after the in-place pass.

Total space: O(k) for the output.

Follow-Up 5 — Count Total Duplicates Removed

public int countDuplicates(int[] nums) {

    int k = removeDuplicates(nums);

    return nums.length - k;

}

nums.length - k equals the number of elements removed.

Production Applications

The in-place deduplication pattern is used in real engineering systems.

Examples include:

Database result set deduplication before pagination
Log stream deduplication for idempotent event processing
Sorted merge output deduplication in MapReduce pipelines
Time-series data compression — removing repeated sensor readings
IP packet deduplication in network processing pipelines
Sorted cache invalidation list compaction
Financial transaction deduplication in reconciliation batches

The sorted property is frequently available in these systems (sorted indexes, sorted logs, sorted merge outputs), making the O(1) Two Pointer approach directly applicable.

Real-World Example — Sorted Event Log Deduplication

A log pipeline receives sorted events. Duplicate event IDs must be removed before downstream processing.

public int deduplicateEventIds(int[] sortedIds) {

    if (sortedIds == null
            || sortedIds.length == 0) {
        return 0;
    }

    int slow = 0;

    for (int fast = 1;
         fast < sortedIds.length;
         fast++) {

        if (sortedIds[fast]
                != sortedIds[slow]) {

            slow++;
            sortedIds[slow] =
                    sortedIds[fast];

        }

    }

    return slow + 1;

}

The logic is identical to the LeetCode solution.

Real-World Example — Sorted Merge Deduplication

After a K-way sorted merge, the output may contain duplicates from overlapping ranges.

Merge Result: [1, 1, 2, 3, 3, 3, 4]

After deduplication: [1, 2, 3, 4]

k = 4

The Two Pointer approach deduplicates the merged output in O(n) time with O(1) extra space.

Senior-Level Discussion — Why Is This Not O(n²)?

A common misconception is that comparing every element to the previous one is quadratic.

In reality:

fast moves forward exactly once per element → n - 1 steps

slow advances at most once per unique value → at most n steps

Total pointer movements → O(n)

There is no nested iteration. Both pointers move left to right.

Senior-Level Discussion — Is This Stable?

Yes.

The relative order of unique elements is preserved:

Input:  [0, 0, 1, 1, 2]

Output: [0, 1, 2]

The original order 0 → 1 → 2 is maintained.

This is guaranteed because fast scans left to right and slow writes left to right.

Senior-Level Discussion — Can This Handle Very Large Arrays?

Yes.

The algorithm uses:

Time  → O(n) — single pass
Space → O(1) — two integer variables

For a 1-billion-element sorted array, the algorithm processes it in linear time using only two index variables.

The bottleneck is I/O (reading and writing the array), not the algorithm.

Interview Explanation

A strong interview walkthrough:

1. Explain the slow-fast pointer pattern

2. Explain why the sorted property eliminates the need for a HashSet

3. Explain the invariant: nums[0..slow] is always the unique prefix

4. Walk through the dry run on the example

5. State O(n) time and O(1) space

6. Mention edge cases: single element, all duplicates, no duplicates

Interview Tips

Interviewers often ask:

Why use Two Pointer instead of a HashSet?
What does the slow pointer represent at any point in time?
Why do you start fast at index 1?
Why return slow + 1 and not slow?
What if all elements are the same?
What if the array has no duplicates?
What happens to elements after index k?
Can this be extended to allow at most k duplicates?
What is the loop invariant?
What is the space complexity?

Be prepared to explain the invariant before writing code.

Approach Comparison

Approach	Time	Space	Notes
Brute Force (List)	O(n)	O(n)	Uses extra list — violates constraint
Two Pointer	O(n)	O(1)	Optimal — in-place, single pass

Unit Tests

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class RemoveDuplicatesTest {

    final RemoveDuplicates solution =
            new RemoveDuplicates();

    @Test
    void example1() {
        int[] nums = {1, 1, 2};
        int k = solution.removeDuplicates(nums);
        assertEquals(2, k);
        assertArrayEquals(
                new int[]{1, 2},
                Arrays.copyOfRange(nums, 0, k));
    }

    @Test
    void example2() {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int k = solution.removeDuplicates(nums);
        assertEquals(5, k);
        assertArrayEquals(
                new int[]{0, 1, 2, 3, 4},
                Arrays.copyOfRange(nums, 0, k));
    }

    @Test
    void singleElement() {
        int[] nums = {5};
        assertEquals(1,
                solution.removeDuplicates(nums));
    }

    @Test
    void allSame() {
        int[] nums = {3, 3, 3, 3};
        int k = solution.removeDuplicates(nums);
        assertEquals(1, k);
        assertEquals(3, nums[0]);
    }

    @Test
    void noDuplicates() {
        int[] nums = {1, 2, 3, 4, 5};
        int k = solution.removeDuplicates(nums);
        assertEquals(5, k);
        assertArrayEquals(
                new int[]{1, 2, 3, 4, 5},
                Arrays.copyOfRange(nums, 0, k));
    }

    @Test
    void negativeNumbers() {
        int[] nums = {-4, -4, -2, 0, 0, 1};
        int k = solution.removeDuplicates(nums);
        assertEquals(4, k);
        assertArrayEquals(
                new int[]{-4, -2, 0, 1},
                Arrays.copyOfRange(nums, 0, k));
    }

    @Test
    void twoElementsDuplicate() {
        int[] nums = {7, 7};
        assertEquals(1,
                solution.removeDuplicates(nums));
    }

    @Test
    void twoElementsUnique() {
        int[] nums = {3, 9};
        int k = solution.removeDuplicates(nums);
        assertEquals(2, k);
        assertArrayEquals(
                new int[]{3, 9},
                Arrays.copyOfRange(nums, 0, k));
    }

    @Test
    void duplicateAtEnd() {
        int[] nums = {1, 2, 3, 4, 4};
        int k = solution.removeDuplicates(nums);
        assertEquals(4, k);
        assertArrayEquals(
                new int[]{1, 2, 3, 4},
                Arrays.copyOfRange(nums, 0, k));
    }

}

Summary

Remove Duplicates from Sorted Array is the canonical problem for the in-place slow-fast Two Pointer write pattern. The brute-force approach using an extra list violates the O(1) space constraint. The Two Pointer approach achieves O(n) time and O(1) space by maintaining a slow pointer as the write position and a fast pointer as the read scanner. The sorted property guarantees all duplicates are adjacent, making a single forward pass sufficient. The invariant nums[0..slow] always holds the complete unique prefix. Mastering this pattern directly enables solving Remove Element, Remove Duplicates II, Move Zeroes, and many other in-place array problems.

Key Takeaways

Use a slow pointer as the write position and a fast pointer as the read scanner.
The slow pointer always marks the last confirmed unique element.
When nums[fast] != nums[slow], advance slow then write nums[fast] at the new slow position.
Return slow + 1, not slow.
The sorted property makes O(1) space possible — all duplicates are adjacent.
Never overwrite nums[slow] before advancing it.
Handle single-element arrays: the loop simply does not execute, and 1 is correctly returned.
Achieve O(n) time and O(1) space — a single pass with two index variables.
This pattern generalises to Remove Element, Move Zeroes, and Remove Duplicates II.

Remove Duplicates from Sorted Array (LeetCode

Introduction

Problem Statement

Formula

Example 1

Example 2

Example 3

Important Problem Guarantees

What Is the Slow-Fast Two Pointer Pattern?

Why Does the Sorted Array Matter?

Approach 1 — Brute Force (Extra Space)

Core Idea

Java Code — Brute Force

Brute Force Complexity

Why Brute Force Fails the Constraint

Approach 2 — Optimal Two Pointer Solution

Core Idea

Algorithm

Java Code — Optimal Solution

LeetCode-Style Implementation

Two Pointer Flow

Detailed Dry Run

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Iteration 5

Iteration 6

Iteration 7

Iteration 8

Iteration 9

Dry Run Table

Visual Pointer Movement

Why This Works

Correctness Proof

Loop Invariant

Complexity Analysis

Why the Complexity Is Not O(n²)

Why Use slow = 0 and fast = 1?

Production-Ready Implementation

Edge Cases

Single Element

All Same Elements

No Duplicates

Two Elements — Duplicate

Two Elements — Unique

Negative Numbers

All Unique with One Duplicate at End

Common Interview Mistakes

Mistake 1 — Starting slow and fast at the Same Index

Mistake 2 — Returning slow Instead of slow + 1

Mistake 3 — Writing Before Advancing slow

Mistake 4 — Using a HashSet (Ignores the Sorted Property)

Mistake 5 — Using a Second Array

Mistake 6 — Using nums.length - 1 as the Loop Bound

Mistake 7 — Not Handling a Single-Element Array

Mistake 8 — Confusing This with Remove Duplicates II

Follow-Up 1 — Allow Each Element at Most Twice (LeetCode #80)

Follow-Up 2 — Remove a Specific Value In-Place (LeetCode #27)

Follow-Up 3 — What If the Array Is Unsorted?

Follow-Up 4 — Return the Unique Elements as a New Array

Follow-Up 5 — Count Total Duplicates Removed

Production Applications

Real-World Example — Sorted Event Log Deduplication

Real-World Example — Sorted Merge Deduplication

Senior-Level Discussion — Why Is This Not O(n²)?

Senior-Level Discussion — Is This Stable?

Senior-Level Discussion — Can This Handle Very Large Arrays?

Interview Explanation

Interview Tips

Approach Comparison

Similar Problems

Unit Tests

Summary

Key Takeaways

Why Use `slow = 0` and `fast = 1`?