1150. Check If a Number Is Majority Element in a Sorted Array
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 oftarget
innums
(or the index wheretarget
would be inserted to maintain the sorted order if it's not present).bisect_right
returns the index of the first element greater thantarget
(which would be one past the last occurrence oftarget
iftarget
is innums
).
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.
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 thebisect_left
function from Python'sbisect
module. Given the sorted arraynums
, it finds the leftmost position at whichtarget
should be inserted in order to maintain the sorted order. Iftarget
is already innums
,bisect_left
will return the index of the first occurrence oftarget
. This is effectively the start index oftarget
in the array. -
bisect_right(nums, target)
: Similarly,bisect_right
finds the rightmost position to inserttarget
while keeping the array sorted. Iftarget
exists in the array,bisect_right
will return the index directly after the last occurrence oftarget
. This is essentially the index at whichtarget
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose we have the array nums
and the target
given as follows:
nums = [1, 2, 2, 3, 3, 3, 3] target = 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:
-
Find the left index for the target
3
usingbisect_left
:from bisect import bisect_left left_index = bisect_left(nums, target) # left_index is 3
This indicates that the first occurrence of
3
in the arraynums
is at index 3. -
Find the right index for the target
3
usingbisect_right
:from bisect import bisect_right right_index = bisect_right(nums, target) # right_index is 7
This suggests that the index directly after the last appearance of
3
in the arraynums
is 7. -
Now we calculate the total count of
target
by subtracting the left index from the right index:count = right_index - left_index # count is 4
The variable
count
now holds the total number of timestarget
appears innums
, and in this case, it is 4. -
Finally, check if
count
is greater thanlen(nums) / 2
to determine iftarget
is a majority element:is_majority = count > len(nums) // 2 # is_majority is True
Since
4
is greater than3.5
, we can confirm that3
is indeed a majority element in the arraynums
.
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
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.
Which of the following array represent a max heap?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Don’t Miss This!