Majority Element - I

Given an array of size n, find the element that appears more than n/2 times.

Example

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

Output: 2

---

Approach 1: Brute Force

For every element, count its occurrences in the entire array.

Intuition

Check each number and calculate its frequency. If frequency becomes greater than n/2, return it.

Java Code

class Solution {
    public int majorityElement(int[] nums) {

        int n = nums.length;

        for(int i = 0; i < n; i++) {

            int count = 0;

            for(int j = 0; j < n; j++) {
                if(nums[i] == nums[j]) {
                    count++;
                }
            }

            if(count > n / 2) {
                return nums[i];
            }
        }

        return -1;
    }
}

Complexity

• Time: O(n²)
• Space: O(1)

---

Approach 2: Better Solution (HashMap)

Intuition

Store the frequency of every element in a HashMap and return the element whose frequency exceeds n/2.

Java Code

class Solution {
    public int majorityElement(int[] nums) {

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for(int key : map.keySet()) {
            if(map.get(key) > nums.length / 2) {
                return key;
            }
        }

        return -1;
    }
}

Complexity

• Time: O(n)
• Space: O(n)

---

Approach 3: Optimal Solution (Moore's Voting Algorithm)

Key Observation

The majority element appears more than half the time.

If we keep canceling one majority element with one non-majority element, the majority element will still survive.

Think of it as:

Same Element      -> +1 vote
Different Element -> -1 vote

---

Dry Run

[2,2,1,1,1,2,2]

Element	Candidate	Count
2	2	1
2	2	2
1	2	1
1	2	0
1	1	1
2	1	0
2	2	1

Final Candidate = 2

---

Optimal Java Code

class Solution {
    public int majorityElement(int[] nums) {

        int candidate = 0;
        int count = 0;

        for(int num : nums) {

            if(count == 0) {
                candidate = num;
            }

            if(num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

Complexity

• Time: O(n)
• Space: O(1)

---

Interview Takeaway

Approach	Time	Space
Brute Force	O(n²)	O(1)
HashMap	O(n)	O(n)
Moore's Voting	O(n)	O(1)

The beauty of Moore's Voting Algorithm is that it achieves linear time with constant space by repeatedly canceling out different elements. Since the majority element occurs more than n/2 times, it can never be completely eliminated and must remain as the final candidate.

I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.

LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
X (Twitter): https://x.com/Jaspree54799902
GitHub: https://github.com/codewithjaspreet