LeetCode Problem 2519

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

LeetCode 2519 - Count the Number of K-Big Indices

Problem Understanding

This problem asks us to determine how many indices in an array satisfy a very specific condition related to smaller values on both sides.

For an index i to be considered k-big, two separate requirements must both hold:

1. There must be at least k indices to the left of i whose values are strictly smaller than nums[i].
2. There must be at least k indices to the right of i whose values are strictly smaller than nums[i].

The word "different indices" simply means we count distinct positions in the array. The values themselves may repeat.

The input consists of:

• An integer array nums
• A positive integer k

The output is the number of indices that satisfy both conditions.

The constraints are important:

• nums.length can be as large as 10^5
• Values inside nums can also be as large as 10^5

These constraints immediately rule out expensive quadratic approaches. Any algorithm that checks all elements to the left and right for every index independently would be too slow.

The problem also uses a strict comparison:

nums[idx] < nums[i]

Equal values do not count. This detail is extremely important because duplicate numbers appear frequently in test cases.

Several edge cases deserve attention early:

• Arrays where all elements are equal, because no index can have strictly smaller neighbors.
• Cases where k is larger than the number of elements available on one side.
• Very small arrays, especially length 1.
• Arrays with many duplicates, because equality must not be counted.
• Increasing or decreasing arrays, where only one side may satisfy the condition.

The challenge is to efficiently compute, for every index:

• How many smaller values appear before it
• How many smaller values appear after it

Once we know both counts, we simply check whether each is at least k.

Approaches

Brute Force Approach

The most direct solution is to examine every index independently.

For each position i, we scan:

• All indices to the left of i
• All indices to the right of i

During these scans, we count how many values are strictly smaller than nums[i].

If both counts are at least k, we increment the answer.

This approach is correct because it explicitly evaluates the exact definition of a k-big index. However, it is inefficient because each index may require scanning almost the entire array.

For an array of size n, this leads to approximately:

O(n^2)

operations in the worst case.

Since n can be 100000, a quadratic solution is far too slow.

Optimal Approach

The key observation is that we repeatedly need prefix and suffix frequency information.

For every element, we want to know:

• How many previously seen values are smaller
• How many future values are smaller

This is a classic use case for a Binary Indexed Tree, also called a Fenwick Tree.

A Fenwick Tree efficiently supports:

• Updating frequencies
• Querying prefix sums

both in:

O(log n)

time.

We process the array twice:

1. Left to right

• Compute how many smaller values exist before each index.

2. Right to left

• Compute how many smaller values exist after each index.

Because values can be as large as 10^5, we use the values directly as Fenwick Tree indices.

The final answer is the number of indices where both counts are at least k.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Scan left and right for every index
Optimal	O(n log n)	O(n)	Uses Fenwick Tree for efficient frequency counting

Algorithm Walkthrough

Step 1: Create a Fenwick Tree

A Fenwick Tree stores frequencies of values encountered so far.

It supports two operations:

• update(index, delta) adds a value to a position.
• query(index) returns the prefix sum from 1 to index.

This allows us to efficiently count how many numbers less than a given value have appeared.

Step 2: Compute Smaller Elements on the Left

We traverse the array from left to right.

For each value nums[i]:

1. Query the Fenwick Tree for:

count of values < nums[i]

2. Store this count in an array called left_smaller.
3. Insert nums[i] into the Fenwick Tree.

The query uses:

query(nums[i] - 1)

because the comparison must be strictly smaller.

Step 3: Reset the Fenwick Tree

After the first pass, the tree contains frequencies from the left traversal.

We create a fresh empty Fenwick Tree before processing from the right side.

Step 4: Compute Smaller Elements on the Right

We now traverse from right to left.

For each value nums[i]:

1. Query how many values smaller than nums[i] already exist in the tree.
2. Store this count in right_smaller.
3. Insert nums[i] into the tree.

Since we move from right to left, the tree represents elements located to the right of the current index.

Step 5: Count Valid K-Big Indices

Finally, iterate through all indices.

If both conditions hold:

left_smaller[i] >= k
right_smaller[i] >= k

then increment the result.

Why it works

The Fenwick Tree always stores frequencies of previously processed values.

During the left-to-right traversal, the tree contains exactly the elements before index i, so querying the tree gives the number of smaller values on the left.

During the right-to-left traversal, the tree contains exactly the elements after index i, so querying gives the number of smaller values on the right.

Because both traversals correctly compute the required counts, checking whether both are at least k correctly identifies every k-big index.

Python Solution

from typing import List

class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        total = 0

        while index > 0:
            total += self.tree[index]
            index -= index & -index

        return total

class Solution:
    def kBigIndices(self, nums: List[int], k: int) -> int:
        max_value = max(nums)

        left_smaller = [0] * len(nums)
        right_smaller = [0] * len(nums)

        fenwick = FenwickTree(max_value)

        for i, value in enumerate(nums):
            left_smaller[i] = fenwick.query(value - 1)
            fenwick.update(value, 1)

        fenwick = FenwickTree(max_value)

        for i in range(len(nums) - 1, -1, -1):
            value = nums[i]
            right_smaller[i] = fenwick.query(value - 1)
            fenwick.update(value, 1)

        answer = 0

        for i in range(len(nums)):
            if left_smaller[i] >= k and right_smaller[i] >= k:
                answer += 1

        return answer

The implementation begins by defining a Fenwick Tree class. The tree stores cumulative frequencies of values.

The update method inserts a value into the structure by incrementing the frequency at a position and propagating changes upward through the Fenwick Tree.

The query method computes a prefix sum, which represents how many values less than or equal to a given number have been inserted so far.

The algorithm then performs two passes through the array.

The first pass computes left_smaller. Before inserting the current value into the tree, we query how many smaller values have already appeared.

The second pass computes right_smaller. Since we traverse from right to left, the tree represents elements positioned after the current index.

Finally, we count how many indices satisfy both conditions.

Go Solution

package main

type FenwickTree struct {
	tree []int
	size int
}

func NewFenwickTree(size int) *FenwickTree {
	return &FenwickTree{
		tree: make([]int, size+1),
		size: size,
	}
}

func (f *FenwickTree) Update(index int, delta int) {
	for index <= f.size {
		f.tree[index] += delta
		index += index & -index
	}
}

func (f *FenwickTree) Query(index int) int {
	sum := 0

	for index > 0 {
		sum += f.tree[index]
		index -= index & -index
	}

	return sum
}

func kBigIndices(nums []int, k int) int {
	maxValue := 0

	for _, value := range nums {
		if value > maxValue {
			maxValue = value
		}
	}

	leftSmaller := make([]int, len(nums))
	rightSmaller := make([]int, len(nums))

	fenwick := NewFenwickTree(maxValue)

	for i, value := range nums {
		leftSmaller[i] = fenwick.Query(value - 1)
		fenwick.Update(value, 1)
	}

	fenwick = NewFenwickTree(maxValue)

	for i := len(nums) - 1; i >= 0; i-- {
		value := nums[i]
		rightSmaller[i] = fenwick.Query(value - 1)
		fenwick.Update(value, 1)
	}

	answer := 0

	for i := 0; i < len(nums); i++ {
		if leftSmaller[i] >= k && rightSmaller[i] >= k {
			answer++
		}
	}

	return answer
}

The Go implementation follows the same structure as the Python version.

The Fenwick Tree is implemented as a struct containing the internal slice and its size.

Go slices are dynamically sized, so no special handling for arrays is necessary. Integer overflow is not a concern because counts never exceed n, which is at most 100000.

The logic remains identical:

• One left-to-right pass
• One right-to-left pass
• Final validation step

Worked Examples

Example 1

nums = [2,3,6,5,2,3]
k = 2

Left Pass

Index	Value	Smaller on Left
0	2	0
1	3	1
2	6	2
3	5	2
4	2	0
5	3	2

Result:

left_smaller = [0,1,2,2,0,2]

Right Pass

Index	Value	Smaller on Right
5	3	0
4	2	0
3	5	2
2	6	3
1	3	1
0	2	0

Result:

right_smaller = [0,1,3,2,0,0]

Final Check

Index	Left ≥ 2	Right ≥ 2	Valid
0	No	No	No
1	No	No	No
2	Yes	Yes	Yes
3	Yes	Yes	Yes
4	No	No	No
5	Yes	No	No

Answer:

2

Example 2

nums = [1,1,1]
k = 3

Since all values are equal, no element has strictly smaller neighbors.

Left Pass

[0,0,0]

Right Pass

[0,0,0]

No index satisfies the condition.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each Fenwick Tree operation takes O(log n), and we perform two passes
Space	O(n)	Arrays for left and right counts plus the Fenwick Tree

The Fenwick Tree supports updates and prefix sum queries in logarithmic time.

We process each element twice:

• Once from left to right
• Once from right to left

Each iteration performs one query and one update, both costing O(log n).

Therefore, the total complexity is:

O(n log n)

The auxiliary space includes:

• left_smaller
• right_smaller
• Fenwick Tree storage

all proportional to the input size.

Test Cases

from typing import List

class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        total = 0

        while index > 0:
            total += self.tree[index]
            index -= index & -index

        return total

class Solution:
    def kBigIndices(self, nums: List[int], k: int) -> int:
        max_value = max(nums)

        left_smaller = [0] * len(nums)
        right_smaller = [0] * len(nums)

        fenwick = FenwickTree(max_value)

        for i, value in enumerate(nums):
            left_smaller[i] = fenwick.query(value - 1)
            fenwick.update(value, 1)

        fenwick = FenwickTree(max_value)

        for i in range(len(nums) - 1, -1, -1):
            value = nums[i]
            right_smaller[i] = fenwick.query(value - 1)
            fenwick.update(value, 1)

        answer = 0

        for i in range(len(nums)):
            if left_smaller[i] >= k and right_smaller[i] >= k:
                answer += 1

        return answer

solution = Solution()

assert solution.kBigIndices([2,3,6,5,2,3], 2) == 2  # provided example
assert solution.kBigIndices([1,1,1], 3) == 0  # all equal values
assert solution.kBigIndices([1], 1) == 0  # single element array
assert solution.kBigIndices([1,2,3,4,5], 1) == 0  # increasing sequence
assert solution.kBigIndices([5,4,3,2,1], 1) == 0  # decreasing sequence
assert solution.kBigIndices([1,5,2,6,3,7,4], 2) == 2  # mixed ordering
assert solution.kBigIndices([2,2,2,2,2], 1) == 0  # duplicates only
assert solution.kBigIndices([1,3,2,4,5], 1) == 1  # one valid index
assert solution.kBigIndices([4,1,5,2,6,3], 1) == 2  # multiple valid indices
assert solution.kBigIndices([10,20,30,40,50], 10) == 0  # k too large

Test Summary

Test	Why
[2,3,6,5,2,3], k=2	Validates the primary example
[1,1,1], k=3	Ensures equal values are not counted
[1], k=1	Tests smallest possible array
Increasing array	Verifies missing right-side smaller values
Decreasing array	Verifies missing left-side smaller values
Mixed ordering	Tests general correctness
Duplicate-heavy input	Confirms strict inequality handling
Single valid index case	Ensures exact counting
Multiple valid indices	Verifies broader correctness
Very large k	Ensures impossible conditions return zero

Edge Cases

All Elements Are Equal

Consider:

nums = [5,5,5,5]

A common mistake is accidentally counting equal values as smaller values.

The problem requires strict inequality:

nums[idx] < nums[i]

The implementation correctly handles this by querying:

query(value - 1)

which excludes equal values from the count.

K Larger Than Available Elements

Consider:

nums = [1,2,3]
k = 5

No index can possibly have five smaller values on both sides because the array itself is too small.

The implementation naturally handles this because computed counts never reach k, so no index is counted.

Strictly Increasing or Decreasing Arrays

For an increasing array:

[1,2,3,4,5]

each element may have many smaller values on the left, but none on the right.

For a decreasing array:

[5,4,3,2,1]

the opposite occurs.

These cases are important because some incorrect implementations only verify one side properly.

The solution explicitly computes independent left and right counts, guaranteeing correctness for both monotonic patterns.