Top Interview 150

Identifying the majority element in an array is a classic problem that is both elegant and efficient when solved using the right approach. In this post, we’ll explore LeetCode 169: Majority Element, along with its optimal solution in JavaScript.

🚀 Problem Description

You are given an array nums of size n. The majority element is the element that appears more than ⌊n/2⌋ times.
You may assume that the majority element always exists in the array.

💡 Examples

Example 1

Input: nums = [3,2,3]  
Output: 3

Example 2

Input: nums = [2,2,1,1,1,2,2]  
Output: 2

🏆 JavaScript Solution

The Boyer-Moore Voting Algorithm is an optimal solution for this problem. It runs in O(n) time and uses O(1) space.

var majorityElement = function(nums) {
    let candidate = null;
    let count = 0;

    // Identify the majority candidate
    for (let num of nums) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }

    return candidate;
};

🔍 How It Works

1. Candidate Selection:

   • Traverse the array while maintaining a count.
   • If the count reaches 0, reset the candidate to the current element.

2. Guaranteed Majority:

   • Since the problem guarantees that a majority element always exists, the candidate identified will be the majority element.

🔑 Complexity Analysis

• Time Complexity: O(n), where n is the size of the array.
• Space Complexity: O(1), since no extra data structures are used.

📋 Dry Run

Input: nums = [2,2,1,1,1,2,2]

Output: 2

✨ Pro Tips for Interviews

1. Explain the guarantee: Clarify that the problem ensures a majority element exists, simplifying the solution.
2. Handle edge cases: Be ready to discuss scenarios like single-element arrays.
3. Highlight efficiency: Emphasize the O(1) space usage of the Boyer-Moore algorithm.

📚 Learn More
For a detailed walkthrough and code explanation, check out my Dev.to post:
👉 Remove Duplicates from Sorted Array II - JavaScript Solution

Let me know your thoughts! How would you solve this? 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving