Jobs

Interviews

Discussions

Check If a Number Is Majority Element in a Sorted Array

Easy

Asked by:

3 views

Topics:

ArraysBinary Search

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element in nums, or false otherwise.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation:
The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

Example 2:

Input: nums = [10,100,101,101], target = 101
Output: false
Explanation:
The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i], target <= 1000

Try coding it in LeetCode

Check If a Number Is Majority Element in a Sorted Array

Easy

Asked by:

3 views

Topics:

ArraysBinary Search

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element in nums, or false otherwise.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation:
The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

Example 2:

Input: nums = [10,100,101,101], target = 101
Output: false
Explanation:
The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i], target <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible integer values in the `nums` array and for the `target`?
Can the input array `nums` be empty or null?
If the target element is not present in the array at all, should I return `false`?
If the target element appears exactly `nums.length / 2` times, should I return `false` since it needs to be *more than* `nums.length / 2`?
Is `nums.length` guaranteed to be within the range of a standard integer, or could it be larger?

Brute Force Solution

Approach

The brute force approach to this problem involves counting how many times the given number appears in the collection of numbers. We then check if that count is more than half the size of the collection. If it is, then it's a majority element, and if not, it isn't.

Here's how the algorithm would work step-by-step:

Go through each number in the collection one by one.
For each number, count how many times the given number is equal to the current number you're looking at.
Once you've gone through all the numbers, see if the total count of the given number is more than half the total numbers in the collection.
If the count is more than half, then the given number is a majority element.
If the count is not more than half, then the given number is not a majority element.

Code Implementation

def is_majority_element_brute_force(numbers, target_number):
    target_number_count = 0

    for current_number in numbers:
        if current_number == target_number:
            target_number_count += 1

    # Check if the number appears more than half the time

    if target_number_count > len(numbers) / 2:
        return True

    # If we've made it here, it's not a majority
    return False

Big(O) Analysis

Time Complexity

O(n) – The given approach iterates through each of the n elements in the input array. For each element, it compares it with the target number and increments a counter if they are equal. This comparison operation takes constant time, O(1). Since the loop iterates through all n elements, the total number of comparisons is proportional to n. Therefore, the overall time complexity of this approach is O(n).

Space Complexity

O(1) – The provided brute force approach iterates through the input array but only uses a counter variable to keep track of the occurrences of the target number. The algorithm doesn't create any auxiliary data structures that scale with the input size N (the size of the collection). Therefore, the space complexity is constant and independent of the input array's size.

Optimal Solution

Approach

The key to solving this efficiently is recognizing the input is sorted. Instead of checking every element, we leverage the sorted nature to quickly find the first and last occurrences of our target number, allowing us to count its occurrences efficiently.

Here's how the algorithm would work step-by-step:

First, find the very first spot where the number shows up in the sorted list.
Next, find the very last spot where the number shows up in the sorted list.
Once you know the start and end positions, it's easy to figure out exactly how many times the number appears.
Finally, check if this count is more than half the total number of items in the list. If it is, then it's a majority element.

Code Implementation

def is_majority_element(numbers, target):
    array_length = len(numbers)

    first_occurrence = find_first_occurrence(numbers, target)

    if first_occurrence == -1:
        return False

    if numbers[first_occurrence + array_length // 2] == target:
        # Check if element at majority index equals target.
        return True

    return False

def find_first_occurrence(numbers, target):
    left_index = 0
    right_index = len(numbers) - 1
    first_occurrence_index = -1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2

        if numbers[middle_index] == target:
            # Potential first occurrence, narrow search to the left
            first_occurrence_index = middle_index
            right_index = middle_index - 1

        elif numbers[middle_index] < target:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return first_occurrence_index

Big(O) Analysis

Time Complexity

O(log n) – The solution uses binary search to find the first and last occurrences of the target number in the sorted array. Binary search has a time complexity of O(log n). Since we perform binary search twice (once for the first occurrence and once for the last occurrence), the overall time complexity remains O(log n) because constant factors are ignored in Big O notation. The check to see if the count is greater than n/2 is constant time and doesn't affect the overall complexity.

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It primarily involves storing a few integer variables to track the first and last occurrences of the target number within the sorted array. The amount of space required for these variables does not depend on the input size, N, (the number of elements in the array). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since there are no elements to satisfy the majority condition.
Array with one element and target matches that element	Return true since the target appears once, and length/2 is 0, so 1 > 0.
Array with one element and target does not match	Return false, since the target is not present and cannot be a majority.
Target is smaller than the smallest element in the array	The number of occurrences will be zero; hence, return false.
Target is larger than the largest element in the array	The number of occurrences will be zero; hence, return false.
Target appears exactly n/2 times (where n is the array length)	Return false since it needs to be strictly more than n/2.
Large array size (potential integer overflow in calculations of n/2)	Use long or handle the division with appropriate data types to avoid overflow.
Target is present at the beginning of the array	The algorithm should still correctly calculate the frequency regardless of where the target appears.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible integer values in the `nums` array and for the `target`?
Can the input array `nums` be empty or null?
If the target element is not present in the array at all, should I return `false`?
If the target element appears exactly `nums.length / 2` times, should I return `false` since it needs to be *more than* `nums.length / 2`?
Is `nums.length` guaranteed to be within the range of a standard integer, or could it be larger?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each number in the collection one by one.
For each number, count how many times the given number is equal to the current number you're looking at.
Once you've gone through all the numbers, see if the total count of the given number is more than half the total numbers in the collection.
If the count is more than half, then the given number is a majority element.
If the count is not more than half, then the given number is not a majority element.

Code Implementation

def is_majority_element_brute_force(numbers, target_number):
    target_number_count = 0

    for current_number in numbers:
        if current_number == target_number:
            target_number_count += 1

    # Check if the number appears more than half the time

    if target_number_count > len(numbers) / 2:
        return True

    # If we've made it here, it's not a majority
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the very first spot where the number shows up in the sorted list.
Next, find the very last spot where the number shows up in the sorted list.
Once you know the start and end positions, it's easy to figure out exactly how many times the number appears.
Finally, check if this count is more than half the total number of items in the list. If it is, then it's a majority element.

Code Implementation

def is_majority_element(numbers, target):
    array_length = len(numbers)

    first_occurrence = find_first_occurrence(numbers, target)

    if first_occurrence == -1:
        return False

    if numbers[first_occurrence + array_length // 2] == target:
        # Check if element at majority index equals target.
        return True

    return False

def find_first_occurrence(numbers, target):
    left_index = 0
    right_index = len(numbers) - 1
    first_occurrence_index = -1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2

        if numbers[middle_index] == target:
            # Potential first occurrence, narrow search to the left
            first_occurrence_index = middle_index
            right_index = middle_index - 1

        elif numbers[middle_index] < target:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return first_occurrence_index

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since there are no elements to satisfy the majority condition.
Array with one element and target matches that element	Return true since the target appears once, and length/2 is 0, so 1 > 0.
Array with one element and target does not match	Return false, since the target is not present and cannot be a majority.
Target is smaller than the smallest element in the array	The number of occurrences will be zero; hence, return false.
Target is larger than the largest element in the array	The number of occurrences will be zero; hence, return false.
Target appears exactly n/2 times (where n is the array length)	Return false since it needs to be strictly more than n/2.
Large array size (potential integer overflow in calculations of n/2)	Use long or handle the division with appropriate data types to avoid overflow.
Target is present at the beginning of the array	The algorithm should still correctly calculate the frequency regardless of where the target appears.