How do you approach Remove Duplicates from Sorted Array?

Use two pointers: one for the current position to write, one for scanning.

What is the time complexity of Remove Duplicates from Sorted Array?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Remove Duplicates from Sorted Array?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Remove Duplicates from Sorted Array

EasyAlgorithms

Description

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. - Return `k`.

Example 1

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.

Example 2

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 being 0, 1, 2, 3, and 4 respectively.

Constraints

- 1 <= nums.length <= 3 * 10^4 - -100 <= nums[i] <= 100 - nums is sorted in non-decreasing order.

Remove Duplicates from Sorted Array: approach, complexity and pitfalls

An easy two pointers problem, graded against 6 test cases (3 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

More Two Pointersproblems →

If you are stuck

Show the 3-step hint ladder

Use two pointers: one for the current position to write, one for scanning.
Since the array is sorted, duplicates are adjacent.
Only write when you find a new unique element.

The optimal approach

Show the approach: Two Pointers

Use a slow pointer to track the position for the next unique element, and a fast pointer to scan through the array.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.