We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of K-Big Indices

Number: 2658

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

Given a 0-indexed integer array nums and a positive integer k, an index i is defined as k-big if:

  • There exist at least k indices j (with j < i) such that nums[j] < nums[i].
  • There exist at least k indices j (with j > i) such that nums[j] < nums[i]. Return the number of k-big indices in the array.

Key Insights

  • To determine the count of elements less than the current element on the left and right, a data structure that supports fast prefix queries is needed.
  • A Fenwick Tree (also known as Binary Indexed Tree) or Segment Tree can efficiently maintain prefix counts during iteration.
  • First, perform coordinate compression to handle a potentially wide range of numbers and map them to a smaller range.
  • Compute two arrays: one for left counts (by scanning from left to right) and one for right counts (by scanning from right to left).
  • An index i qualifies as k-big if both counts are at least k.

Space and Time Complexity

Time Complexity: O(n log n) where n is the length of nums (due to coordinate compression and Fenwick Tree operations). Space Complexity: O(n) for the auxiliary arrays and the Fenwick Tree.

Solution

The solution uses coordinate compression to map the potentially large numbers into a manageable range. Then, we use a Fenwick Tree to count the number of elements less than the current element while scanning the array.

  1. Compute a sorted list of unique values from nums and create a mapping (compression) for these values.
  2. Initialize a Fenwick Tree of appropriate size and iterate over nums from left to right. For each index i, query the tree to determine how many numbers that have already appeared are less than nums[i]. This gives the left count.
  3. Reset (or use another tree) and iterate over nums from right to left to compute the right count for each index.
  4. Finally, loop through the computed counts and count indices where both left and right counts are at least k.

A similar approach and data structure could be applied in any language that supports these operations.

Code Solutions

# Python solution using Fenwick Tree and coordinate compression.

# Fenwick Tree implementation.
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)
        
    # update the tree index (1-indexed) with delta.
    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index
            
    # query the prefix sum from 1 to index.
    def query(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

def countKBIGIndices(nums, k):
    n = len(nums)
    # coordinate compression
    sorted_unique = sorted(set(nums))
    rank = {num: i+1 for i, num in enumerate(sorted_unique)}  # 1-indexed for fenwick tree
    size = len(sorted_unique)
    
    leftCount = [0] * n
    ft = FenwickTree(size)
    # Compute left counts.
    for i in range(n):
        r = rank[nums[i]]
        # Query how many numbers < current number (all indices with rank r-1 or less).
        leftCount[i] = ft.query(r - 1)
        ft.update(r, 1)

    rightCount = [0] * n
    ft = FenwickTree(size)
    # Compute right counts by scanning from right to left.
    for i in range(n-1, -1, -1):
        r = rank[nums[i]]
        rightCount[i] = ft.query(r - 1)
        ft.update(r, 1)
    
    # Count indices that have at least k smaller numbers on both sides.
    answer = 0
    for i in range(n):
        if leftCount[i] >= k and rightCount[i] >= k:
            answer += 1
    return answer

# Example usage:
print(countKBIGIndices([2, 3, 6, 5, 2, 3], 2))  # Expected Output: 2
← Back to All Questions