Log inSign up
easyLeetCodeNot Started

Remove Duplicates from Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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. Then return *the number of unique elements in* nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things: - Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. - The remaining elements of nums are not important as well as the size of nums. - Return k.

Example 1 · Standard 3-element Array with Duplicates:

Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2, _]
Explanation: 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.

Example 2 · 10-element Array with Repeated Sequences:

Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.

Example 3 · Already Unique Array:

Input: nums = [1, 2, 3, 4, 5]
Output: 5, nums = [1, 2, 3, 4, 5]
Explanation: All elements are already unique. Function returns k = 5 and array remains unchanged.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Properties of sorted arrays (adjacent duplicates)
  • Two Pointers technique (slow write pointer, fast read pointer)
  • In-place array overwriting

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Slow/Fast Two Pointers in-place compaction idiom.
  • Leverage sorted monotonicity to detect duplicates through adjacent comparisons.
  • Generalize the write condition to support allowing up to k duplicate elements.
  • Implement clean, standalone solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Given a pre-sorted array containing duplicate elements.
  • Must filter out duplicates in-place and maintain original relative order.
  • Must achieve strictly O(1) auxiliary space.

Algorithmic Decision Tree:

  • Always use Slow/Fast Two Pointers: write pointer starts at index 1; read pointer advances from index 1. Write when nums[read] != nums[write - 1] (or nums[read] != nums[read - 1]).

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Hash Set Deduplication

Intuition

Insert all elements into an ordered set / hash set to eliminate duplicates, then write unique values back into nums.

Algorithm

  1. Insert all elements of nums into an ordered set uniqueSet.
  2. Let k = 0.
  3. For each value val in uniqueSet:
  4. nums[k++] = val.
  5. Return k.

Hash Set Deduplication

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 1, 1, 2]
Current operationSTEP 1 OF 6
Phase 1 — Insert First Element: nums[0] is 0
Visual state
Values and pointers at this exact step
array
S
0
0
1
1
2
0
↑ i = 0
1
2
3
4
Variables at this step
Index
0
Value
0
seen
{ 0 }
Check / comparison
0 not in seen -> insert.
Decision / next transition
seen = { 0 }.
Why this step matters

Phase 1 — Insert First Element: nums[0] is 0. Insert into LinkedHashSet: seen = { 0 }.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <set>
3#include <vector>
4using namespace std;
5
6// Brute Force: Set deduplication (O(N) space)
7int removeDuplicates(vector<int>& nums) {
8 set<int> uniqueSet(nums.begin(), nums.end());
9 int k = 0;
10 for (int val : uniqueSet) {
11 nums[k++] = val;
12 }
13 return k;
14}
15
16int main() {
17 vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
18 int k = removeDuplicates(nums);
19
20 cout << "k = " << k << ", nums = [";
21 for (int i = 0; i < k; i++) {
22 cout << nums[i] << (i + 1 < k ? ", " : "");
23 }
24 cout << "]" << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Hash Set Deduplication.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Hash Set Deduplication.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Optimal — Slow & Fast Two Pointers (In-Place O(1) Space)

Intuition

Place write pointer at 1. Iterate read pointer from 1 to N-1; whenever nums[read] != nums[read - 1], copy nums[read] to nums[write] and advance write by 1.

Algorithm

  1. If nums.length == 0, return 0.
  2. Initialize write = 1.
  3. Loop read from 1 to nums.length - 1:
  4. If nums[read] != nums[read - 1]:
  5. nums[write] = nums[read].
  6. write++.
  7. Return write.

Slow & Fast Two Pointers (In-Place O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 1, 1, 2]
Current operationSTEP 1 OF 6
Phase 1 — Setup Pointers: slow = 0 holds the last known unique element
Visual state
Values and pointers at this exact step
array
S
0
0
1
1
2
0
↑ slow=0
1
↑ fast=1
2
3
4
Variables at this step
slow
0
fast
1
nums
[0, 0, 1, 1, 2]
Check / comparison
slow = 0 (val 0), fast = 1 (val 0).
Decision / next transition
nums[fast] == nums[slow] (0 == 0). Duplicate! Advance fast to 2.
Why this step matters

Phase 1 — Setup Pointers: slow = 0 holds the last known unique element. fast = 1 scans ahead for the next distinct number.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal: Slow & Fast Two Pointers (O(N) time, O(1) space)
6int removeDuplicates(vector<int>& nums) {
7 if (nums.empty()) return 0;
8
9 int write = 1;
10 for (size_t read = 1; read < nums.size(); read++) {
11 if (nums[read] != nums[read - 1]) {
12 nums[write] = nums[read];
13 write++;
14 }
15 }
16 return write;
17}
18
19int main() {
20 vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
21 int k = removeDuplicates(nums);
22
23 cout << "k = " << k << ", nums = [";
24 for (int i = 0; i < k; i++) {
25 cout << nums[i] << (i + 1 < k ? ", " : "");
26 }
27 cout << "]" << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Optimal — Slow & Fast Two Pointers (In-Place O(1) Space).
  • Space complexity: O(N) — Space complexity for Approach 2: Optimal — Slow & Fast Two Pointers (In-Place O(1) Space).

3. Better — Generalized k-Duplicates Template

Intuition

Compare with nums[write - k_allowed] to cleanly generalize for allowing up to k duplicates (e.g. Remove Duplicates II).

Algorithm

  1. Let k_allowed = 1.
  2. Initialize write = 0.
  3. Loop num through nums:
  4. If write < k_allowed || num != nums[write - k_allowed]:
  5. nums[write] = num.
  6. write++.
  7. Return write.

Generalized k-Duplicates Template

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 1, 1, 2]
Current operationSTEP 1 OF 6
Phase 1 — Invariant Rule: For at most 1 copy, check if current element x > nums[slow - 1]
Visual state
Values and pointers at this exact step
array
S
0
0
1
1
2
0
1
↑ slow=1
2
3
4
Variables at this step
slow
1
nums[slow-1]
0
Check / comparison
Base element nums[0]=0 already in place. slow = 1.
Decision / next transition
Begin loop from index 1.
Why this step matters

Phase 1 — Invariant Rule: For at most 1 copy, check if current element x > nums[slow - 1]. Initialize slow = 1 for base element.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Generalized template allowing up to k_allowed duplicates
6int removeDuplicates(vector<int>& nums) {
7 int k_allowed = 1;
8 int write = 0;
9
10 for (int num : nums) {
11 if (write < k_allowed || num != nums[write - k_allowed]) {
12 nums[write] = num;
13 write++;
14 }
15 }
16 return write;
17}
18
19int main() {
20 vector<int> nums = {1, 1, 2};
21 int k = removeDuplicates(nums);
22 cout << "k = " << k << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Better — Generalized k-Duplicates Template.
  • Space complexity: O(1) — Space complexity for Approach 3: Better — Generalized k-Duplicates Template.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Hash Set DeduplicationO(N)O(N)Very intuitive, works even if array is unsorted.Baseline only.
2.Slow & Fast Two PointersO(N)O(1)Optimal single pass, strictly O(1) memory, clean 5-line implementation.Optimal gold standard.
3.Generalized k-DuplicatesOptimalO(N)O(1)Versatile; directly solves both Remove Duplicates I and II.Top-tier interview demonstration.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All Elements Identical — Input: nums = [1, 1, 1, 1], Expected: 1, nums = [1] — Only 1 unique element exists; write remains 1.
  • All Elements Already Distinct — Input: nums = [1, 2, 3, 4], Expected: 4, nums = [1, 2, 3, 4] — No elements removed; returns original length 4.
  • Single Element Array — Input: nums = [7], Expected: 1, nums = [7] — Loop 1..0 does not execute; returns 1 immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Remove Duplicates from Sorted Array?

2.Why is the brute force approach suboptimal for large inputs in Remove Duplicates from Sorted Array?

3.Which data structure or technique enables the optimal solution for Remove Duplicates from Sorted Array?

Back to DSA Sheet