Problem Description

You are given an integer array nums that is sorted in non-decreasing order (ascending order) and an integer target. Your task is to determine whether target is a majority element in the array.

A majority element is defined as an element that appears more than nums.length / 2 times in the array. In other words, the element must occur more than half the total number of elements in the array to be considered a majority element.

Return true if target is a majority element, otherwise return false.

Since the array is sorted, all occurrences of any element will be consecutive. The solution leverages binary search to efficiently find the leftmost and rightmost positions of target in the array. By using bisect_left to find the first occurrence and bisect_right to find the position just after the last occurrence, we can calculate the count of target as right - left. If this count is greater than len(nums) // 2, then target is a majority element.

Intuition

The key insight comes from recognizing that the array is sorted in non-decreasing order. In a sorted array, all occurrences of the same element must be grouped together consecutively. This means if target appears in the array, all its occurrences form a continuous segment.

To check if target is a majority element, we need to count how many times it appears. A naive approach would be to iterate through the entire array and count occurrences, which takes O(n) time. However, since the array is sorted, we can do better.

Instead of counting element by element, we can find the boundaries of where target appears in the array. If we know the leftmost position where target starts and the rightmost position where it ends, we can calculate the count directly as the difference between these positions.

Binary search is perfect for this because:

1. We can use binary search to find the first occurrence of target (leftmost position)
2. We can use binary search to find the first element greater than target (which gives us the position right after the last occurrence)
3. The difference between these two positions gives us the exact count of target

This approach reduces our time complexity from O(n) to O(log n) for finding both boundaries. Once we have the count, we simply check if it's greater than len(nums) // 2 to determine if target is a majority element.

The elegance of this solution lies in transforming a counting problem into a boundary-finding problem, leveraging the sorted nature of the array to achieve logarithmic time complexity.

Learn more about Binary Search patterns.

Solution Approach

The solution leverages Python's bisect module which provides efficient binary search operations on sorted sequences. Here's how the implementation works:

Step 1: Find the leftmost position of target

left = bisect_left(nums, target)

bisect_left(nums, target) returns the leftmost position where target should be inserted to keep the array sorted. If target exists in the array, this gives us the index of its first occurrence. If target doesn't exist, it returns the position where it would be inserted.

Step 2: Find the position after the rightmost occurrence

right = bisect_right(nums, target)

bisect_right(nums, target) returns the rightmost position where target should be inserted to keep the array sorted. If target exists, this gives us the index immediately after its last occurrence. If target doesn't exist, it returns the same position as bisect_left.

Step 3: Calculate the count and check majority condition

return right - left > len(nums) // 2

The count of target in the array is right - left. We check if this count is greater than len(nums) // 2 (integer division for the floor value).

Example walkthrough:

• For nums = [2, 4, 5, 5, 5, 5, 5, 6, 6] and target = 5:
  • bisect_left(nums, 5) returns 2 (first occurrence of 5)
  • bisect_right(nums, 5) returns 7 (position after last 5)
  • Count = 7 - 2 = 5
  • Array length = 9, so 9 // 2 = 4
  • Since 5 > 4, return true

Edge cases handled:

• If target doesn't exist in the array, both left and right will be the same value, making right - left = 0, which correctly returns false
• The solution works for arrays of any size, including single-element arrays

Time Complexity: O(log n) for two binary search operations Space Complexity: O(1) as we only use constant extra space

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: nums = [1, 2, 3, 3, 3, 3, 4], target = 3

Step 1: Find the leftmost position of target (3) Using binary search to find where 3 first appears:

• Initial array: [1, 2, 3, 3, 3, 3, 4]
• Indices: [0, 1, 2, 3, 4, 5, 6]
• bisect_left(nums, 3) performs binary search:
  • Middle element at index 3 is 3, but we need the leftmost 3
  • Search continues in left half
  • Finds first 3 at index 2
• Result: left = 2

Step 2: Find the position after the rightmost occurrence of target (3) Using binary search to find where we'd insert a value just greater than 3:

• bisect_right(nums, 3) performs binary search:
  • Looks for the position after the last 3
  • Finds that index 6 (where 4 is) is the first position greater than 3
• Result: right = 6

Step 3: Calculate count and check majority

• Count of target: right - left = 6 - 2 = 4
• Array length: 7
• Majority threshold: 7 // 2 = 3
• Is 4 > 3? Yes!
• Return: true

The target 3 appears 4 times in an array of length 7, which is more than half the array size, making it a majority element.

Visual representation:

Array:  [1, 2, 3, 3, 3, 3, 4]
Index:   0  1  2  3  4  5  6
              ↑           ↑
            left        right
         (first 3)   (after last 3)
Count = 6 - 2 = 4 occurrences of 3

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(log n), where n is the length of the array nums. This is because the algorithm uses two binary search operations (bisect_left and bisect_right) to find the leftmost and rightmost positions of the target element in the sorted array. Each binary search operation takes O(log n) time, and since we perform two binary searches sequentially, the overall time complexity remains O(log n) (as O(log n) + O(log n) = O(log n)).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space to store the variables left and right, regardless of the input size. The binary search operations are performed in-place without requiring additional space proportional to the input size.

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

Common Pitfalls

1. Misunderstanding the Majority Element Definition

A common mistake is checking if the count equals n/2 instead of checking if it's strictly greater than n/2. The majority element must appear more than half the times, not exactly half or at least half.

Incorrect Implementation:

# Wrong: checking >= instead of >
return right - left >= len(nums) // 2

Correct Implementation:

# Correct: strictly greater than n/2
return right - left > len(nums) // 2

2. Not Handling Empty Arrays

While the bisect functions handle empty arrays gracefully (both return 0), it's good practice to explicitly handle this edge case for clarity and to avoid unnecessary operations.

Enhanced Solution:

def isMajorityElement(self, nums: List[int], target: int) -> bool:
    if not nums:  # Handle empty array
        return False
  
    left = bisect_left(nums, target)
    right = bisect_right(nums, target)
    return right - left > len(nums) // 2

3. Confusion Between bisect_left and bisect_right

Developers sometimes confuse which function to use or attempt to use bisect_left for both boundaries, leading to off-by-one errors.

Incorrect Approach:

# Wrong: using bisect_left for both boundaries
left = bisect_left(nums, target)
right = bisect_left(nums, target + 1)  # This works but is less intuitive

Better Approach:

# Clear and intuitive
left = bisect_left(nums, target)   # First occurrence
right = bisect_right(nums, target)  # After last occurrence

4. Manual Binary Search Implementation Errors

Some developers try to implement binary search manually instead of using the bisect module, leading to boundary condition errors.

Error-Prone Manual Implementation:

def findLeft(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1  # Easy to mess up boundaries
    return left

Recommended Solution: Use Python's built-in bisect module which is well-tested and optimized. If manual implementation is required, carefully test boundary conditions.

5. Integer Division vs Float Division

Using float division (/) instead of integer division (//) can cause issues when comparing with the count.

Incorrect:

# Wrong: float division might cause comparison issues
return right - left > len(nums) / 2

Correct:

# Correct: integer division for proper comparison
return right - left > len(nums) // 2