Count the Number of K Big Indices
The problem
You are provided a positive integer k and an integer array nums that is 0-indexed.
An index is referred to as i k-big if the following criteria are met:
- At least k distinct indices of idx1 exist such that nums[idx1] < nums[i] and idx1 < i.
- At least k distinct indices of idx2 exist such that nums[idx2] < nums[i] and idx2 > i.
Give back how many k-big indices there are.
Input : nums = [1, 2, 3, 6, 5, 2, 4, 1] , k = 3 Output : 2 Explanation : There are only 2 big indices in nums. index 3 -> There are three valid idx1 0, 1, 2. There are four valid idx2 4, 5, 6, 7. index 4 -> There are three valid idx1 0, 1, 2. There are three valid idx2 5, 6, 7.
Input : nums = [1, 2, 3, 4, 5, 6, 7] , k = 3 Output : 0 Explanation : There are only 0 big indices in nums.
Input : nums = [4, 1, 3, 9, 5, 1, 3], k = 2
- 1 <= nums.length <= 105
- 1 <= nums[i], k <= nums.length
cpp
class Solution {
public:
int kBigIndices(vector<int>& nums, int k) {
//your code goes here
}
};java
class Solution {
public int kBigIndices(List<Integer> nums, int k) {
//your code goes here
}
}python
class Solution:
def kBigIndices(self, nums: List[int], k: int) -> int:
#your code goes herejavascript
class Solution {
kBigIndices(nums, k) {
//your code goes here
}
}csharp
public class Solution{
public int KBigIndices(int[] nums, int k){
//your code goes here
}
}go
func kBigIndices(nums []int, k int) int {
}Stuck? Show a way to structure it+
- 01Coordinate-compress values to ranks.
- 02Sweep left to right and query how many prior values are smaller.
- 03Sweep right to left and query how many later values are smaller.
- 04Count indices whose two totals are both at least k.
Reference answer
Then expect these follow-ups
How would you solve it with a segment tree instead?
Tests: data-structure substitution
How would the condition change for greater values?
Tests: rank transformations
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland

Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India

Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question