AlgoViz
HomeArrays & Hashing

Remove duplicates from Sorted array

Easy

Two pointers: write index and read index

Problem

Given an integer array nums sorted in non-decreasing order, remove all duplicates in-place so that each unique element appears only once. Return the number of unique elements in the array. If the number of unique elements be k, then, Change the array nums such that the first k elements of nums contain the unique values in the order that they were present originally. The remaining elements, as well as the size of the array does not matter in terms of correctness. The driver code will assess correctness by printing and checking only the first k elements of the modified array. An array sorted in non-decreasing order is an array where every element to the right of an element is either equal to or greater in value than that element.

In simple words

Since it's sorted, copies sit together — keep a slow pointer that writes each new value once.

The idea

Because the array is sorted, duplicates are adjacent. Keep a write pointer for the end of the deduplicated prefix and a read pointer scanning ahead; copy an element forward only when it differs from the last one written.

The trick

  • The write pointer's final value is the length of the unique prefix.
  • Only compare against nums[write - 1], never scan backwards.
  • O(n) time, O(1) space — nothing is allocated.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0
3
3
5
6
0
1
2
3
4
5

Step 1 of 2. Here's the example — nums = [0, 0, 3, 3, 5, 6] Values: 0, 0, 3, 3, 5, 6.

1/2
Optimal
timeO(n)spaceO(1)
1k = 1                       // first element is always unique2for i in 1..n-1:3  if nums[i] != nums[k-1]:4    nums[k] = nums[i]; k++5return k                     // count of unique elements

Input

array
[0, 0, 3, 3, 5, 6]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 1, 2]
Output:
2
Explanation:
Unique values are 1 and 2 → length 2.

Example 2

Input:
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output:
5
Explanation:
Unique values 0,1,2,3,4 → length 5.

Example 3

Input:
nums = [1, 2, 3]
Output:
3
Explanation:
Nothing to remove; length stays 3.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in non-decreasing order.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.