Given an array, nums, having $n$ integers, return the majority element. An element will be considered a majority element if it occurs more than $⌊n / 2⌋$ times in the array.

Note: It is safe to assume that the majority element always exists in the array.

Constraints

• $n ==$ nums.length
• $1\leq n\leq 3 * 10^3$
• $−10^4 \leq$ nums[i] $\leq10^4$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Implement your solution in the following coding playground: