Skip to main content
Talentd

Count the Number of K-Big Indices - Solution & Explanation

HardPremiumFree on FleetCodeArrayBinary SearchDivide and ConquerBinary Indexed Tree9 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

 

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 <= 105
  • 1 <= nums[i], k <= nums.length

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force CountingO(n²)O(1)Good for understanding the condition or very small arrays
Segment Tree / Ordered SetO(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

Video Solution

LeetCode 2519. Count the Number of K-Big Indices - Amazon Interview Question • Code with Carter • 1,536 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Count the Number of K-Big Indices easy or hard?
The problem is rated Hard on LeetCode because it requires recognizing the pattern of counting smaller elements on both sides efficiently. While the logic is straightforward once identified, implementing Fenwick trees or segment trees correctly requires strong data structure knowledge.
Count the Number of K-Big Indices Python or Java solution
Most implementations use a Fenwick Tree with coordinate compression. Python, Java, C++, Go, and TypeScript solutions all follow the same steps: compress values, compute left smaller counts, compute right smaller counts, and count indices where both are at least k. Each update and query runs in O(log n).
How to solve Count the Number of K-Big Indices in O(n log n)?
Use coordinate compression followed by a Binary Indexed Tree. During a left-to-right pass, query how many numbers smaller than the current value already appeared. During a right-to-left pass, repeat the process to count smaller elements on the right. Count indices where both results are at least k.
What is the best approach for Count the Number of K-Big Indices?
The most efficient approach uses a Binary Indexed Tree (Fenwick Tree). Scan the array left-to-right to count how many smaller elements appear before each index, then scan right-to-left to count smaller elements after it. Both operations use prefix frequency queries in O(log n), producing an overall time complexity of O(n log n).
Is Count the Number of K-Big Indices asked at Google Amazon Meta?
Problems involving counting smaller elements and Fenwick trees frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as 'count of smaller numbers after self' or range frequency queries are common interview patterns that test data structures like Binary Indexed Trees and Segment Trees.
What data structure is used in Count the Number of K-Big Indices?
The key data structure is a Binary Indexed Tree (Fenwick Tree). It efficiently maintains prefix frequencies and supports updates and queries in O(log n). Segment trees or ordered sets can also solve the problem, but Fenwick trees are typically simpler and faster for this pattern.
What is the time complexity of Count the Number of K-Big Indices?
The optimal solution runs in O(n log n) time using a Binary Indexed Tree or Segment Tree. Each element performs a logarithmic query and update while counting smaller elements on the left and right. The brute force method takes O(n²) time because it scans both sides for every index.

Ready to solve this problem?

Practice Count the Number of K-Big Indices with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count of Smaller Numbers After Self

Next

Find All Good Indices