CC

CoreCoding

Built for depth, not noise.

Back to DSA track

Remove Duplicates from Sorted Array

Compress a sorted array in place so each unique value appears once, then return the new length.

Two Pointers
EASY

Problem intuition

  • Because duplicates are adjacent in a sorted array, you only need to track the next slot for a new unique value.
  • A non-optimal solution can still be correct by writing into a helper structure first, but the clean version reuses the array in place.

Solution

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Copy uniques into a helper list

  • Scan once, store unique values in a helper list, then copy them back.
  • This is correct, but it wastes extra space.
  • Time complexity: O(n)
    • you make one pass to collect unique values and another pass to write them back, both linear.
  • Space complexity: O(n)
    • the helper list can grow to hold every element when all values are unique.

Solution 2

Read pointer and write pointer

  • Keep one pointer on the next write position.
  • Copy each newly discovered value into place.
  • Time complexity: O(n)
    • the read pointer scans the array once while the write pointer only moves forward.
  • Space complexity: O(1)
    • the work is done in place using just two pointer variables.