Majority Element🏎

Question

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

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

Example 2:

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

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

Java Solution

Four different solutions with 4 different time/space complexities

O(n²)
For each element going through the whole array, so O(n²)

Code

O(n)
Going through the whole array only once, so O(n)

Code

O(n log n)
Sorting takes O(n log n) time to sort the list, so O(n log n)

Code

O(n) && O(1) for space complexity
Going through the array only once, and maintaining the space constant by not using any extra array or hashmap with the help of the Boyer-Moore Voting Algorithm ( yeah I also can’t pronounce it)

Code