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

EasyArrayBinary Search
Leetcode Link

Problem Description

Given an integer array nums which is sorted in non-decreasing order, and an integer target, the task is to determine whether target is a "majority" element in nums. A majority element is one that appears more than nums.length / 2 times. The function should return true if target is indeed a majority element, and false otherwise.

Intuition

The intuition behind the solution comes from the property of the array being sorted in non-decreasing order. We can use binary search to quickly find the first and last occurrences of the target element. In Python, this can be efficiently done using the bisect_left and bisect_right functions from the bisect module.

  • bisect_left returns the index of the first occurrence of target in nums (or the index where target would be inserted to maintain the sorted order if it's not present).
  • bisect_right returns the index of the first element greater than target (which would be one past the last occurrence of target if target is in nums).

By subtracting the index returned by bisect_left from the index returned by bisect_right, we get the total number of times target appears in nums. If this number is greater than nums.length / 2, then target is a majority element, and we return true. If not, we return false.

Using binary search makes the solution very efficient even for large arrays, since we avoid scanning the whole array and operate with a time complexity of O(log n).

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The solution uses a binary search approach to find the first and last occurrences of the target element in the sorted array. The binary search algorithm is a well-known method that operates by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half; otherwise, reduce it to the upper half. Repeatedly checking in this manner until the value is found or the interval is empty.

Here's how the bisect_left and bisect_right functions contribute to the solution:

  • bisect_left(nums, target): This line of code uses the bisect_left function from Python's bisect module. Given the sorted array nums, it finds the leftmost position at which target should be inserted in order to maintain the sorted order. If target is already in nums, bisect_left will return the index of the first occurrence of target. This is effectively the start index of target in the array.

  • bisect_right(nums, target): Similarly, bisect_right finds the rightmost position to insert target while keeping the array sorted. If target exists in the array, bisect_right will return the index directly after the last occurrence of target. This is essentially the index at which target would no longer appear in the array.

With the indices from bisect_left and bisect_right, the code calculates the number of times target appears in the array by subtracting the left index from the right index (right - left). This gives us the total count of target in nums.

To determine if target is a majority element, the code compares the count of target with half of the array's length (len(nums) // 2). The integer division by two ensures that we have a threshold which target's count must exceed to be considered a majority element. If the count is greater than this threshold, the function returns true; otherwise, it returns false.

The data structure used here is the list nums, and the algorithm implemented is binary search through the use of bisect_left and bisect_right. No additional data structures are necessary. This approach is efficient because it minimizes the number of elements inspected, and the binary search is performed in O(log n) time complexity, where n is the number of elements in nums.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the array nums and the target given as follows:

1nums = [1, 2, 2, 3, 3, 3, 3]
2target = 3

The array nums is sorted, and we want to determine whether 3 is a majority element. The majority element must appear more than len(nums) / 2 = 7 / 2 = 3.5 times. Since the array length is 7, the target must appear more than 3 times to be a majority element.

Let's apply the binary search approach using the bisect_left and bisect_right functions from the bisect module:

  1. Find the left index for the target 3 using bisect_left:

    1from bisect import bisect_left
2left_index = bisect_left(nums, target) # left_index is 3

    This indicates that the first occurrence of 3 in the array nums is at index 3.

  2. Find the right index for the target 3 using bisect_right:

    1from bisect import bisect_right
2right_index = bisect_right(nums, target) # right_index is 7

    This suggests that the index directly after the last appearance of 3 in the array nums is 7.

  3. Now we calculate the total count of target by subtracting the left index from the right index:

    1count = right_index - left_index # count is 4

    The variable count now holds the total number of times target appears in nums, and in this case, it is 4.

  4. Finally, check if count is greater than len(nums) / 2 to determine if target is a majority element:

    1is_majority = count > len(nums) // 2 # is_majority is True

    Since 4 is greater than 3.5, we can confirm that 3 is indeed a majority element in the array nums.

So, using this binary search approach, we have determined that the target element 3 is a majority element in the array with minimal computation compared to traversing the entire array. The example validates the solution's ability to efficiently solve the given problem.

Solution Implementation

1from bisect import bisect_left, bisect_right
2
3class Solution:
4    def isMajorityElement(self, nums: List[int], target: int) -> bool:
5        # Find the leftmost index where `target` should be inserted to keep the list sorted.
6        left_index = bisect_left(nums, target)
7      
8        # Find the rightmost index where `target` should be inserted to keep the list sorted.
9        right_index = bisect_right(nums, target)
10      
11        # Check if the count of `target` in the list is greater than half the length of the list.
12        # This is done by comparing the difference between `right_index` and `left_index`, which
13        # gives the number of occurrences of `target`, to half the length of the list.
14        return right_index - left_index > len(nums) // 2
15
1class Solution {
2    // Function to check if the target is the majority element in the sorted array
3    public boolean isMajorityElement(int[] nums, int target) {
4        // Find the start index of the target value
5        int startIndex = findFirstOccurrence(nums, target);
6        // Find the start index of the value immediately after the target
7        int endIndex = findFirstOccurrence(nums, target + 1);
8      
9        // Check if the count of the target value is more than half of the array's length
10        return (endIndex - startIndex) > nums.length / 2;
11    }
12  
13    // Helper function to find the first occurrence of a value using binary search
14    private int findFirstOccurrence(int[] nums, int value) {
15        int left = 0;
16        int right = nums.length;
17        while (left < right) {
18            // Compute the middle index
19            int mid = left + (right - left) / 2;
20          
21            // Narrow down to the left half if the middle element is greater than or equal to the value
22            if (nums[mid] >= value) {
23                right = mid;
24            } else {
25                // Otherwise, narrow down to the right half 
26                left = mid + 1;
27            }
28        }
29        // Return the starting index where the target value would be or is located
30        return left;
31    }
32}
33
1#include <vector>
2#include <algorithm> // Required for std::lower_bound and std::upper_bound
3
4class Solution {
5public:
6    bool isMajorityElement(vector<int>& nums, int target) {
7        // Use lower_bound to find the first occurrence of 'target'
8        auto firstOccurrence = std::lower_bound(nums.begin(), nums.end(), target);
9      
10        // Use upper_bound to find the position immediately after the last occurrence of 'target'
11        auto lastOccurrence = std::upper_bound(nums.begin(), nums.end(), target);
12      
13        // Calculate the number of times 'target' appears in the vector
14        int count = lastOccurrence - firstOccurrence;
15      
16        // Check if the count of 'target' is more than half the size of the vector
17        bool isMajority = count > nums.size() / 2;
18      
19        return isMajority;
20    }
21};
22
1// This function determines if a given target is the majority element in a sorted array.
2function isMajorityElement(nums: number[], target: number): boolean {
3    // Helper function that performs a binary search to find the start 
4    // index of a given number (x) in the sorted array.
5    const binarySearch = (x: number): number => {
6        let leftIndex = 0;
7        let rightIndex = nums.length;
8        // Perform a binary search.
9        while (leftIndex < rightIndex) {
10            let midIndex = (leftIndex + rightIndex) >> 1; // Equivalent to Math.floor((leftIndex + rightIndex) / 2)
11            if (nums[midIndex] >= x) {
12                rightIndex = midIndex;
13            } else {
14                leftIndex = midIndex + 1;
15            }
16        }
17        return leftIndex;
18    };
19
20    // Using the helper function to find the first occurrence of the target.
21    const firstTargetIndex = binarySearch(target);
22    // Finding the first index past the last occurrence of the target 
23    // using the next number (target + 1). 
24    const firstIndexPastTarget = binarySearch(target + 1);
25
26    // Determine if the target is the majority element by comparing the 
27    // number of occurrences to more than half the size of the array.
28    return firstIndexPastTarget - firstTargetIndex > nums.length >> 1; // Equivalent to Math.floor(nums.length / 2)
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Time and Space Complexity

Time Complexity

The time complexity of the provided code is determined by the functions bisect_left and bisect_right from Python's bisect module. Both functions perform binary search to find the leftmost and rightmost positions of target in the sorted array nums, respectively.

The binary search algorithm has a time complexity of O(log n), where n is the number of elements in the array. Since the code performs two binary searches, one for bisect_left and one for bisect_right, the total time complexity is:

2 * O(log n) = O(log n)

This simplifies to O(log n) because the constants are dropped in Big O notation.

Space Complexity

The space complexity of the code is O(1) since it uses only a fixed amount of extra space. The variables left and right are used to store the indices found by the binary search, and no additional data structures are created that depend on the size of the input array nums. Therefore, the space requirements of the algorithm do not scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫