Count the Number of K-Big Indices

Count the Number of K-Big Indices

What is this problem about?

In the Count the Number of K-Big Indices coding problem, an index i is considered "$k$-big" if there are at least $k$ elements to its left that are strictly smaller than nums[i], AND at least $k$ elements to its right that are also strictly smaller than nums[i].

Your task is to return the total count of such indices in the array.

Why is this asked in interviews?

Amazon uses this "Hard" problem to test proficiency with order-statistic data structures. It evaluates whether a candidate can efficiently perform "count smaller than $X$" queries over a dynamic range. A naive solution ($O(N^2)$) will not pass. The problem requires a strategy that runs in $O(N \log N)$ or $O(N \log K)$, demonstrating mastery of Binary Indexed Trees (BIT) or Priority Queues.

Algorithmic pattern used

This problem can be solved using two passes with Binary Indexed Trees or Heaps.

1. Left Pass: Iterate from left to right. For each element, use a BIT to query how many elements seen so far are smaller than nums[i]. If the count is $\ge k$, mark left_valid[i] = true. Then add nums[i] to the BIT.
   • Optimization: For a fixed $k$, you can use a Max-Heap of size $k$ to store the $k$ smallest elements seen. If nums[i] > heap.top(), then at least $k$ elements are smaller.
2. Right Pass: Repeat the process from right to left to mark right_valid[i].
3. Combine: Count indices where both left_valid and right_valid are true.

Example explanation

nums = [2, 3, 6, 5, 2, 3], k = 2

1. Index 2 (value 6):
   • Left: [2, 3]. Two elements < 6. (Left Valid)
   • Right: [5, 2, 3]. Three elements < 6. (Right Valid)
   • Index 2 is $k$-big.
2. Index 3 (value 5):
   • Left: [2, 3]. Two elements < 5. (Left Valid)
   • Right: [2, 3]. Two elements < 5. (Right Valid)
   • Index 3 is $k$-big. Total = 2.

Common mistakes candidates make

• Off-by-one: Counting elements $\le$ nums[i] instead of strictly $<$.
• Coordinate Compression: If using a BIT and values are large, forgetting to compress the values or using a dynamic segment tree.
• Heap misuse: Using a Min-Heap when a Max-Heap is needed to track the smallest $k$ elements.

Interview preparation tip

Practice the "Two Pass" pattern. Many array problems that require checking conditions on both the left and right side of an element can be solved by running the same logic twice (once forward, once backward) and intersecting the results.