Remove Duplicates from Sorted Array is a classic interview question that appears as problem 26 on LeetCode and similar platforms. It tests your ability to manipulate arrays in‑place while maintaining O(1) extra space, a skill that is valuable for optimizing memory usage in real‑world applications. In this guide we will walk through the problem statement, explore multiple solution strategies, analyze their complexity, and provide clear, ready‑to‑run code snippets in Python, Java, and C++. By the end you will not only know how to solve the task but also understand why the two‑pointer technique is the preferred approach.
Table of Contents
<a name="problem-statement"></a>
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 Most people skip this — try not to..
After removing the duplicates, return the number of unique elements k. It does not matter what values are set beyond the first k positions of the array.
Constraints
0 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 100numsis sorted in non‑decreasing order.
Example
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: k = 5, nums = [0,1,2,3,4,_,_,_,_,_]
(The underscores denote values that can be ignored.)
<a name="why-in-place-matters"></a>
Why In‑Place Matters
In many systems—especially embedded devices or memory‑constrained environments—allocating a new array proportional to the input size is undesirable. The in‑place requirement forces you to reuse the existing storage, achieving O(1) auxiliary space. Demonstrating this ability signals to interviewers that you understand both algorithmic efficiency and practical resource constraints Worth keeping that in mind..
Short version: it depends. Long version — keep reading Not complicated — just consistent..
<a name="approach-overview"></a>
Approach Overview
Because the input array is already sorted, duplicate values appear consecutively. This property enables a linear scan where we keep track of the position of the last unique element and overwrite the next duplicate with the next distinct value. Two main strategies emerge:
Easier said than done, but still worth knowing That's the part that actually makes a difference..
- Two‑pointer technique – uses a slow pointer for the location of the next unique element and a fast pointer to scan the array.
- Extra‑space method – builds a new list of unique elements (simple but violates the O(1) space constraint).
We will focus on the two‑pointer method because it satisfies both time and space optimality Not complicated — just consistent..
<a name="two-pointer-technique-optimal-solution"></a>
Two‑Pointer Technique (Optimal Solution)
Intuition
Maintain two indices:
- slow (
i) – points to the last confirmed unique element. - fast (
j) – iterates through the array looking for the next new value.
When nums[j] differs from nums[i], we have found a new unique element. We increment i and copy nums[j] to nums[i]. If they are equal, we simply advance j to skip the duplicate Worth knowing..
Algorithm
- If the array is empty, return
0. - Initialize
i = 0. - Loop
jfrom1ton‑1:- If
nums[j] != nums[i]:- Increment
i. - Set
nums[i] = nums[j].
- Increment
- If
- Return
i + 1as the count of unique elements.
Why It Works
Because the array is sorted, all duplicates of a value are grouped together. The slow pointer never overtakes the fast pointer; it only moves when a new value is encountered, guaranteeing that nums[0..i] contains each distinct value exactly once in original order.
<a name="alternative-using-extra-space"></a>
Alternative: Using Extra Space
A straightforward solution creates a new list, appends each element only if it differs from the last appended element, and finally copies the result back into nums. This runs in O(n) time and O(n) space. While easier to understand, it fails the in‑place requirement and is therefore not acceptable for the problem as stated Simple as that..
<a name="step-by-step-walkthrough"></a>
Step‑by‑Step Walkthrough
Let’s trace the algorithm on the example nums = [0,0,1,1,1,2,2,3,3,4].
| Step | j (fast) | nums[j] | i (slow) | nums[i] before | Action | nums after action | i |
|---|---|---|---|---|---|---|---|
| Init | – | – | 0 | 0 | – | [0,0,1,1,1,2,2,3,3,4] | 0 |
| 1 | 1 | 0 | 0 | 0 | equal → skip j | unchanged | 0 |
| 2 | 2 | 1 | 0 | 0 | not equal → i=1, nums[1]=1 | [0,1,1,1,1,2,2,3,3,4] | 1 |
| 3 | 3 | 1 | 1 | 1 | equal → skip j | unchanged | 1 |
| 4 | 4 | 1 | 1 | 1 | equal → skip j | unchanged | 1 |
| 5 | 5 |
| Step | j (fast) | nums[j] | i (slow) | nums[i] before | Action | nums after action | i |
|---|---|---|---|---|---|---|---|
| 5 | 5 | 2 | 1 | 1 | not equal → i=2, nums[2]=2 | [0,1,2,1,1,2,2,3,3,4] | 2 |
| 6 | 6 | 2 | 2 | 2 | equal → skip j | unchanged | 2 |
| 7 | 7 | 3 | 2 | 2 | not equal → i=3, nums[3]=3 | [0,1,2,3,1,2,2,3,3,4] | 3 |
| 8 | 8 | 3 | 3 | 3 | equal → skip j | unchanged | 3 |
| 9 | 9 | 4 | 3 | 3 | not equal → i=4, nums[4]=4 | [0,1,2,3,4,2,2,3,3,4] | 4 |
After the loop finishes, the slow pointer i ends at index 4.
The function returns i + 1 = 5, indicating that the array now contains five distinct values.
The first five positions of nums hold the unique elements in their original order:
This is where a lot of people lose the thread.
[0, 1, 2, 3, 4, …]
Any elements beyond index 4 are irrelevant for the result; they may contain leftover values but will be ignored by the caller.
Conclusion
The two‑pointer technique delivers an in‑place, O(n) time, O(1) space solution to the “Remove Duplicates from Sorted Array” problem. By leveraging the sorted property of the input, the algorithm efficiently collapses consecutive duplicates while preserving the relative order of the remaining elements. This approach not only meets the strict constraints of the problem but also exemplifies a clean, pointer‑driven mindset that is valuable across many array‑manipulation challenges.
Key Takeaways
- Sorted input is a powerful ally: Because duplicates are grouped together, we only need to compare adjacent elements to identify redundancy.
- Two pointers, one pass: The fast pointer scans the array while the slow pointer marks the boundary of the deduplicated region, eliminating the need for nested loops or extra storage.
- In-place modification: The algorithm writes results back into the original array, satisfying space constraints without sacrificing clarity or performance.
When to Reach for This Pattern
This two-pointer strategy extends beyond duplicate removal. Any problem that involves compacting an array based on a condition—such as filtering out specific values, partitioning elements, or merging sorted sequences—can benefit from the same fast/slow pointer dance. Recognizing the underlying structure allows you to adapt the technique to a wide range of coding challenges.
Final Thoughts
Mastering the two-pointer approach isn’t just about solving one LeetCode problem; it’s about cultivating a mindset for efficient array manipulation. Also, by keeping one pointer anchored to the result and another roaming ahead to explore possibilities, you gain a simple yet profound tool for writing clean, optimal code. Whether you're preparing for technical interviews or building production systems, this pattern is sure to serve you well.
