How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

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.

Input: ([],)

Expected Output: 0

Explanation: Empty array has no unique values; length 0.

Input: ([5],)

Expected Output: 1

Explanation: Single element is already unique; length 1.

Input: ([2, 2, 2, 2],)

Expected Output: 1

Explanation: All identical collapse to a single 2; length 1.

Input: ([-3, -3, -1, 0, 0, 7],)

Expected Output: 4

Explanation: Distinct values [-3,-1,0,7]; length 4 (handles negatives).

Input: ([1, 2, 3, 4, 5],)

Expected Output: 5

Explanation: Already all distinct; length unchanged at 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.

Input: ([],)

Expected Output: 0

Explanation: Empty array; length 0.

Input: ([4],)

Expected Output: 1

Explanation: Single element kept; length 1.

Input: ([2, 2, 2, 2],)

Expected Output: 2

Explanation: Four 2s collapse to two; length 2.

Input: ([1, 2, 3],)

Expected Output: 3

Explanation: All distinct, none exceeds twice; length 3.

Input: ([-1, -1, -1, 0, 0],)

Expected Output: 4

Explanation: Third -1 dropped; result [-1,-1,0,0]; length 4 (handles negatives).

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].

Quick Overview

This question evaluates proficiency in in-place array manipulation, handling duplicates in sorted sequences, and formal reasoning about space and time complexity.