DEV Community

Cover image for LeetCode Challenge: 169. Majority Element - JavaScript Solution 🚀
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on • Edited on

2 1 1 1 1

LeetCode Challenge: 169. Majority Element - JavaScript Solution 🚀

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
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: nums = [2,2,1,1,1,2,2]  
Output: 2
Enter fullscreen mode Exit fullscreen mode

🏆 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;
};
Enter fullscreen mode Exit fullscreen mode

🔍 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]

Majority Elements

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

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (1)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up