Welcome to Subscribe On Youtube

3837. Delayed Count of Equal Elements 🔒

Description

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

Solutions

Solution 1: Hash Table + Reverse Enumeration

We can use a hash table $\textit{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 $\textit{cnt}$, then assign the value of $\textit{cnt}[nums[i]]$ to the answer array $\textit{ans}[i]$.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$.

  • class Solution {
    public int[] delayedCount(int[] nums, int k) {
        int n = nums.length;
        var cnt = new HashMap<Integer, Integer>();
        int[] ans = new int[n];
        for (int i = n - k - 2; i >= 0; --i) {
            cnt.merge(nums[i + k + 1], 1, Integer::sum);
            ans[i] = cnt.getOrDefault(nums[i], 0);
        }
        return ans;
    }
}


  • class Solution {
public:
    vector<int> delayedCount(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> cnt;
        vector<int> ans(n);
        for (int i = n - k - 2; i >= 0; --i) {
            ++cnt[nums[i + k + 1]];
            ans[i] = cnt[nums[i]];
        }
        return ans;
    }
};


  • class Solution:
    def delayedCount(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        cnt = Counter()
        ans = [0] * n
        for i in range(n - k - 2, -1, -1):
            cnt[nums[i + k + 1]] += 1
            ans[i] = cnt[nums[i]]
        return ans


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


  • function delayedCount(nums: number[], k: number): number[] {
    const n = nums.length;
    const cnt = new Map<number, number>();
    const ans = Array(n).fill(0);
    for (let i = n - k - 2; i >= 0; i--) {
        cnt.set(nums[i + k + 1], (cnt.get(nums[i + k + 1]) ?? 0) + 1);
        ans[i] = cnt.get(nums[i]) ?? 0;
    }
    return ans;
}


  • use std::collections::HashMap;

impl Solution {
    pub fn delayed_count(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let mut cnt: HashMap<i32, i32> = HashMap::new();
        let mut ans = vec![0; n];
        let k = k as usize;
        let mut i = n as i32 - k as i32 - 2;
        while i >= 0 {
            let idx = i as usize;
            *cnt.entry(nums[idx + k + 1]).or_insert(0) += 1;
            ans[idx] = *cnt.get(&nums[idx]).unwrap_or(&0);
            i -= 1;
        }
        ans
    }
}

All Problems

All Solutions