𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

Leetcode 169 asks you to find the majority element in an array. The majority element appears more than n / 2 times. We assume it always exists.

You can solve this in two ways.

Approach 1: The Map Method

This method uses a Map to count how many times each number appears.

• Create a Map to store counts.
• Loop through the array.
• Update the count for each number.
• Loop through the Map to find the number with a count higher than n / 2.

Complexity:

• Time: O(n) because you use two sequential loops.
• Space: O(n) because the Map grows with the number of unique elements.

Approach 2: Boyer-Moore Voting Algorithm

This is an optimized way to solve the problem using constant memory.

Think of the numbers as opposing teams. Every time a number meets a different number, they cancel each other out. Since the majority element appears more than half the time, it will always be the last one standing.

How it works:

• Pick a candidate and set a count to 0.
• Loop through the array.
• If the count is 0, set the current number as the candidate.
• If the current number matches the candidate, increase the count by 1.
• If it does not match, decrease the count by 1.

Complexity:

• Time: O(n) because you only pass through the array once.
• Space: O(1) because you only use two variables.

Why it matters:

Both methods have a time complexity of O(n). However, the second approach uses much less memory. It does not need a Map. This makes it better for large datasets.

Source: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6