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 A