Check If a Number Is Majority Element in a Sorted Array

Problem Description

So, you think you can just waltz into a sorted array and claim that a number is the “majority” element? Well, hold your horses! The problem is to check if a given number appears more than half the time in a sorted array. Imagine you’re at a party, and you want to know if the punch bowl is the most popular drink. If it’s not, you might as well stick to water!

In simpler terms, given a sorted array of integers and a target integer, you need to determine if the target appears more than n/2 times, where n is the length of the array. If it does, congratulations! You’ve found the life of the party. If not, well, better luck next time!

Code Solution


class Solution {
  public boolean isMajorityElement(int[] nums, int target) {
    final int n = nums.length;
    final int i = firstGreaterEqual(nums, target);
    return i + n / 2 < n && nums[i + n / 2] == target;
  }

  private int firstGreaterEqual(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

Approach

The approach used in the code is quite clever. It employs a binary search to find the first occurrence of the target element in the sorted array. Once we have that index, we simply check if the element at the index i + n/2 is equal to the target. If it is, then the target is indeed the majority element. It’s like finding the first slice of cake at a party and then checking if there’s enough cake left for everyone!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log n)
Space Complexity	O(1)

Real-World Example

Imagine you’re at a concert, and the crowd is chanting for their favorite band. If the band’s name is mentioned more than half the time during the concert, you can safely say they are the majority favorite. If not, well, maybe it’s time to switch to a different genre!