Count the Number of K Big Indices

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

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 here

javascript

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+
  1. 01Coordinate-compress values to ranks.
  2. 02Sweep left to right and query how many prior values are smaller.
  3. 03Sweep right to left and query how many later values are smaller.
  4. 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.

Get 5x interviews10 free auto-applies. No card.
  • 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

Or practice this question first

Next question