Majority Element (Boyer–Moore Vote)

Easy · Arrays & Strings · about 10 minutes

Asked at Amazon, Google, Apple.

One value in nums (length n) occupies more than ⌊n / 2⌋ of the positions, and it is guaranteed to exist. Find it in O(n) time while using only O(1) extra memory.