Binary Search to Find Next Greater Element IV

The problem sometimes with BS is to handle the corner cases. In the problem down below, corner cases in my solutions happen when the index k is out of range or when we find an exact match (handled in the return statement). Code is down below, cheers, ACC.

Delayed Count of Equal Elements - LeetCode

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

public class Solution {
	public int[] DelayedCount(int[] nums, int k)
	{
		Hashtable listIndexes = new Hashtable();

		for (int i = 0; i < nums.Length; i++)
		{
			if (!listIndexes.ContainsKey(nums[i])) listIndexes.Add(nums[i], new List());
			List list = (List)listIndexes[nums[i]];
			list.Add(i);
		}

		int[] retVal = new int[nums.Length];
		for (int i = 0; i < nums.Length; i++)
		{
			retVal[i] = BinarySearchIndexes((List)listIndexes[nums[i]], i + k);
		}

		return retVal;
	}

	private int BinarySearchIndexes(List list, int k)
	{
		if (k >= list[list.Count - 1]) return 0;

		int left = 0;
		int right = list.Count - 1;

		while (left < right)
		{
			int middle = (left + right) / 2;
			if (k > list[middle]) left = middle + 1;
			else right = middle;
		}

		return list[left] == k ? list.Count - left - 1 : list.Count - left;
	}
}