Min deletions to avoid overlap in first k

You are given two integer arrays list1 and list2 and an integer k.

You may delete elements from list2 (deletions can be at any positions). The relative order of the remaining elements of list2 must stay the same.

After deletions, list2 must still contain at least k elements. Let:

• A be the first k elements of list1 (i.e., list1[0..k-1] ).
• B be the first k elements of the modified list2 .

Requirement: No value may appear in both A and B (i.e., the sets of values used in the first k positions must be disjoint).

Return the minimum number of deletions needed in list2 to satisfy the requirement. If it is impossible (i.e., you cannot obtain k valid elements for B), return -1.

Clarifications

• Duplicates may exist in either array.
• The constraint is about value overlap between A and B ; duplicates inside B itself are allowed unless they also appear in A .

Example

• list1 = [5,1,2,9] , list2 = [1,3,5,4,3] , k = 3
  • A = {5,1,2} .
  • Delete 1 and 5 from list2 , remaining [3,4,3] → B = [3,4,3] has no overlap with A .
  • Answer: 2 deletions.

Constraints (reasonable interview scale)

• 1 <= k <= min(len(list1), len(list2))
• len(list1), len(list2) <= 2 * 10^5