Count the Number of K Big Indices
AmazonThe 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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question