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 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:


2. Traverse the array while maintaining a count.



3. If the count reaches 0, reset the candidate to the current element.




4. 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]

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

JavaScript #LeetCode #CodingInterview #ProblemSolving