Problem: Remove Duplicates from Sorted Array

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. The relative order of the elements should be kept the same.

Return the number of unique elements in nums.

Approach: Same-Direction Pointers

We use two pointers moving in the same direction:

1. Read Pointer (read): Scans every element of the array.
2. Write Pointer (write): Tracks the index where the next unique element should be written.

Since the array is sorted, duplicates are always adjacent. We only "write" an element if it is different from the one before it.

Java Implementation

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;

    int write = 1; // Start from index 1

    for (int read = 1; read < nums.length; read++) {
        // If current element is different from the previous unique one
        if (nums[read] != nums[read - 1]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

Dry Run

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

Final Length: 3. Array Prefix: [1, 2, 3]

Complexity Discussion

• Time Complexity: $O(n)$. We pass through the array exactly once.
• Space Complexity: $O(1)$. We modify the array in-place.

Interview Tips

• Mention that this pattern is useful for "Compaction" or "In-place filtering."
• Be prepared to handle variations where you can keep at most two occurrences of each element.