DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Remove Duplicates from Sorted Array

easyTwo pointers

Problem statement

You are given a list nums sorted in non-decreasing order. Rearrange it in place so that each distinct value appears once at the front, in the original order. Return k, the number of distinct values. Only the first k positions are checked; whatever is left after them does not matter.

Examples

Example 1

Input: nums = [2, 2, 3, 5, 5, 5, 9]

Output: 4, nums starts with [2, 3, 5, 9]

Explanation: There are 4 distinct values. Positions 4 to 6 can hold anything.

Example 2

Input: nums = [7]

Output: 1, nums starts with [7]

Explanation: A single value is already unique.

Hints

Approach

Use two pointers. k is the length of the de-duplicated prefix. Scan with i, and whenever nums[i] differs from the last kept value nums[k - 1], it is new: copy it to nums[k] and grow the prefix.

  1. If the list is empty, return 0.
  2. Set k = 1 (the first value is always kept).
  3. For i from 1 to the end: if nums[i] != nums[k - 1], set nums[k] = nums[i] and increase k.
  4. Return k.

This relies on the list being sorted. On an unsorted list, a repeat that is not adjacent would slip through.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
if not nums:
return 0
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return k

Follow-up questions

  • Allow each value to appear at most twice.
  • The list is not sorted. What is the best you can do while keeping first-seen order?

Frequently asked questions

Both work for this problem, because the list is sorted. Comparing with the last kept value generalises better: change the condition to nums[i] != nums[k - 2] and the same loop keeps up to two copies of each value.

Arrays in many languages have a fixed size, so the problem asks for the new logical length instead. In Python you could del nums[k:] afterwards if you really want a shorter list.

It is exactly what uniq does on sorted input, and why shell pipelines use sort | uniq: once equal lines are adjacent, removing repeats needs only one pass and no memory of earlier lines.