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 - 1Problem Overview: You are given an integer array and need to count how many pairs of indices (i, j) satisfy i < j and nums[i] == nums[j]. Each element contributes to the total based on how many identical values appear later in the array.
Approach 1: Brute Force Pair Checking (O(n^2) time, O(1) space)
The straightforward approach checks every possible pair of indices. Use two nested loops: the outer loop fixes index i, and the inner loop scans all positions j > i. Every time nums[i] == nums[j], increment the answer. This method requires no additional data structures but performs n*(n-1)/2 comparisons, which becomes slow for large arrays. It mainly serves as a baseline and helps verify correctness before optimizing.
Approach 2: Hash Table + Reverse Enumeration (O(n) time, O(n) space)
The optimal solution scans the array from right to left while maintaining a frequency map using a hash table. The map stores how many times each value has already appeared to the right of the current index. When you process nums[i], perform a constant-time lookup to see how many identical values exist in the suffix of the array. That number directly represents how many valid pairs start at index i. After counting, update the frequency of nums[i] in the map and continue moving left.
This reverse traversal avoids repeatedly scanning the suffix. Each element contributes exactly one lookup and one update in the map, keeping the runtime linear. The technique is a common pattern in array problems where future occurrences matter. It also relies on efficient frequency tracking, a typical use case for counting with hash maps.
Recommended for interviews: Interviewers expect the hash table + reverse enumeration approach. The brute force solution demonstrates you understand the pair definition, but the optimized method shows you can reduce repeated work using frequency counting. Achieving O(n) time with a single pass and constant-time hash lookups is the key signal of strong problem-solving skills.
We 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n^2) | O(1) | Useful for understanding the problem or very small arrays |
| Hash Table + Reverse Enumeration | O(n) | O(n) | General case; optimal for large arrays and typical interview expectations |
Practice Delayed Count of Equal Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor