Skip to main content
Talentd

Delayed Count of Equal Elements - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableCounting7 min readAsked at: Mitsogo
Practice this problem

Problem Statement

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, and
  • nums[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] satisfying
nums[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] satisfying
nums[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 <= 105
  • 1 <= nums[i] <= 105
  • 0 <= k <= n - 1

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckingO(n^2)O(1)Useful for understanding the problem or very small arrays
Hash Table + Reverse EnumerationO(n)O(n)General case; optimal for large arrays and typical interview expectations

Frequently Asked Questions

Is Delayed Count of Equal Elements easy or hard?
The problem is typically classified as Medium difficulty. The brute force idea is simple, but recognizing that you can track future occurrences with a hash table to achieve O(n) time requires familiarity with frequency counting patterns.
Delayed Count of Equal Elements Python/Java solution
In Python, use a dictionary to track element frequencies while iterating from the end of the array. In Java, use a HashMap<Integer, Integer> for the same purpose. For each element, add the current frequency from the map to the answer, then update the map with the new count.
How to solve Delayed Count of Equal Elements in O(n)?
Iterate through the array from right to left and maintain a hash map storing how many times each value has appeared so far. When processing nums[i], check the map for its frequency and add that count to the result. Then increment the frequency of nums[i] in the map. Each lookup and update takes constant time, giving an overall O(n) solution.
What is the best approach for Delayed Count of Equal Elements?
The most efficient approach uses a hash table combined with reverse enumeration. Traverse the array from right to left while storing frequencies of elements already seen. For each element, the frequency in the map directly tells how many equal elements appear later. This reduces the complexity to O(n) time with O(n) extra space.
Is Delayed Count of Equal Elements asked at Google/Amazon/Meta?
Pair counting and frequency tracking problems are common interview patterns at companies like Google, Amazon, and Meta. While the exact problem title may vary, the technique of using a hash table to count future or past occurrences frequently appears in coding interviews.
What data structure is used in Delayed Count of Equal Elements?
A hash table (hash map) is the primary data structure used. It stores the frequency of elements encountered during the reverse traversal. This allows constant-time lookups and updates when counting equal elements appearing later in the array.
What is the time complexity of Delayed Count of Equal Elements?
The optimal solution runs in O(n) time because each element is processed exactly once with constant-time hash map operations. A naive brute force approach checks all pairs and requires O(n^2) time. Space complexity for the optimal method is O(n) due to the frequency map.

Ready to solve this problem?

Practice Delayed Count of Equal Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays