Count the Number of K-Big Indices

Problem

You are given a 0-indexed integer array nums and a positive integer k.

We call an index i k-big if the following conditions are satisfied:

• There exist at least k different indices idx1 such that idx1 < i and nums[idx1] < nums[i].
• There exist at least k different indices idx2 such that idx2 > i and nums[idx2] < nums[i].

Return the number of k-big indices.

Examples

Example 1:

Input: nums = [2,3,6,5,2,3], k = 2
Output: 2
Explanation: There are only two 2-big indices in nums:
- i = 2 --> There are two valid idx1: 0 and 1. There are three valid idx2: 2, 3, and 4.
- i = 3 --> There are two valid idx1: 0 and 1. There are two valid idx2: 3 and 4.

Example 2:

Input: nums = [1,1,1], k = 3
Output: 0
Explanation: There are no 3-big indices in nums.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i], k <= nums.length

Solution

Method 1 – Binary Indexed Tree (Fenwick Tree)

Intuition

We need to count, for each index, the number of elements less than nums[i] to its left and right. This is a classic use case for a Binary Indexed Tree (Fenwick Tree) or a Segment Tree, as we need to efficiently count and update frequencies.

Approach

1. Coordinate compress nums to map values to a smaller range (since nums[i] can be up to 1e5).
2. Use a BIT to count, for each index i, the number of elements less than nums[i] to its left (left_smaller[i]).
3. Use another BIT (or reuse) to count, for each index i, the number of elements less than nums[i] to its right (right_smaller[i]).
4. For each index, if both left_smaller[i] and right_smaller[i] are at least k, count it as k-big.
5. Return the total count.

Code

Python

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n+2)
    def update(self, i, v):
        i += 1
        while i <= self.n+1:
            self.tree[i] += v
            i += i & -i
    def query(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

class Solution:
    def kBigIndices(self, nums: list[int], k: int) -> int:
        n = len(nums)
        arr = sorted(set(nums))
        idx = {v: i for i, v in enumerate(arr)}
        nums2 = [idx[v] for v in nums]
        left = [0]*n
        bit = BIT(len(arr))
        for i in range(n):
            left[i] = bit.query(nums2[i]-1)
            bit.update(nums2[i], 1)
        right = [0]*n
        bit = BIT(len(arr))
        for i in range(n-1, -1, -1):
            right[i] = bit.query(nums2[i]-1)
            bit.update(nums2[i], 1)
        ans = 0
        for i in range(n):
            if left[i] >= k and right[i] >= k:
                ans += 1
        return ans

Java

class Solution {
    class BIT {
        int[] tree;
        int n;
        BIT(int n) {
            this.n = n;
            tree = new int[n+2];
        }
        void update(int i, int v) {
            i++;
            while (i <= n+1) {
                tree[i] += v;
                i += i & -i;
            }
        }
        int query(int i) {
            i++;
            int res = 0;
            while (i > 0) {
                res += tree[i];
                i -= i & -i;
            }
            return res;
        }
    }
    public int kBigIndices(int[] nums, int k) {
        int n = nums.length;
        int[] arr = java.util.Arrays.stream(nums).distinct().sorted().toArray();
        java.util.Map<Integer, Integer> idx = new java.util.HashMap<>();
        for (int i = 0; i < arr.length; ++i) idx.put(arr[i], i);
        int[] nums2 = new int[n];
        for (int i = 0; i < n; ++i) nums2[i] = idx.get(nums[i]);
        int[] left = new int[n];
        BIT bit = new BIT(arr.length);
        for (int i = 0; i < n; ++i) {
            left[i] = bit.query(nums2[i]-1);
            bit.update(nums2[i], 1);
        }
        int[] right = new int[n];
        bit = new BIT(arr.length);
        for (int i = n-1; i >= 0; --i) {
            right[i] = bit.query(nums2[i]-1);
            bit.update(nums2[i], 1);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] >= k && right[i] >= k) ans++;
        }
        return ans;
    }
}

Complexity

• 🧺 Space complexity: O(nnnxxx)