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

Coordinate compress nums to map values to a smaller range (since nums[i] can be up to 1e5).
Use a BIT to count, for each index i, the number of elements less than nums[i] to its left (left_smaller[i]).
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]).
For each index, if both left_smaller[i] and right_smaller[i] are at least k, count it as k-big.
Return the total count.

Code

[{"language":"Python","code":"class BIT:\n    def __init__(self, n):\n        self.n = n\n        self.tree = [0] * (n+2)\n    def update(self, i, v):\n        i += 1\n        while i <= self.n+1:\n            self.tree[i] += v\n            i += i & -i\n    def query(self, i):\n        i += 1\n        res = 0\n        while i > 0:\n            res += self.tree[i]\n            i -= i & -i\n        return res\n\nclass Solution:\n    def kBigIndices(self, nums: list[int], k: int) -> int:\n        n = len(nums)\n        arr = sorted(set(nums))\n        idx = {v: i for i, v in enumerate(arr)}\n        nums2 = [idx[v] for v in nums]\n        left = [0]*n\n        bit = BIT(len(arr))\n        for i in range(n):\n            left[i] = bit.query(nums2[i]-1)\n            bit.update(nums2[i], 1)\n        right = [0]*n\n        bit = BIT(len(arr))\n        for i in range(n-1, -1, -1):\n            right[i] = bit.query(nums2[i]-1)\n            bit.update(nums2[i], 1)\n        ans = 0\n        for i in range(n):\n            if left[i] >= k and right[i] >= k:\n                ans += 1\n        return ans","lang":"python"},{"language":"Java","code":"class Solution {\n    class BIT {\n        int[] tree;\n        int n;\n        BIT(int n) {\n            this.n = n;\n            tree = new int[n+2];\n        }\n        void update(int i, int v) {\n            i++;\n            while (i <= n+1) {\n                tree[i] += v;\n                i += i & -i;\n            }\n        }\n        int query(int i) {\n            i++;\n            int res = 0;\n            while (i > 0) {\n                res += tree[i];\n                i -= i & -i;\n            }\n            return res;\n        }\n    }\n    public int kBigIndices(int[] nums, int k) {\n        int n = nums.length;\n        int[] arr = java.util.Arrays.stream(nums).distinct().sorted().toArray();\n        java.util.Map<Integer, Integer> idx = new java.util.HashMap<>();\n        for (int i = 0; i < arr.length; ++i) idx.put(arr[i], i);\n        int[] nums2 = new int[n];\n        for (int i = 0; i < n; ++i) nums2[i] = idx.get(nums[i]);\n        int[] left = new int[n];\n        BIT bit = new BIT(arr.length);\n        for (int i = 0; i < n; ++i) {\n            left[i] = bit.query(nums2[i]-1);\n            bit.update(nums2[i], 1);\n        }\n        int[] right = new int[n];\n        bit = new BIT(arr.length);\n        for (int i = n-1; i >= 0; --i) {\n            right[i] = bit.query(nums2[i]-1);\n            bit.update(nums2[i], 1);\n        }\n        int ans = 0;\n        for (int i = 0; i < n; ++i) {\n            if (left[i] >= k && right[i] >= k) ans++;\n        }\n        return ans;\n    }\n}","lang":"java"}]

Complexity

🧺 Space complexity: O(nnnxxx)

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wrap items-start justify-between gap-4","children":[["$","h1",null,{"className":"text-4xl font-bold text-gray-900 dark:text-gray-100","children":"Count

Related Tags