Question

2519. Count the Number of K-Big Indices

中文文档

Description

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_.

 

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.

class BinaryIndexedTree:
  def __init__(self, n):
    self.n = n
    self.c = [0] * (n + 1)

  def update(self, x, delta):
    while x <= self.n:
      self.c[x] += delta
      x += x & -x

  def query(self, x):
    s = 0
    while x:
      s += self.c[x]
      x -= x & -x
    return s


class Solution:
  def kBigIndices(self, nums: List[int], k: int) -> int:
    n = len(nums)
    tree1 = BinaryIndexedTree(n)
    tree2 = BinaryIndexedTree(n)
    for v in nums:
      tree2.update(v, 1)
    ans = 0
    for v in nums:
      tree2.update(v, -1)
      ans += tree1.query(v - 1) >= k and tree2.query(v - 1) >= k
      tree1.update(v, 1)
    return ans

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }

  public void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += x & -x;
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= x & -x;
    }
    return s;
  }
}

class Solution {
  public int kBigIndices(int[] nums, int k) {
    int n = nums.length;
    BinaryIndexedTree tree1 = new BinaryIndexedTree(n);
    BinaryIndexedTree tree2 = new BinaryIndexedTree(n);
    for (int v : nums) {
      tree2.update(v, 1);
    }
    int ans = 0;
    for (int v : nums) {
      tree2.update(v, -1);
      if (tree1.query(v - 1) >= k && tree2.query(v - 1) >= k) {
        ++ans;
      }
      tree1.update(v, 1);
    }
    return ans;
  }
}

class BinaryIndexedTree {
public:
  BinaryIndexedTree(int _n)
    : n(_n)
    , c(_n + 1) {}

  void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += x & -x;
    }
  }

  int query(int x) {
    int s = 0;
    while (x) {
      s += c[x];
      x -= x & -x;
    }
    return s;
  }

private:
  int n;
  vector<int> c;
};

class Solution {
public:
  int kBigIndices(vector<int>& nums, int k) {
    int n = nums.size();
    BinaryIndexedTree* tree1 = new BinaryIndexedTree(n);
    BinaryIndexedTree* tree2 = new BinaryIndexedTree(n);
    for (int& v : nums) {
      tree2->update(v, 1);
    }
    int ans = 0;
    for (int& v : nums) {
      tree2->update(v, -1);
      ans += tree1->query(v - 1) >= k && tree2->query(v - 1) >= k;
      tree1->update(v, 1);
    }
    return ans;
  }
};

type BinaryIndexedTree struct {
  n int
  c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  c := make([]int, n+1)
  return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, delta int) {
  for x <= this.n {
    this.c[x] += delta
    x += x & -x
  }
}

func (this *BinaryIndexedTree) query(x int) int {
  s := 0
  for x > 0 {
    s += this.c[x]
    x -= x & -x
  }
  return s
}

func kBigIndices(nums []int, k int) (ans int) {
  n := len(nums)
  tree1 := newBinaryIndexedTree(n)
  tree2 := newBinaryIndexedTree(n)
  for _, v := range nums {
    tree2.update(v, 1)
  }
  for _, v := range nums {
    tree2.update(v, -1)
    if tree1.query(v-1) >= k && tree2.query(v-1) >= k {
      ans++
    }
    tree1.update(v, 1)
  }
  return
}