Implement in-place duplicate removal
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a non-decreasing array of integers, overwrite it in-place so that each distinct value appears exactly once while preserving the order of the unique values. Return the new length of the compressed prefix and justify that your algorithm uses O(
1) extra space and runs in O(n) time. Follow-up: modify your solution so that each value may appear at most twice, and explain the changes.
Quick Answer: This question evaluates proficiency in in-place array manipulation, handling duplicates in sorted sequences, and formal reasoning about space and time complexity.
Remove Duplicates from Sorted Array (In-Place)
Given a non-decreasing (sorted ascending) array of integers `nums`, overwrite it in place so that each distinct value appears exactly once while preserving the relative order of the unique values. Return the new length `k` of the compressed prefix; the first `k` elements of `nums` must hold the distinct values in their original sorted order. Elements beyond index `k` do not matter.
Your algorithm must use O(1) extra space and run in O(n) time. Use a two-pointer technique: a `write` pointer marks the next slot to fill, and a `read` pointer scans the array; only when the value at `read` differs from the last written value do you copy it forward and advance `write`.
Constraints
- 0 <= len(nums) <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order
- Must modify nums in place with O(1) extra memory
Examples
Input: ([1, 1, 2],)
Expected Output: 2
Explanation: Unique prefix becomes [1, 2]; new length is 2.
Input: ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4],)
Expected Output: 5
Explanation: Distinct values [0,1,2,3,4]; new length is 5.
Hints
- Keep one pointer for the position of the last unique value already written, and a second pointer that scans forward.
- Because the array is sorted, all copies of a value are contiguous — you only need to compare each element with the most recently written one.
- When nums[read] differs from nums[write - 1], write it at index `write` and increment `write`.
Remove Duplicates from Sorted Array II — At Most Twice (In-Place)
Follow-up to the previous problem. Given a non-decreasing array of integers `nums`, overwrite it in place so that each distinct value appears at most twice while preserving order. Return the new length `k`; the first `k` elements must hold the result. The algorithm must still run in O(n) time and use O(1) extra space.
The key change from the 'each value once' version: instead of comparing the candidate against the last written element (`nums[write - 1]`), compare it against the element two positions back (`nums[write - 2]`). If the candidate equals `nums[write - 2]`, that value would appear three times, so skip it; otherwise keep it. The first two elements of any block are always kept (guarded by `write < 2`). This generalizes to 'at most k times' by comparing against `nums[write - k]`.
Constraints
- 0 <= len(nums) <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order
- Each distinct value may appear at most twice in the result
- Must modify nums in place with O(1) extra memory
Examples
Input: ([1, 1, 1, 2, 2, 3],)
Expected Output: 5
Explanation: Third 1 is dropped; result prefix [1,1,2,2,3]; length 5.
Input: ([0, 0, 1, 1, 1, 1, 2, 3, 3],)
Expected Output: 7
Explanation: 1 appears 4 times -> kept twice; result [0,0,1,1,2,3,3]; length 7.
Hints
- Always keep the first two elements of any equal-value block, then drop the rest.
- Compare the current candidate against the element two slots before the write pointer (nums[write - 2]) instead of one slot back.
- Guard with `write < 2` so the first two writes are unconditional; this pattern generalizes to 'at most k copies' by comparing with nums[write - k].