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
PreviewInitialize a 'write' pointer at index 1. Iterate 'read' from index 1 to the end…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
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.
Return the Length of the Unique Elements Subarray
To return the count of unique elements found, which is the position of the 'write' pointer after processing.
2 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 6 lines available on Pro.
Test Your Understanding
Why does comparing nums[read] with nums[write - 1] guarantee that only unique elements are written?
See the answer with Pro.
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