Count the Number of K-Big Indices - Practice Coding Problems

Count the Number of K-Big Indices - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,5,1,4], k = 2

› Output: 1

💡 Note: Only index 2 (value 5) is k-big: it has 2 smaller elements on left [2,3] and 2 smaller elements on right [1,4]

Example 2 — No K-Big Indices

$ Input: nums = [1,1,1], k = 3

› Output: 0

💡 Note: No index can have 3 smaller elements on both sides since all elements are equal and array has only 3 elements

Example 3 — Multiple K-Big Indices

$ Input: nums = [1,2,3,4,5,6], k = 1

› Output: 4

💡 Note: Indices 1,2,3,4 are k-big: each has at least 1 smaller element on left and 1 smaller element on right

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁶
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,3,5,1,4] with k=2

Check Each Index

Count smaller elements on left and right

Output

Count of indices with both counts >= k

Key Takeaway

🎯 Key Insight: Count smaller elements on both sides of each index to determine if it's k-big

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that an index is k-big if it has at least k smaller elements on both its left and right sides. The brute force approach checks each index by counting smaller elements on both sides in O(n³) time. A better approach uses two passes to precompute left and right counts in O(n²) time. For optimal performance, advanced data structures like Binary Indexed Trees can achieve O(n log n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Counting	O(n²)	O(n)	Precompute counts of smaller elements on left and right for each index
Brute Force	O(n³)	O(1)	For each index, count smaller elements on left and right sides

Two-Pass Counting — Algorithm Steps

Step 1: First pass - count smaller elements to the left of each index
Step 2: Second pass - count smaller elements to the right of each index
Step 3: Check each index if both left and right counts >= k

Visualization

Tap to expand

Step-by-Step Walkthrough

Pass 1

Count smaller elements to the left for each index

Pass 2

Count smaller elements to the right for each index

Check

Find indices where both counts >= k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int* leftCount = (int*)calloc(numsSize, sizeof(int));
    int* rightCount = (int*)calloc(numsSize, sizeof(int));
    
    // Count smaller elements to the left
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                leftCount[i]++;
            }
        }
    }
    
    // Count smaller elements to the right
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[j] < nums[i]) {
                rightCount[i]++;
            }
        }
    }
    
    // Count k-big indices
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (leftCount[i] >= k && rightCount[i] >= k) {
            count++;
        }
    }
    
    free(leftCount);
    free(rightCount);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops: first loop for each index, inner loop to count smaller elements

⚠ Quadratic Growth

Space Complexity

O(n)

Two arrays to store left and right counts for each index

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler