Min deletions to avoid overlap in first k

Problem Statement

You are given an array of integers nums and an integer k. Your task is to modify the array such that all elements in the first k positions are distinct. To achieve this, you can only perform one operation: delete an element from the array.

Your goal is to find the minimum number of deletions required to satisfy the condition. If the array has fewer than k elements, treat the entire array as the prefix.

Function Signature

def min_deletions_to_unique_prefix(nums: list[int], k: int) -> int:

Constraints

• 1 <= len(nums) <= 10^5
• 1 <= k <= len(nums)
• 1 <= nums[i] <= 10^9

Examples

Example 1: Input: nums = [1, 2, 1, 3, 4], k = 3 Output: 1 Explanation: The prefix of length 3 is [1, 2, 1]. Removing the first 1 (or the second 1) results in a prefix of length 2 [2, 1], which is valid. Since the goal is the minimum deletions to ensure the first k slots (or remaining elements) are unique, removing one instance makes the prefix [2, 1, 3] which is valid.

Example 2: Input: nums = [1, 1, 1, 2, 2], k = 3 Output: 2 Explanation: To make the prefix unique, you must remove two 1s, leaving [1, 2, 2]. Then remove one 2, leaving [1, 2].