3837. Delayed Count of Equal Elements 🔒

MediumArrayHash TableCounting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n and an integer k.

For each index i, we define the delayed count as the number of indices j that satisfy both of the following conditions:

i + k < j <= n - 1, which means j must come strictly after the position i + k and stay within the array bounds.
nums[j] == nums[i], which means the value at index j must equal the value at index i.

In simple terms, for each index i, we look only at the elements that appear after position i + k (skipping the next k elements right after i), and count how many of those elements share the same value as nums[i].

Return an array ans where ans[i] is the delayed count of index i.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Counting frequencies of elements with a hash table for reverse-enumeration lookups.

Open in Flowchart

Intuition

For each index i, we need to count how many elements equal to nums[i] appear strictly after the position i + k. A straightforward approach would be to check every valid j for each i, but this leads to repeated work and is inefficient.

The key observation is to look at the structure of the valid range. For index i, the elements we care about start from index i + k + 1 and go up to the end of the array. Now consider what happens when we move from index i to index i - 1: the valid range shifts by one position, and the only new element that enters the window is the one at index (i - 1) + k + 1 = i + k. Everything else in the range stays the same.

This suggests processing the indices in reverse order. If we move from the end of the array toward the beginning, then each time we step to a smaller index i, exactly one new element (the element at index i + k + 1) becomes eligible to be counted. So instead of recomputing the count from scratch, we can maintain a running tally of how many times each value has appeared in the current valid range.

To track these counts, we use a hash table cnt, where cnt[v] stores how many times value v has appeared so far in the range (i + k, n - 1]. As we move backward through the indices, we first add the newly eligible element nums[i + k + 1] to cnt, then simply read off cnt[nums[i]] to get the answer for index i. This way, each element is added to the hash table only once, giving us an efficient single-pass solution.

Solution Approach

Solution 1: Hash Table + Reverse Enumeration

We use a hash table cnt to record the number of occurrences of each value within the index range (i + k, n - 1]. The core idea is to enumerate the indices in reverse order so that each newly eligible element is added to the hash table exactly once.

Data Structures Used:

A hash table cnt (implemented with Counter) that maps each value to its count within the current valid range.
An answer array ans of length n, initialized with all zeros.

Step-by-step walkthrough:

Let n be the length of nums. Initialize an empty counter cnt and an answer array ans = [0] * n.
Enumerate index i in reverse, starting from n - k - 2 down to 0. We start at n - k - 2 because for any index i, the first eligible element sits at position i + k + 1. For this position to be a valid index (at most n - 1), we need i + k + 1 <= n - 1, which gives i <= n - k - 2. Any index larger than this has an empty valid range, so its answer stays at the default value 0.
For each i, the element at index i + k + 1 is the new element that enters the valid range. We add it to the hash table: cnt[nums[i + k + 1]] += 1.
After updating the counter, the value cnt[nums[i]] directly tells us how many elements equal to nums[i] lie in the range (i + k, n - 1]. We assign this to the answer: ans[i] = cnt[nums[i]].
After the loop finishes, return ans.

Because we process the indices from right to left, the element at index i + k + 1 is precisely the one that becomes newly available when we move from index i + 1 to index i. This guarantees that cnt always reflects the correct counts for the current range, and each element is inserted into the hash table only once.

Complexity Analysis:

Time complexity: O(n), since we iterate through the array once and each hash table operation takes constant time on average.
Space complexity: O(n), for the hash table cnt which may store up to n distinct values.

Example Walkthrough

Let's trace through a small example to see how the reverse enumeration with a hash table works.

Input: nums = [1, 2, 1, 1, 2], k = 1, so n = 5.

Goal: For each index i, count how many indices j satisfy i + 1 < j <= 4 and nums[j] == nums[i].

Setup:

cnt = {} (empty counter)
ans = [0, 0, 0, 0, 0]
Starting index: n - k - 2 = 5 - 1 - 2 = 2, so we iterate i from 2 down to 0.

Indices i = 3 and i = 4 are skipped because their valid range (i + k, n - 1] is empty (no room for any j), so their answers stay at 0.

Iteration steps:

Step	`i`	New element index `i+k+1`	Add `nums[i+k+1]` to `cnt`	`cnt` after update	`nums[i]`	`ans[i] = cnt[nums[i]]`
1	`2`	`2+1+1 = 4`	`nums[4] = 2`	`{2: 1}`	`nums[2] = 1`	`cnt[1] = 0`
2	`1`	`1+1+1 = 3`	`nums[3] = 1`	`{2: 1, 1: 1}`	`nums[1] = 2`	`cnt[2] = 1`
3	`0`	`0+1+1 = 2`	`nums[2] = 1`	`{2: 1, 1: 2}`	`nums[0] = 1`	`cnt[1] = 2`

Final result: ans = [2, 1, 0, 0, 0]

Verification:

i = 0 (nums[0] = 1): valid j range is 1 < j <= 4, i.e. j ∈ {2, 3, 4}. Values are 1, 1, 2 → two 1s match. ✓ ans[0] = 2
i = 1 (nums[1] = 2): valid j range is 2 < j <= 4, i.e. j ∈ {3, 4}. Values are 1, 2 → one 2 matches. ✓ ans[1] = 1
i = 2 (nums[2] = 1): valid j range is 3 < j <= 4, i.e. j ∈ {4}. Value is 2 → no 1s match. ✓ ans[2] = 0
i = 3, 4: empty range → 0. ✓

Key insight illustrated: Notice how at each step we only add one new element to cnt (the element at i + k + 1), rather than rescanning the whole tail of the array. When moving from i = 1 to i = 0, the element at index 2 becomes newly eligible and enters the window, while everything already counted remains valid. This single-insertion-per-step behavior is exactly what gives the algorithm its O(n) efficiency.

Solution Implementation

1from collections import Counter
2from typing import List
3
4
5class Solution:
6    def delayedCount(self, nums: List[int], k: int) -> List[int]:
7        n = len(nums)
8        # counter holds frequencies of values located at indices >= i + k + 1
9        # relative to the current index i being processed
10        counter = Counter()
11        ans = [0] * n
12
13        # Iterate from right to left.
14        # The first valid index that can have an element at distance k+1
15        # ahead is n - k - 2 (since (n - k - 2) + (k + 1) = n - 1).
16        for i in range(n - k - 2, -1, -1):
17            # Bring the element that is exactly (k + 1) positions ahead
18            # of i into the window of "delayed" elements.
19            counter[nums[i + k + 1]] += 1
20            # Record how many elements at indices >= i + k + 1
21            # share the same value as nums[i].
22            ans[i] = counter[nums[i]]
23
24        return ans
25

1class Solution {
2    public int[] delayedCount(int[] nums, int k) {
3        int n = nums.length;
4        // Frequency map counting occurrences of values located at indices > current i + k.
5        Map<Integer, Integer> countMap = new HashMap<>();
6        int[] answer = new int[n];
7
8        // Traverse from right to left.
9        // For index i, we consider only elements at indices strictly greater than i + k.
10        // The smallest valid starting i is n - k - 2, so that i + k + 1 == n - 1 is in range.
11        for (int i = n - k - 2; i >= 0; i--) {
12            // The element nums[i + k + 1] now becomes eligible for index i (and all smaller i),
13            // so add it to the frequency map.
14            countMap.merge(nums[i + k + 1], 1, Integer::sum);
15
16            // Record how many eligible elements equal nums[i].
17            answer[i] = countMap.getOrDefault(nums[i], 0);
18        }
19
20        return answer;
21    }
22}
23

1class Solution {
2public:
3    // For each index i, count how many later elements (at least k+1 positions
4    // after i) have the same value as nums[i].
5    vector<int> delayedCount(vector<int>& nums, int k) {
6        int n = nums.size();
7
8        // frequency[value] -> number of eligible later elements equal to value
9        unordered_map<int, int> frequency;
10
11        // result[i] holds the answer for index i
12        vector<int> result(n);
13
14        // Iterate from right to left.
15        // When processing index i, the element at index (i + k + 1) becomes
16        // eligible (it lies exactly k+1 positions ahead), so we record it first.
17        for (int i = n - k - 2; i >= 0; --i) {
18            // Add the newly eligible element into the frequency map.
19            ++frequency[nums[i + k + 1]];
20
21            // The answer for i is how many eligible later elements
22            // share the same value as nums[i].
23            result[i] = frequency[nums[i]];
24        }
25
26        return result;
27    }
28};
29

1/**
2 * For each index i, counts how many later elements equal nums[i],
3 * considering only positions that are at least (k + 1) indices ahead of i.
4 *
5 * @param nums - The input array of numbers.
6 * @param k    - The required gap (delay) between an index and the positions counted.
7 * @returns An array where result[i] is the count of elements equal to nums[i]
8 *          located at indices >= i + k + 1.
9 */
10function delayedCount(nums: number[], k: number): number[] {
11    const length: number = nums.length;
12
13    // Frequency map of values located at positions >= i + k + 1 relative to current i.
14    const frequency: Map<number, number> = new Map<number, number>();
15
16    // Result array, defaulting every entry to 0.
17    const result: number[] = Array<number>(length).fill(0);
18
19    // Iterate from the last index that has a valid "delayed" element ahead of it.
20    // The first counted position for index i is (i + k + 1), so the largest i
21    // with such a position in bounds is (length - k - 2).
22    for (let i = length - k - 2; i >= 0; i--) {
23        // The element at position (i + k + 1) now enters the valid window for index i.
24        const incomingValue: number = nums[i + k + 1];
25        frequency.set(incomingValue, (frequency.get(incomingValue) ?? 0) + 1);
26
27        // Record how many valid elements ahead match the current value nums[i].
28        result[i] = frequency.get(nums[i]) ?? 0;
29    }
30
31    return result;
32}
33

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The single for loop iterates from n - k - 2 down to 0, performing at most n iterations. Inside each iteration, the operations on the Counter (incrementing a count and looking up a value) take O(1) time on average. Therefore, the overall time complexity is O(n).
Space Complexity: O(n). The Counter object cnt can store up to O(n) distinct elements in the worst case (when all elements in nums are unique). Additionally, the answer array ans requires O(n) space. Hence, the total space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Off-by-One Error in the Starting Index of Reverse Enumeration

The most common mistake is miscalculating the starting index of the reverse loop. Many people instinctively write for i in range(n - k - 1, -1, -1) or for i in range(n - 1, -1, -1), both of which lead to bugs.

Why it's wrong:

The condition for j is i + k < j <= n - 1, which means the first eligible element is at index i + k + 1. For this index to be valid, we need:

i + k + 1 <= n - 1
i <= n - k - 2

If you start at n - k - 1, then on the very first iteration you access nums[i + k + 1] = nums[(n - k - 1) + k + 1] = nums[n], which is out of bounds and raises an IndexError.
If you start at n - 1, the same out-of-bounds access happens even sooner.

Correct approach:

Start the loop at n - k - 2, which is exactly the largest index whose valid range is non-empty:

for i in range(n - k - 2, -1, -1):
    counter[nums[i + k + 1]] += 1
    ans[i] = counter[nums[i]]

All indices i > n - k - 2 correctly keep their default answer of 0, since their valid range is empty.

Pitfall 2: Adding the Wrong Element to the Counter

A subtle error is adding nums[i] (the current element) or nums[i + k] to the counter instead of nums[i + k + 1].

Why it's wrong:

The window of "delayed" elements is the range (i + k, n - 1], i.e., indices strictly greater than i + k. When moving from i + 1 to i, the newly available element is exactly the one at index i + k + 1 (since index (i+1) + k + 1 = i + k + 2 was already in the window, and now i + k + 1 becomes the new boundary entrant).

Adding nums[i + k] would incorrectly include the element at the boundary, violating the strict inequality i + k < j.
Adding nums[i] confuses the value being queried with the value being inserted.

Correct approach:

Always insert nums[i + k + 1] before reading ans[i] = counter[nums[i]], so the counter reflects the full range (i + k, n - 1] for the current i.

Pitfall 3: Forgetting to Handle Edge Cases for Large `k`

When k >= n - 1, the starting index n - k - 2 becomes negative, so the loop body never executes. This is actually correct behavior—every index has an empty valid range—but only if you rely on range naturally producing an empty sequence.

Why it matters:

# When n = 5, k = 10:
n - k - 2 = 5 - 10 - 2 = -7
range(-7, -1, -1)  # empty, loop never runs

The range(-7, -1, -1) is empty because the start is already below the stop with a negative step, so ans remains all zeros, which is correct. No special-casing is needed, but be careful not to add a manual guard like if i >= 0 inside an incorrectly written loop that could still attempt the first iteration. Trusting range to handle this cleanly avoids introducing accidental bugs.

Pitfall 4: Using `dict` Instead of `Counter` Without Default Handling

If you replace Counter with a plain dict, then counter[nums[i]] raises a KeyError whenever nums[i] hasn't been inserted yet.

Correct approaches:

Use collections.Counter (recommended), which returns 0 for missing keys automatically.
Or use dict.get(nums[i], 0) to provide a default:

counter = {}
for i in range(n - k - 2, -1, -1):
    counter[nums[i + k + 1]] = counter.get(nums[i + k + 1], 0) + 1
    ans[i] = counter.get(nums[i], 0)

This preserves correctness while avoiding the KeyError trap.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering