This Majority Counting Problem is Asked by Facebook

You may often hear the term “majority” in relation to voting, whether it’s in a country’s presidential election or choosing a group leader for your class projects. This vote is based on who receives the most votes, or in other words, who has the majority of votes, will be the leader or president.

By counting the ballots or raised hands, you can determine that X has the most votes and should be the leader. However, when dealing with a large number of participants and various selections, it can be easy to lose track of the current count of X’s votes.

Today’s problem was asked by Facebook.

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Additional question: Can you implement a solution with the time complexity of O(n) with the space complexity of O(1)?

There are many ways to solve this problem, one way is that to sort the items, and return the middle element of it. However, this approach only works because it’s guaranteed that majority of elements exist. With sorting, it also comes with time complexity of O(N log(N)) and space complexity of O(1).

There’s other approach where you can do it with O(N) that is using Boyer–Moore. The algorithm works as following:

• Initialize an element m and a counter c with c = 0
• For each element x of the input sequence:
• If c = 0, then assign m = x and c = 1
• else if m = x, then assign c = c + 1
• else assign c = c − 1
• Return m

source: Wikipedia — Boyer-More Majority Vote Algorithm

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Time Complexity: O(N log (N)) | Space Complexity: O(1)
        # nums.sort() # in-place sorting 
        # return nums[len(nums)//2]
        # Time Complexity: O(N) | Space Complexity: O(1) -> Boyer-Moore Voting Algorithm
        m, c = 0, 0
        for num in nums:
            if c == 0:
                m = num
                c += 1
            elif m == num:
                c += 1
            else:
                c -= 1
        
        return m