Implement in-place duplicate removal

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.

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

Example 1

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

Explanation: Unique prefix becomes [1, 2]; new length is 2.

Example 2

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

Explanation: Distinct values [0,1,2,3,4]; new length is 5.

Hints

1. Keep one pointer for the position of the last unique value already written, and a second pointer that scans forward.
2. 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.
3. 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

Example 1

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

Explanation: Third 1 is dropped; result prefix [1,1,2,2,3]; length 5.

Example 2

Input: ([0, 0, 1, 1, 1, 1, 2, 3, 3],)
Output: 7

Explanation: 1 appears 4 times -> kept twice; result [0,0,1,1,2,3,3]; length 7.

Hints

1. Always keep the first two elements of any equal-value block, then drop the rest.
2. Compare the current candidate against the element two slots before the write pointer (nums[write - 2]) instead of one slot back.
3. 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].