Cleanup by Unequal Pairs

Medium

You get an array sorted_values in non-decreasing order. You may repeat this operation any number of times: pick two elements with **different** values and remove both from the array. The remaining elements keep their order. Return the smallest length the array can be reduced to.

Example 1

sorted_values=[1, 1, 2, 3, 3, 3] → 0

Remove the pairs (1, 3), (1, 3) and (2, 3) and the array is empty.

Example 2

sorted_values=[4, 4, 4, 4, 7] → 3

The 7 can go only together with one 4. The remaining three 4s are equal, so none of them can be removed.

Example 3

sorted_values=[2, 5, 9] → 1

Constraints

1 ≤ len(sorted_values) ≤ 10⁵
1 ≤ sorted_values[i] ≤ 10⁹
The array is sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Two Pointers Binary Search Counting

Similar problems

Spells Without Neighbors Medium Pairs With a Fixed Gap Medium Stick Triples That Form a Triangle Medium Jobs With a Cooldown Medium Best-Paid Gig for Each Worker Medium

Input

sorted_values=[1, 1, 2, 3, 3, 3]

Expected

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