#26

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Remove Duplicates from Sorted Array

Learn how to remove duplicates from a sorted array in-place using two-pointer scanning while preserving element order.

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Single Pass

We use a variable $k$ to record the current length of the processed array. Initially, $k=0$ represents an empty array.

1

2

3

4

5

6

7

8

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for x in nums:
            if k == 0 or x != nums[k - 1]:
                nums[k] = x
                k += 1
        return k

Continue Practicing

#27 remove element #31 next permutation #18 4sum