FastPrepMaximum Distinct Values After Cross-Array Swaps

Maximum Distinct Values After Cross-Array Swaps

Scale AI logoScale AI● EasyNEW GRADOA
Learn

Problem statement

You are given integer arrays a and b and an integer k.

In one operation, choose any index in a and any index in b, then swap those two elements. Return the maximum possible number of distinct values in a after at most k operations.

Function

maximumDistinctAfterSwaps(a: int[], b: int[], k: int) → int

Examples

Example 1

a = [2,3,3,2,2]b = [1,3,2,4,1]k = 4return = 4

Replace duplicate copies in a with the new values 1 and 4.

Example 2

a = [1,1,2,2]b = [3,4,1,5]k = 2return = 4

Swap duplicate copies for 3 and 4.

Example 3

a = [1,2,3]b = [4,5]k = 2return = 3

a is already fully distinct; replacing a unique value cannot increase its count.

Constraints

  • 1 <= a.length, b.length <= 200000.
  • 0 <= k <= 200000.
  • -1000000000 <= a[i], b[i] <= 1000000000.

More Scale AI problems

See Scale AI hiring insights
public int maximumDistinctAfterSwaps(int[] a, int[] b, int k) {
    // write your code here
}
a[2,3,3,2,2]
b[1,3,2,4,1]
k4
expected4
Checking account…