Most Distinct Values from Two Halves

Medium

You are given two arrays first and second of the same even length n. Remove exactly n / 2 elements from each array, so that exactly half of each remains. Then all remaining elements of both arrays are pooled together. Return the largest possible number of distinct values in that pool.

Example 1

first=[4, 4, 7, 7], second=[7, 7, 7, 9] → 3

Keep [4, 7] from first and [7, 9] from second. Together they give three distinct numbers: 4, 7 and 9.

Example 2

first=[5, 5, 5, 5, 5, 5], second=[5, 5, 6, 6, 8, 8] → 3

first holds only fives, while second can keep 6 and 8. That makes 3 distinct numbers.

Example 3

first=[1, 2, 3, 4], second=[1, 2, 3, 4] → 4

Keep 1 and 2 in the first array and 3 and 4 in the second, and all four numbers survive.

Constraints

1 ≤ n ≤ 2·10⁴ and n is even
first.length = second.length = n
1 ≤ first[i], second[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table

Similar problems

Jobs With a Cooldown Medium Sorted Into Runs of Three Medium Fewest Guests by Lanyard Color Medium Deal Into Consecutive Sets Medium Pair Each Number With Its Double Medium

Input

first=[4, 4, 7, 7], second=[7, 7, 7, 9]

Expected

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