Online Majority Element In Subarray Solution

Language Options

Problem Description

Ah, the classic “Online Majority Element In Subarray” problem! Imagine you’re at a party, and everyone is shouting their favorite pizza topping. You want to know which topping is the most popular among your friends, but you can only ask a few of them at a time. Sounds like a fun game, right? Well, that’s exactly what this problem is about!

In this LeetCode challenge, you’re given an array of integers representing elements (like pizza toppings) and you need to answer multiple queries. Each query asks for the majority element in a specific subarray, but only if that element appears at least a certain number of times (the threshold). If no such element exists, you return -1.

So, if you think you can handle the pressure of being the pizza topping judge, let’s dive into the code!

Code Solution


class MajorityChecker {
  public MajorityChecker(int[] arr) {
    this.arr = arr;
    for (int i = 0; i < arr.length; ++i) {
      if (!numToIndices.containsKey(arr[i]))
        numToIndices.put(arr[i], new ArrayList<>());
      numToIndices.get(arr[i]).add(i);
    }
  }

  public int query(int left, int right, int threshold) {
    for (int i = 0; i < kTimes; ++i) {
      final int randIndex = rand.nextInt(right - left + 1) + left;
      final int num = arr[randIndex];
      List indices = numToIndices.get(num);
      final int l = firstGreaterEqual(indices, left);
      final int r = firstGreaterEqual(indices, right + 1);
      if (r - l >= threshold)
        return num;
    }
    return -1;
  }

  private static final int kTimes = 20; // 2^kTimes >> |arr|
  private int[] arr;
  private Map> numToIndices = new HashMap<>();
  private Random rand = new Random();

  private int firstGreaterEqual(List A, int target) {
    final int i = Collections.binarySearch(A, target);
    return i < 0 ? -i - 1 : i;
  }
}

Approach

The approach taken in this solution is quite clever! The constructor initializes a mapping of each number to its indices in the array. When a query is made, the algorithm randomly selects an index within the specified range and checks if the number at that index meets the threshold requirement. It does this multiple times (20 times, to be exact) to increase the chances of finding a valid majority element. If it finds one, it returns that number; otherwise, it returns -1.

Time and Space Complexity

Time Complexity

The average time complexity for each query is O(k * log(n)), where k is the number of times we sample (20 in this case) and n is the number of elements in the array. The binary search for indices takes O(log(n)).

Space Complexity

O(n) for storing the indices of each number in the map.

Real-World Example

Imagine you're at a pizza party, and you want to know which topping is the favorite among your friends. You can't ask everyone, so you randomly pick a few people and ask them. If enough of them say "pepperoni," you declare it the winner! This is similar to how the algorithm works—sampling randomly to find the majority element in a subarray.