LeetCode 3837 - Delayed Count of Equal Elements

LeetCode Problem 3837

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem requires computing a delayed count for each element in an array nums. For an index i, the delayed count is defined as the number of later elements (indices j > i + k) that are equal to nums[i]. In simpler terms, for each element, we want to count how many times that same value occurs after a certain delay k.

The input is an integer array nums of length n and an integer k. The output is an array of the same length n, where each entry ans[i] corresponds to the delayed count for index i.

Constraints indicate that n can be as large as 10^5, and values of nums[i] are up to 10^5. This tells us that a naive approach with nested loops is likely too slow, and an efficient solution should avoid repeated scanning of the array. Edge cases include k = 0 (count immediately after i) and k = n - 1 (no index j satisfies i + k < j). The array could also contain all identical elements, which could stress performance.

Approaches

The brute-force approach is straightforward: iterate over each index i and for each i, scan all indices j > i + k to count the number of times nums[j] equals nums[i]. This guarantees correctness but runs in O(n^2) in the worst case, which is not feasible for n = 10^5.

The key insight for an optimal solution is that we can process the array from right to left while maintaining a hash map that tracks the frequency of elements we've already seen. By maintaining counts of future elements in a hash map, we can directly look up how many instances of nums[i] exist at positions j > i + k without scanning repeatedly. Specifically, we add counts to the hash map only after the delay k, ensuring we count only valid j indices. This approach reduces the time complexity to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Scan all valid j for each i
Optimal	O(n)	O(n)	Right-to-left traversal with delayed frequency map

Algorithm Walkthrough

1. Initialize an array ans of length n filled with zeros. This will store the delayed counts for each index.

2. Initialize an empty hash map count_map to store counts of elements that have appeared in the array at positions beyond the current index plus k.

3. Iterate over nums from right to left (from index n-1 down to 0):

4. For each index i, check if nums[i] exists in count_map. If it does, assign ans[i] = count_map[nums[i]]; otherwise, it remains 0.

5. Check if i + k < n. If this condition holds, increment count_map[nums[i + k]] by 1. This ensures we only count elements that appear after the required delay.

6. After the iteration is complete, ans contains the delayed counts for all indices.

Why it works: The algorithm maintains an invariant that count_map[x] always contains the number of times element x appears strictly after index i + k. By processing from right to left, we ensure that each ans[i] is calculated based on only the valid future indices, and by updating the map after i + k, we respect the delay requirement.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def delayedCount(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        ans = [0] * n
        count_map = defaultdict(int)
        
        for i in range(n - 1, -1, -1):
            ans[i] = count_map[nums[i]]
            if i + k < n:
                count_map[nums[i + k]] += 1
        
        return ans

The Python implementation initializes the answer array and a defaultdict for counting. By iterating from the last element to the first, we correctly update the counts for future elements while assigning the delayed counts at each index. The if i + k < n condition ensures only valid delayed indices contribute to the frequency map.

Go Solution

func delayedCount(nums []int, k int) []int {
    n := len(nums)
    ans := make([]int, n)
    countMap := make(map[int]int)
    
    for i := n - 1; i >= 0; i-- {
        ans[i] = countMap[nums[i]]
        if i + k < n {
            countMap[nums[i + k]]++
        }
    }
    
    return ans
}

In Go, we use a native map to track element counts. The logic is identical to the Python solution. A slice of length n is pre-allocated for ans, and we increment counts only for indices beyond i + k to ensure correctness.

Worked Examples

Example 1: nums = [1,2,1,1], k = 1

Iterating right to left:

i	nums[i]	ans[i]	Update count_map
3	1	0	-
2	1	0	count_map[3]? i+k=3? update count_map[3] no? Wait clarify
Let's recalc: count_map update: nums[i+k] if i+k<n

i	nums[i]	ans[i]	i+k<n? update count_map[nums[i+k]]
3	1	0	3+1=4 ≥ n -> no
2	1	0	2+1=3 < n -> count_map[nums[3]]=count_map[1]+=1 -> count_map[1]=1
1	2	0	1+1=2 < n -> count_map[nums[2]]=count_map[1]+=1 -> count_map[1]=2
0	1	2	0+1=1 < n -> count_map[nums[1]]=count_map[2]+=1 -> count_map[2]=1

Final ans = [2,0,0,0]

Example 2: nums = [3,1,3,1], k = 0

i	nums[i]	ans[i]	Update count_map
3	1	0	i+k=3 < n yes -> count_map[nums[3]]=count_map[1]=1
2	3	0	i+k=2 -> count_map[nums[2]]=count_map[3]=1
1	1	1	i+k=1 -> count_map[nums[1]]=count_map[1]+=1 -> count_map[1]=2
0	3	1	i+k=0 -> count_map[nums[0]]=count_map[3]+=1 -> count_map[3]=2

Final ans = [1,1,0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is visited once, and hash map operations are O(1) on average
Space	O(n)	Hash map stores counts for each unique number in the array

The dominant factor is the single pass over the array and the use of the hash map to track frequencies, which scales linearly with the number of elements.

Test Cases

# Provided examples
assert Solution().delayedCount([1,2,1,1], 1) == [2,0,0,0]  # Example 1
assert Solution().delayedCount([3,1,3,1], 0) == [1,1,0,0]  # Example 2

# Edge cases
assert Solution().delayedCount([1], 0) == [0]  # single element
assert Solution().delayedCount([1,1,1,1], 3) == [0,0,0,0]  # delay larger than index
assert Solution().delayedCount([1,2,3,4,5], 0) == [0,0,0,0,0]  # all unique
assert Solution().delayedCount([1,1,1,1,1], 0) == [4,3,2,1,0]  # all same, zero delay
assert Solution().delayedCount([1,2,1,2,1,2], 1) == [2,2,1,1,0,0]  # alternating pattern

Test	Why
Single element	Checks minimal array
Delay larger than possible indices	Ensures zero counts when no future index is valid