You are given a 0-indexed integer array nums and a positive integer k.
We call an index ik-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.
Example 1:
Input: nums = [2,3,6,5,2,3], k = 2
Output: 2
Explanation: There are only two 2-big indices in nums:
- i = 2 --> There are two valid idx1: 0 and 1. There are three valid idx2: 2, 3, and 4.
- i = 3 --> There are two valid idx1: 0 and 1. There are two valid idx2: 3 and 4.
Example 2:
Input: nums = [1,1,1], k = 3
Output: 0
Explanation: There are no 3-big indices in nums.
Constraints:
1 <= nums.length <= 105
1 <= nums[i], k <= nums.length
Solutions
Solution 1: Binary Indexed Tree
We maintain two binary indexed trees, one records the number of elements smaller than the current position on the left, and the other records the number of elements smaller than the current position on the right.
We traverse the array, and for the current position, if the number of elements smaller than the current position on the left is greater than or equal to $k$, and the number of elements smaller than the current position on the right is greater than or equal to $k$, then the current position is a k-big, and we increment the answer by one.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the length of the array.