Skip to main content

64. Remove Duplicates from Sorted Array II

mediumAsked at Ola

Allow each unique element to appear at most twice in a sorted array, in-place.

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

Problem

Given a sorted integer array nums, remove some duplicates in-place such that each unique element appears at most twice. Return the new length and place the resulting values in the first part of nums.

Constraints

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

Examples

Example 1

Input
nums = [1,1,1,2,2,3]
Output
5, [1,1,2,2,3]

Example 2

Input
nums = [0,0,1,1,1,1,2,3,3]
Output
7, [0,0,1,1,2,3,3]

Approaches

1. Counting filter

Walk; track per-value count; write only if count <= 2.

Time
O(n)
Space
O(n)
const cnt = new Map();
let k = 0;
for (const x of nums) {
  const c = (cnt.get(x)||0) + 1;
  cnt.set(x, c);
  if (c <= 2) nums[k++] = x;
}
return k;

Tradeoff:

2. Two-pointer write at k-2

Allow nums[i] only when k < 2 or nums[i] != nums[k-2]; works because input is sorted.

Time
O(n)
Space
O(1)
function removeDuplicates(nums) {
  let k = 0;
  for (const x of nums) {
    if (k < 2 || nums[k-2] !== x) nums[k++] = x;
  }
  return k;
}

Tradeoff:

Ola-specific tips

Ola asks this to test in-place index hygiene on sorted streams; tie it to capping at most two repeated heartbeats per driver before alerting.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →