Min deletions to avoid overlap in first k
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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`
Quick Answer: This question evaluates array and sequence manipulation skills, set-based reasoning about value overlap, and the ability to compute minimal edits while preserving relative order constraints.
You are given two integer arrays `list1` and `list2` and an integer `k`. You may delete any elements from `list2`, but the relative order of the remaining elements must stay the same. After deletions, `list2` must still contain at least `k` elements. Let `forbidden` be the set of values appearing in the first `k` elements of `list1`. Your goal is to make sure that every one of the first `k` elements of the modified `list2` is not in `forbidden`. Return the minimum number of deletions needed. If it is impossible to obtain `k` valid elements for the front of `list2`, return `-1`.
Constraints
- 1 <= k <= min(len(list1), len(list2))
- len(list1), len(list2) <= 2 * 10^5
- Array values may be negative and may contain duplicates
Examples
Input: ([1, 2, 3], [2, 1, 4, 5], 2)
Expected Output: 2
Explanation: The forbidden set is {1, 2}. In `list2`, the first two values must be deleted, then 4 and 5 become the first two remaining elements.