Majority element using divide&conquer

Question

I want to find the majority element from a list using divide & conquer algorithm.

I saw this code on Leetcode with this solution:

class Solution:
def majorityElement(self, nums, lo=0, hi=None):
    def majority_element_rec(lo, hi):
        # base case; the only element in an array of size 1 is the majority
        # element.
        if lo == hi:
            return nums[lo]

        # recurse on left and right halves of this slice.
        mid = (hi-lo)//2 + lo
        left = majority_element_rec(lo, mid)
        right = majority_element_rec(mid+1, hi)

        # if the two halves agree on the majority element, return it.
        if left == right:
            return left

        # otherwise, count each element and return the "winner".
        left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)
        right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)

        return left if left_count > right_count else right

    return majority_element_rec(0, len(nums)-1)

when there is a majority element, the result is right but when there is not such an element, it returns the wrong result.

I tried to change the return statement to:

    if left_count > right_count:
        return left
    elif left_count < right_count:
        return right
    else:
        return -1

so it returns -1 when there is no right answer. When the input is [1,2,1,3] the result is -1(right answer) but when the input is [1,2,3,3] the output is 3 which is wrong.

It seems that everyone use this solution but it isn't working. Any ideas about how to fix it?

TIA

Answer 1

I think the recursive step is OK since if there is a majority element, it must be the majority element of at least one of the halves of the array, and the recursive step will find it. If there is no majority element the recursive algorithm will still return a (wrong) candidate.

If you want the program to detect if the element is indeed the majority element, I would just change the final step.

def majorityElement(self, nums):
    ...
    candidate = majority_element_rec(0, len(nums)-1)
    if nums.count(candidate) > len(nums)//2:
        return count
    else:
        return -1

Alternatively the recursive step could perform the same check whether the found candidate is indeed a majority element by replacing the last line:

return left if left_count > right_count else right

with

majority = ((hi - lo) + 1) / 2
if left_count > majority:
     return left
if right_count > majority:
     return right
return -1

This should still work because the majority element if it exists must be the majority element in one half of the array recursively and must thus still propagate.