🐘 Keep Them Apart 🦙
Learn this problemProblem statement
You are given an array A of length n and an integer d >= 1. You may delete elements from the array from any position.
After deletions, consider the original indices of the remaining elements, i.e. their position in the input before any deletions. The array is valid if, for every value x, any two kept occurrences of x that appear at original positions i < j satisfy j - i >= d.
Your task is to compute the minimum number of deletions required to make the array valid.
Note: Distances are measured using the original indices from the input array, not the compressed indices after deletion.
Function
minimumDeletions(A: int[], d: int) → intExamples
Example 1
A = [1, 2, 2, 1]d = 3return = 1When x = 1, we have indices 1 and 4; we can keep both because 4 - 1 >= 3.
When x = 2, we have indices 2 and 3; we need to delete at least one element.
Therefore, the minimum number of deletions is 1.
Constraints
n <= 10^5,d <= 10^5, and0 < A[i] <= 10^9for all test cases.- Subtask A:
n <= 10,d <= 10, and0 < A[i] <= 10. - Subtask B:
n <= 100,d <= 100, and0 < A[i] <= 10. - Subtask C:
n <= 10^5,d <= 100, and0 < A[i] <= 10^9. - Subtask D:
n <= 10^5,d <= 10^5, and0 < A[i] <= 10^9.