Majority Element

1. Get the size of the array, n.
2. Use an outer loop to iterate from i = 0 to n-1.
3. Inside the outer loop, select nums[i] as the candidate and initialize count = 0.
4. Use an inner loop to iterate from j = 0 to n-1.
5. Inside the inner loop, if nums[j] is equal to the candidate nums[i], increment count.
6. After the inner loop completes, check if count > n / 2.
7. If the condition is true, return the candidate nums[i].

The brute force method uses two nested loops. The outer loop picks an element from the array as a potential candidate for the majority element. The inner loop then iterates through the entire array to count the occurrences of this candidate element.

If the count for any candidate becomes greater than n/2, that candidate is the majority element, and we can return it immediately. Since the problem guarantees that a majority element always exists, this process will always find and return the correct element.

1class Solution {2    public int majorityElement(int[] nums) {3        int n = nums.length;4        for (int i = 0; i < n; i++) {5            int count = 0;6            for (int j = 0; j < n; j++) {7                if (nums[j] == nums[i]) {8                    count++;9                }10            }11            if (count > n / 2) {12                return nums[i];13            }14        }15        // This part is unreachable given the problem constraints16        // but is needed for the compiler.17        return -1; 18    }19}

1. Sort the input array nums in non-decreasing order.
2. The majority element is guaranteed to be at the index n/2.
3. Return the element nums[n/2].

The intuition behind this approach is that if an element occurs more than n/2 times in an array, it will always be the middle element when the array is sorted. Let's consider an array of size n. If we sort it, the element at index n/2 (using 0-based indexing) is the median. Since the majority element appears more than n/2 times, it must occupy this median position.

For example, in [2,2,1,1,1,2,2], n=7. n/2 is 3. After sorting, we get [1,1,1,2,2,2,2]. The element at index 3 is 2, which is the majority element.

1import java.util.Arrays;2 3class Solution {4    public int majorityElement(int[] nums) {5        Arrays.sort(nums);6        return nums[nums.length / 2];7    }8}

1. Create a HashMap to store elements as keys and their frequencies as values.
2. Iterate through the input array nums.
3. For each num, update its frequency in the hash map.
4. After the first loop, iterate through the entries of the hash map.
5. For each entry, check if its value (frequency) is greater than n/2.
6. If it is, return the key corresponding to that entry.

We can find the majority element by counting the occurrences of each element in the array. A hash map is an ideal data structure for this task, as it provides average O(1) time complexity for insertions and lookups.

We traverse the input array nums. For each element, we update its count in the hash map. If the element is not yet in the map, we add it with a count of 1. If it's already present, we increment its count.

After populating the map, we can iterate through its entries to find which element has a count greater than n/2. Since a majority element is guaranteed to exist, we will surely find one.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int majorityElement(int[] nums) {6        Map<Integer, Integer> counts = new HashMap<>();7        for (int num : nums) {8            counts.put(num, counts.getOrDefault(num, 0) + 1);9        }10 11        int n = nums.length;12        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {13            if (entry.getValue() > n / 2) {14                return entry.getKey();15            }16        }17        18        // Unreachable code given problem constraints19        return -1;20    }21}

1. Initialize count = 0 and candidate = null.
2. Iterate through each element num in the array nums.
3. If count is 0, set candidate = num.
4. If num is equal to candidate, increment count. Otherwise, decrement count.
5. After the loop finishes, candidate will hold the majority element. Return candidate.

The Boyer-Moore Voting Algorithm is a clever and efficient method for finding the majority element. The core idea is based on the fact that the majority element occurs more than n/2 times. This means it appears more often than all other elements combined.

The algorithm maintains two variables: a candidate for the majority element and a count. We iterate through the array.

• If count is 0, we choose the current element as the new candidate.
• If the current element is the same as the candidate, we increment count.
• If the current element is different, we decrement count.

Essentially, we are pairing up each occurrence of the majority element with an occurrence of a non-majority element. Since the majority element is more frequent, it will be the last one standing as the candidate.

Because the problem guarantees that a majority element always exists, the final candidate will be the answer. If there was no guarantee, a second pass would be needed to verify if the candidate's count is actually greater than n/2.

1class Solution {2    public int majorityElement(int[] nums) {3        int count = 0;4        Integer candidate = null;5 6        for (int num : nums) {7            if (count == 0) {8                candidate = num;9            }10            count += (num == candidate) ? 1 : -1;11        }12 13        return candidate;14    }15}