Watch 5 video solutions for Count the Number of K-Big Indices, a hard level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by Code with Carter has 1,515 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |