Majority Element

easy

Given an array nums of size n, return the majority element — the element that appears more than ⌊n / 2⌋ times.

You may assume that the majority element always exists in the array.

Test Cases

Copy an input into the main harness and Run to verify

Input

nums = [3,2,3]

Expected Output

3

Input

nums = [2,2,1,1,1,2,2]

Expected Output

2

Explanation: 2 appears four times out of seven, which is more than 7 / 2 = 3.

Hint 1 — click to reveal

Counting with a hash map is the obvious O(n) time, O(n) space answer.

Hint 2 — click to reveal

Can you do it in O(1) space? Think about pairing off different elements and cancelling them.

Java Compiler