At Most Two Copies

Medium

The array values is sorted in non-decreasing order. Keep every value at most twice by dropping the extra copies right inside this array, without making a copy. Let k be the number of elements left after the cleanup. Modify values so that its first k elements hold the result in the original order; whatever follows does not matter. Return k. Try to do it in one pass with O(1) extra memory.

Example 1

values=[3, 3, 3, 3, 8, 9, 9] → 5

Two of the four 3s stay. The function returns 5 and the array starts with [3, 3, 8, 9, 9, …].

Example 2

values=[-4, 0, 0, 2] → 4

No value occurs more than twice, so nothing changes: the answer is 4.

Example 3

values=[6, 6, 6] → 2

Constraints

1 ≤ len(values) ≤ 3·10⁴
-10⁴ ≤ values[i] ≤ 10⁴
values is sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers

Similar problems

Two Boards Holding Water Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Next Arrangement in Order Medium

Input

values=[3, 3, 3, 3, 8, 9, 9]

Expected

Run checks the first 3 tests in your browser. Submit checks all 131 tests on the server, hidden ones included.