How to Solve Remove Duplicates from Sorted Array

This problem requires modifying a sorted array in-place to eliminate duplicate values while keeping the original order intact. The optimal solution uses a two-pointer approach where one pointer tracks the unique elements and the other scans through the array. Careful management of the invariant prevents overwriting and ensures correct counting of unique elements.

Problem Statement

Given a sorted integer array, modify it in-place so that each unique element appears exactly once and the relative order of elements remains the same. Return the total count of unique elements after duplicates have been removed.

You must achieve this with constant extra space and without using additional arrays. The array should be updated in such a way that the first k elements contain the unique elements, where k is the returned length, and the values beyond k are not considered.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }

Example 2

Input: nums = [1,1,2]

Output: 2, nums = [1,2,_]

Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 3

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

Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

Solution Approach

Two-Pointer Scanning

Initialize one pointer at the first element as the 'write' position and another pointer to iterate through the array. When a new unique element is found, write it at the 'write' position and increment the pointer, maintaining the invariant of all unique elements being contiguous.

Invariant Maintenance

Keep the invariant that all elements before the write pointer are unique. Each time a duplicate is skipped, the write pointer does not move, ensuring no overwrites. This guarantees that the array's beginning always reflects the current set of unique values.

Edge Cases Handling

Handle arrays with length 0 or 1 directly. Since the array is sorted, consecutive duplicates are adjacent, allowing simple comparison with the previous element to detect duplicates. No extra storage is required beyond the two pointers.

Complexity Analysis

Time complexity is O(n) since each element is processed once by the scanning pointer. Space complexity is O(1) as all operations are in-place without additional data structures.

What Interviewers Usually Probe

• Checks if you recognize the array is sorted and duplicates are consecutive.
• Watches whether you properly maintain the two-pointer invariant without extra memory.
• Assesses handling of edge cases like empty arrays or arrays with all identical elements.

Common Pitfalls or Variants

Common pitfalls

• Overwriting unique elements when the write pointer is incremented incorrectly.
• Using extra arrays, violating the in-place constraint.
• Failing to return the correct count of unique elements while only modifying the array partially.

Follow-up variants

• Remove duplicates allowing at most two occurrences instead of one, requiring adjusted invariant logic.
• Apply the same approach to a sorted linked list instead of an array.
• Handle arrays sorted in descending order, requiring reversed comparisons but same two-pointer logic.

How GhostInterview Helps

• Provides step-by-step guidance on setting up the two-pointer invariant for duplicate removal.
• Highlights subtle edge cases, ensuring accurate k calculation and array updates.
• Offers clear walkthroughs to avoid overwriting or miscounting unique elements during in-place modification.

Topic Pages

• Array
• Two Pointers

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the most efficient way to remove duplicates from a sorted array?

Using a two-pointer approach where one pointer tracks the position to write unique elements and the other scans for new values.

Do I need extra space to remove duplicates in this problem?

No, the problem requires in-place modification with O(1) extra space using the two-pointer invariant method.

How does the array being sorted simplify removing duplicates?

Since duplicates are consecutive, you only need to compare each element with the previous unique value to detect duplicates.

What should be returned after removing duplicates?

Return the number of unique elements, with the first k positions of the array containing these values in order.

Can this two-pointer pattern be adapted for allowing multiple occurrences?

Yes, by adjusting the write pointer logic and invariant, you can allow up to a fixed number of duplicates while scanning.