You are given an integer array nums of length n and an integer k.
For each index i, define the delayed count as the number of indices j such that:
i + k < j <= n - 1, andnums[j] == nums[i]Return an array ans where ans[i] is the delayed count of index i.
Example 1:
Input: nums = [1,2,1,1], k = 1
Output: [2,0,0,0]
Explanation:
i |
nums[i] |
possible j |
nums[j] |
satisfyingnums[j] == nums[i] |
ans[i] |
|---|---|---|---|---|---|
| 0 | 1 | [2, 3] | [1, 1] | [2, 3] | 2 |
| 1 | 2 | [3] | [1] | [] | 0 |
| 2 | 1 | [] | [] | [] | 0 |
| 3 | 1 | [] | [] | [] | 0 |
Thus, ans = [2, 0, 0, 0].
Example 2:
Input: nums = [3,1,3,1], k = 0
Output: [1,1,0,0]
Explanation:
i |
nums[i] |
possible j |
nums[j] |
satisfyingnums[j] == nums[i] |
ans[i] |
|---|---|---|---|---|---|
| 0 | 3 | [1, 2, 3] | [1, 3, 1] | [2] | 1 |
| 1 | 1 | [2, 3] | [3, 1] | [3] | 1 |
| 2 | 3 | [3] | [1] | [] | 0 |
| 3 | 1 | [] | [] | [] | 0 |
Thus, ans = [1, 1, 0, 0].
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1050 <= k <= n - 1We can use a hash table cnt to record the number of occurrences of each number within the index range (i + k, n - 1]. We enumerate index i in reverse order starting from index n - k - 2. During the enumeration, we first add the number at index i + k + 1 to the hash table cnt, then assign the value of cnt[nums[i]] to the answer array ans[i].
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.
Java
C++
Go
TypeScript
Rust
Practice Delayed Count of Equal Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor