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:
k different indices idx1 such that idx1 < i and nums[idx1] < nums[i].k different indices idx2 such that idx2 > i and nums[idx2] < nums[i].Return the number of k-big indices.
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 <= 1051 <= nums[i], k <= nums.lengthProblem Overview: You receive an integer array nums and a number k. An index i is considered k-big if there are at least k elements smaller than nums[i] to its left and at least k elements smaller than nums[i] to its right. The task is to count how many indices satisfy this condition.
Approach 1: Brute Force Counting (O(n²) time, O(1) space)
The direct approach checks every index and counts how many elements smaller than nums[i] exist on the left and right. For each index, iterate left to count valid elements, then iterate right and repeat. If both counts reach at least k, mark the index as k-big. This solution is straightforward and helps verify correctness during early reasoning. However, it performs two scans per element, leading to O(n²) time, which fails for large inputs.
Approach 2: Ordered Set / Segment Tree (O(n log n) time, O(n) space)
You can maintain a frequency structure while scanning the array. Using a balanced ordered structure such as a Segment Tree or ordered set, track how many values smaller than the current number have appeared. First scan left-to-right to compute leftSmaller[i]. Then scan right-to-left to compute rightSmaller[i]. Range queries return the number of values smaller than nums[i] in O(log n). Finally, count indices where both values are at least k. This approach handles large ranges efficiently and demonstrates strong understanding of range counting data structures.
Approach 3: Binary Indexed Tree (Fenwick Tree) (O(n log n) time, O(n) space)
The most practical solution uses a Binary Indexed Tree. First coordinate-compress values in nums so they map to a small range. Traverse left-to-right and query the Fenwick tree for how many numbers smaller than the current value have already appeared. Store this as leftSmaller[i], then update the tree with the current value. Reset the structure and repeat the process from right-to-left to compute rightSmaller[i]. Finally, iterate once more and count indices where both counts are at least k. Each query and update takes O(log n), producing an overall complexity of O(n log n). Fenwick trees are simpler to implement than segment trees and perform extremely well for frequency prefix queries in array problems.
Recommended for interviews: The Binary Indexed Tree approach is the expected solution. Interviewers typically look for the insight that the problem reduces to counting smaller elements on both sides using prefix frequency queries. Explaining the brute force approach first shows understanding of the condition, while transitioning to Fenwick tree optimization demonstrates strong algorithmic problem solving.
We maintain two binary indexed trees, one records the number of elements smaller than the current position on the left, and the other records the number of elements smaller than the current position on the right.
We traverse the array, and for the current position, if the number of elements smaller than the current position on the left is greater than or equal to k, and the number of elements smaller than the current position on the right is greater than or equal to k, then the current position is a k-big, and we increment the answer by one.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Counting | O(n²) | O(1) | Good for understanding the condition or very small arrays |
| Segment Tree / Ordered Set | O(n log n) | O(n) | Useful when solving general range counting queries or extending the problem |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Most practical solution for counting smaller elements on both sides |
LeetCode 2519. Count the Number of K-Big Indices - Amazon Interview Question • Code with Carter • 1,515 views views
Watch 4 more video solutions →Practice Count the Number of K-Big Indices with our built-in code editor and test cases.
Practice on FleetCode