**Explanation**

There are many ways to solve this problem such as sorting *nums* and returning nums[n/2], using a dictionary to store the frequency of each distinct integer in *nums*, but I will show you a way to solve this problem that runs strictly in O(n) with O(1) space.

```
/* Simple Example */
/* We start off with a simple example to illustrate the code's logic */
int [] nums = { 2, 1, 2, 2 };
/* 1. Set majorityElementSoFar to be nums[0], which is 2, count to be 1. */
int majorityElementSoFar = nums[0]; // 2
int count = 1;
/* 2. Check nums[1]. Since is NOT equal to majorityElementSoFar AND
* count - 1 would be 0, we need to set majorityElementSoFar to be
* nums[1], which is 1.
*/
assert(nums[1] != majorityElementSoFar && count - 1 == 0);
majorityElementSoFar = nums[1]; // 1
/* 3. Check nums[2]. Since it is NOT equal to majorityElementSoFar AND
* count - 1 would be 0, we need to set majortyElementSoFar to be
* nums[2], which is 2.
*/
assert(nums[2] != majorityElementSoFar && count - 1 == 0);
majorityElementSoFar = nums[2]; // 2
/* 4. Check nums[3]. Since it IS equal to majorityElementSoFar, we
* increment count by 1.
*/
assert(nums[3] == majorityElementSoFar);
count++;
/* 5. Return majorityElementSoFar as our solution. */
return majorityElementSoFar; // 2
```

The idea behind this solution is take advantage of the fact that the majority element appears **more** than ⌊ n/2 ⌋ times. As long as we keep track of the majority element so far, with the help of a *count* variable, regardless of how many times *majoritySoFar* is reset again and again, we are guaranteed to have *majorityElementSoFar* equal to the actual majority element by the end.

**Time Complexity**

The time complexity is O(n) where n is the number of elements in input *nums*, since we scan through every element in nums once.

```
class Solution {
public int majorityElement(int[] nums) {
// Initially set the first element of nums to be majority
int majorityElementSoFar = nums[0];
int count = 1;
// Scan sequentially from the second element onwards
for (int i = 1; i < nums.length; i++) {
if (nums[i] == majorityElementSoFar) {
count++;
}
// Need to set a new majorityElementSoFar
else if (count == 1) {
majorityElementSoFar = nums[i];
}
// Decrement count with no repercussions
else {
count--;
}
}
return majorityElementSoFar;
}
}
```