1150. Check If a Number Is Majority Element in a Sorted Array

Problem

Check If a Number Is Majority Element in a Sorted Array - LeetCodeLeetCode

Intuition

If the number has to be majority, it should at least occur more than nums.length/2 times in the array.

Since we found the first position, if we take half the length of input array and add it to the the first position, it gives the minimum position at which target should be present to be called as a majority number

Check if the plusNBy2Idx is in range and check if the number present at plusNBy2Idx is the target

Time Complexity

Space Complexity

Solution

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        // n -> number of elements in nums
        // Time Complexity: O(log n);
        // Space Complexity: O(1), auxillary space, no extra space is used

        // Find the first position
        int firstPosition = findFirstPosition(nums, target);

        // If the number has to be majority, it should atleast occur more than nums.length/2
        // times in the array
        // Since we found the first position, if we take half the length of input array
        // It gives the minimum position at which target should be present to be called
        // as a majority number
        int plusNBy2Idx = firstPosition + nums.length/2;


        // Check if the plusNBy2Idx is in range and check if the number present at plusNBy2Idx
        // is the target
        return plusNBy2Idx < nums.length && nums[plusNBy2Idx] == target;
    }

    private int findFirstPosition(int[] nums, int target) {
        int low = -1, high = nums.length;

        while(low + 1 < high) {
            int mid = low + (high-low)/2;

            if(nums[mid] >= target) {
                high = mid;
            } else {
                low = mid;
            }
        }

        return high;
    } 
}