Refer to Boyer-Moore Majority Vote Algorithm, it has O(N) time and O(1) space. Marvelous!
There is a wonderful article talking about the algorithm: Majority Voting Algorithm - Blog of Greg Grothaus
# Using Boyer-Moore Majority Voting Algorithm def majority_element(nums) candidate = nil count = 0 # first round to find candidate nums.each do |ele| candidate = ele if count == 0 if candidate == ele count += 1 else count -= 1 end end # second round to confirm count = 0 nums.each do |ele| count += 1 if ele == candidate end count > nums.count/2 ? candidate : nil end