Remove Duplicates from Sorted Array
Problem
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space for another array; modify the input array in-place with O(1) extra memory.
- 0 ≤ nums.length ≤ 3 * 10⁴
- −10⁴ ≤ nums[i] ≤ 10⁴
- nums is sorted in non-decreasing order
Example
nums = [0,0,1,1,1,2,2,3,3,4]5The algorithm uses two pointers. The read pointer scans the array, and the write pointer marks where the next unique element should be placed. Start with nums = [0,0,1,1,1,2,2,3,3,4]. Because the array is sorted, duplicates always appear next to each other. This means we only need to compare each value with the last unique value we kept. write starts at 1 because the first element is always unique. At this point nums[:1] = [0], which is the current unique region. read = 1 → nums[1] = 0. The last unique value is nums[write - 1] = nums[0] = 0. Since they are equal, this is a duplicate, so we skip it. read = 2 → nums[2] = 1. The last unique value is 0. Because the values differ, this is a new unique element. We copy it to nums[1] and move write to 2. Now nums[:2] = [0,1]. read = 3 and read = 4 → both values are 1. The last unique value is nums[1] = 1. Since they are duplicates, we skip them. read = 5 → nums[5] = 2. The last unique value is 1. This is a new value, so we write it to nums[2] and move write to 3. Now nums[:3] = [0,1,2]. read = 6 → value is 2. Duplicate, skip. read = 7 → value is 3. Last unique value is 2, so this is a new unique element. Write it to nums[3] and move write to 4. Now nums[:4] = [0,1,2,3]. read = 8 → value is 3. Duplicate, skip. read = 9 → value is 4. Last unique value is 3, so this is new. Write it to nums[4] and move write to 5. After the scan finishes, the first five positions contain the unique values [0,1,2,3,4]. Because write now equals 5, we return 5.
Approach
Straightforward Solution
A naive approach would be to create a new array and copy unique elements, which uses O(n) extra space and violates the in-place constraint.
Core Observation
Because the array is sorted, duplicates appear consecutively. This means that scanning linearly and comparing adjacent elements is sufficient to identify duplicates.
Path to Optimal
The key insight is to use two pointers: one to read through the array and one to write unique elements. By comparing the current read element with the last written unique element, duplicates can be skipped, and unique elements can be compacted at the front of the array.
Optimal Approach
Initialize a 'write' pointer at index 1. Iterate 'read' from index 1 to the end. For each 'read', if nums[read] differs from nums[write - 1], assign nums[write] = nums[read] and increment 'write'. After the loop, 'write' represents the length of the unique elements subarray. This approach runs in O(n) time and O(1) space.
Time
O(n)
The algorithm makes a single pass through the array with the 'read' pointer, performing constant-time comparisons and assignments.
Space
O(1)
Only two integer pointers are used regardless of input size, and the input array is modified in-place without additional data structures.
Pattern Spotlight
Two Pointers (In-Place Array Modification)
When removing duplicates or partitioning a sorted array in-place, use one pointer to scan and another to track the position of the next unique element, ensuring O(1) space and linear time by overwriting duplicates as they are found.
Solution
| 1 | class Solution: |
| 2 | def removeDuplicates(self, nums: List[int]) -> int: |
| 3 | |
| 4 | write = 1 |
| 5 | |
| 6 | for read in range(1, len(nums)): |
| 7 | |
| 8 | if nums[read] != nums[write - 1]: |
| 9 | nums[write] = nums[read] |
| 10 | write += 1 |
| 11 | |
| 12 | return write |
Step-by-Step Solution
Initialize Write Pointer to Track Unique Elements
| 4 | write = 1 |
Objective
To set the starting position for writing unique elements, assuming the first element is always unique.
Key Insight
Since the array is sorted, the first element is always unique and can be considered the initial unique element. Starting 'write' at 1 means the next unique element found will be written at this position, compacting the array in-place.
Interview Quick-Check
Core Logic
Initializing 'write' to 1 assumes the first element is unique and sets the stage for overwriting duplicates starting from the second position.
Common Pitfalls & Bugs
Starting 'write' at 0 would overwrite the first element unnecessarily and complicate the logic.
Scan Array with Read Pointer and Overwrite Duplicates
| 6 | for read in range(1, len(nums)): |
| 8 | if nums[read] != nums[write - 1]: |
| 9 | nums[write] = nums[read] |
| 10 | write += 1 |
Objective
To iterate through the array, identify unique elements by comparing with the last written unique element, and overwrite duplicates by writing unique elements at the 'write' pointer.
Key Insight
The sorted property ensures duplicates are adjacent. By comparing nums[read] with nums[write - 1], the algorithm detects when a new unique element appears. Writing this element at 'write' compacts the array, and incrementing 'write' prepares for the next unique element. This in-place overwrite avoids extra space and maintains order.
Interview Quick-Check
Core Logic
The key operation is comparing nums[read] with nums[write - 1] to detect new unique elements and writing them at 'write' to overwrite duplicates.
State & Boundaries
The loop runs from index 1 to the end, ensuring all elements are checked against the last unique element.
Common Pitfalls & Bugs
Failing to increment 'write' after writing a unique element would cause overwriting and loss of data.
Return the Length of the Unique Elements Subarray
| 12 | return write |
Objective
To return the count of unique elements found, which is the position of the 'write' pointer after processing.
Key Insight
Because 'write' tracks the next position to write a unique element, it also represents the total number of unique elements after the loop completes. Returning 'write' gives the new length of the array without duplicates.
Interview Quick-Check
Core Logic
Returning 'write' correctly reports the count of unique elements, as it points to the index after the last unique element.
Line Analysis
This solution has 1 Critical line interviewers watch for.
if nums[read] != nums[write - 1]:Check if the current 'read' element differs from the last unique element at 'write - 1'.
This comparison leverages the sorted property to detect new unique elements by comparing with the last written unique element, ensuring duplicates are skipped.
write = 1Initialize the 'write' pointer at index 1 to track the position for the next unique element.
Starting 'write' at 1 assumes the first element is unique and sets the baseline for overwriting duplicates, enabling in-place compaction without losing the first element.
nums[write] = nums[read]Overwrite the element at 'write' with the new unique element found at 'read'.
Writing the unique element at 'write' compacts the array in-place, replacing duplicates and preserving the order of unique elements.
write += 1Increment 'write' to prepare for the next unique element.
Incrementing 'write' advances the position for the next unique element, preventing overwriting and maintaining the compacted array structure.
return writeReturn 'write' as the length of the array containing unique elements.
Because 'write' points to the index after the last unique element, it correctly represents the count of unique elements in the modified array.
for read in range(1, len(nums)):Iterate 'read' pointer from index 1 to the end of the array.
This loop scans every element after the first, ensuring all potential duplicates are checked against the last unique element.
Test Your Understanding
Why does comparing nums[read] with nums[write - 1] guarantee that only unique elements are written?
Because 'write - 1' always points to the last unique element written, any difference means the current 'read' element is a new unique value that should be recorded; duplicates appear consecutively due to sorting, so this comparison suffices.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Remove Duplicates from Sorted Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove Duplicates from Sorted Array drill