Skip to main content

4. Remove Duplicates from Sorted Array

easyAsked at PayPal

Remove duplicates from a sorted array in-place and return the new length. PayPal asks this to test the two-pointer reflex — the same technique they apply when deduplicating idempotency keys in a sorted append-only ledger.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • LeetCode Discuss (2025-10)— PayPal early-career screen, in-place constraint emphasized.

Problem

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.

Constraints

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

Examples

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.

Example 2

Input
nums = [0,0,1,1,1,2,2,3,3,4]
Output
5, nums = [0,1,2,3,4,_,_,_,_,_]

Approaches

1. Set-based copy out

Push to a Set, then write back into nums. Returns size.

Time
O(n)
Space
O(n)
function removeDuplicates(nums) {
  const set = new Set(nums);
  const arr = [...set];
  for (let i = 0; i < arr.length; i++) nums[i] = arr[i];
  return arr.length;
}

Tradeoff: Uses O(n) extra space and ignores that input is already sorted.

2. Two-pointer in-place (optimal)

Write pointer k starts at 1. Read pointer i scans. If nums[i] != nums[i-1], write nums[i] to nums[k] and advance k.

Time
O(n)
Space
O(1)
function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let k = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i - 1]) {
      nums[k++] = nums[i];
    }
  }
  return k;
}

Tradeoff: O(1) space — exactly what PayPal needs for stream-dedup of idempotency keys in a fixed-size ring buffer.

PayPal-specific tips

PayPal interviewers care about in-place semantics — the question is engineered to weed out candidates who don't recognize 'sorted' as a hint. Bonus signal: mention that for idempotency key dedup, you'd combine this with a TTL bloom filter to bound space.

Common mistakes

  • Comparing nums[i] to nums[k-1] vs nums[i-1] — both work for this problem but differ in 'remove duplicates II' (allow up to 2 copies).
  • Returning the array instead of the length k.
  • Modifying the array length (e.g., splice) — overcomplicates and ruins O(1) space.

Follow-up questions

An interviewer at PayPal may pivot to one of these next:

  • Allow each element up to twice (LC 80).
  • Remove a specific value, not duplicates (LC 27).
  • Dedup an unsorted array in-place.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does the sortedness matter?

Duplicates are adjacent. So you only compare against the previous kept element, not all previous elements — that's the O(n) vs O(n^2) difference.

What if nums is empty?

Return 0. Always guard with an explicit length check before reading nums[0].

Practice these live with InterviewChamp.AI

Drill Remove Duplicates from Sorted Array and other PayPal interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →