0169_majority_element.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Majority Element - LeetCode 169</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#169</span> Majority Element</h1>
            <p>Find the element that appears more than ⌊n/2⌋ times using Boyer-Moore Voting.</p>
            <div class="problem-meta">
                <span class="meta-tag">Array</span>
                <span class="meta-tag">Divide and Conquer</span>
                <span class="meta-tag">Easy</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0169_majority_element/0169_majority_element.py</code>
            </div>

        </div>



        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Count how often each number appears and return the one with the highest count.</p>
            <ul>
                <li><strong>Count:</strong> Store each number's count in a hash map</li>
                <li><strong>Compare:</strong> Keep the number with the largest count</li>
                <li><strong>Return:</strong> That number is the majority element</li>
            </ul>
        </div>

        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            <div class="controls">
                <button id="stepBtn">Step</button>
                <button id="autoBtn">Auto Run</button>
                <button id="resetBtn">Reset</button>
            </div>
            <svg id="mainSvg" width="800" height="350"></svg>
            <div class="status-message" id="status">Click "Step" to find majority element</div>
        </div>

        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from collections import Counter


"""
LeetCode 169. Majority Element

Problem from LeetCode: https://leetcode.com/problems/majority-element/

Description:
Given an array nums of size n, return the majority element.

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.

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

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

Constraints:
- n == nums.length
- 1 &lt;= n &lt;= 5 * 10^4
- -10^9 &lt;= nums[i] &lt;= 10^9

Follow-up: Could you solve the problem in linear time and in O(1) space?
"""

class Solution:

    def majority_element(self, nums: list[int]) -&gt;int:
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num] += 1
        majority_entry = None
        for num, count in counts.items():
            if majority_entry is None or count &gt; counts[majority_entry]:
                majority_entry = num
        return majority_entry

    def majorityElement_counter(self, nums: list[int]) -&gt;int:
        counts = Counter(nums)
        return max(counts.keys(), key=counts.get)

    def majorityElement_boyer_moore(self, nums: list[int]) -&gt;int:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    nums1 = [3,2,3]
    print(f"Input: nums = {nums1}")
    print(f"Output (basic): {solution.majority_element(nums1)}")  # Expected output: 3
    print(f"Output (Counter): {solution.majorityElement_counter(nums1)}")  # Expected output: 3
    print(f"Output (Boyer-Moore): {solution.majorityElement_boyer_moore(nums1)}")  # Expected output: 3
    
    # Example 2
    nums2 = [2,2,1,1,1,2,2]
    print(f"\nInput: nums = {nums2}")
    print(f"Output (basic): {solution.majority_element(nums2)}")  # Expected output: 2
    print(f"Output (Counter): {solution.majorityElement_counter(nums2)}")  # Expected output: 2
    print(f"Output (Boyer-Moore): {solution.majorityElement_boyer_moore(nums2)}")  # Expected output: 2
</pre>
            </div>
        </div>
    </div>

    <script>
        const nums = [2, 2, 1, 1, 1, 2, 2];
        let candidate = null;
        let count = 0;
        let i = 0;

        const width = 800, height = 350;
        const svg = d3.select("#mainSvg");
        let autoTimer = null, autoRunning = false;

        function draw() {
            svg.selectAll("*").remove();
            const cellWidth = 60, startX = 150, startY = 80;

            svg.append("text").attr("x", width/2).attr("y", 30)
                .attr("text-anchor", "middle").attr("font-weight", "bold")
                .text("Boyer-Moore Voting Algorithm");

            // Draw array
            nums.forEach((num, idx) => {
                const x = startX + idx * cellWidth;
                let fill = "#e3f2fd", stroke = "#1976d2";
                if (idx === i) { fill = "#fef3c7"; stroke = "#f59e0b"; }
                else if (idx < i) { fill = num === candidate ? "#d1fae5" : "#fee2e2"; stroke = num === candidate ? "#10b981" : "#ef4444"; }

                svg.append("rect").attr("x", x).attr("y", startY)
                    .attr("width", cellWidth - 5).attr("height", 50).attr("rx", 8)
                    .attr("fill", fill).attr("stroke", stroke).attr("stroke-width", 2);

                svg.append("text").attr("x", x + (cellWidth-5)/2).attr("y", startY + 33)
                    .attr("text-anchor", "middle").attr("font-size", "22px")
                    .attr("font-weight", "bold").text(num);
            });

            // Pointer
            if (i < nums.length) {
                svg.append("text").attr("x", startX + i * cellWidth + (cellWidth-5)/2).attr("y", startY - 10)
                    .attr("text-anchor", "middle").attr("font-size", "12px").attr("fill", "#f59e0b")
                    .text("▼");
            }

            // Variables
            const varsY = 180;
            svg.append("rect").attr("x", 150).attr("y", varsY)
                .attr("width", 150).attr("height", 60).attr("rx", 10)
                .attr("fill", "#e8f5e9").attr("stroke", "#4caf50");
            svg.append("text").attr("x", 225).attr("y", varsY + 22)
                .attr("text-anchor", "middle").attr("font-size", "12px").text("Candidate:");
            svg.append("text").attr("x", 225).attr("y", varsY + 48)
                .attr("text-anchor", "middle").attr("font-size", "24px")
                .attr("font-weight", "bold").text(candidate !== null ? candidate : "?");

            svg.append("rect").attr("x", 350).attr("y", varsY)
                .attr("width", 150).attr("height", 60).attr("rx", 10)
                .attr("fill", "#e3f2fd").attr("stroke", "#1976d2");
            svg.append("text").attr("x", 425).attr("y", varsY + 22)
                .attr("text-anchor", "middle").attr("font-size", "12px").text("Count:");
            svg.append("text").attr("x", 425).attr("y", varsY + 48)
                .attr("text-anchor", "middle").attr("font-size", "24px")
                .attr("font-weight", "bold").text(count);

            // Result
            if (i >= nums.length) {
                svg.append("rect").attr("x", width/2 - 120).attr("y", 280)
                    .attr("width", 240).attr("height", 50).attr("rx", 12)
                    .attr("fill", "#d1fae5").attr("stroke", "#10b981").attr("stroke-width", 2);
                svg.append("text").attr("x", width/2).attr("y", 312)
                    .attr("text-anchor", "middle").attr("font-size", "20px")
                    .attr("font-weight", "bold").attr("fill", "#10b981")
                    .text(`Majority Element: ${candidate}`);
            }
        }

        function step() {
            if (i >= nums.length) return false;

            const num = nums[i];
            if (count === 0) {
                candidate = num;
                document.getElementById("status").textContent = `count=0, new candidate: ${num}`;
            }

            if (num === candidate) {
                count++;
                document.getElementById("status").textContent = `${num} = candidate, count++: ${count}`;
            } else {
                count--;
                document.getElementById("status").textContent = `${num} ≠ candidate, count--: ${count}`;
            }

            i++;
            draw();
            return i < nums.length;
        }

        function reset() {
            candidate = null; count = 0; i = 0;
            if (autoTimer) clearInterval(autoTimer);
            autoRunning = false;
            document.getElementById("autoBtn").textContent = "Auto Run";
            document.getElementById("status").textContent = 'Click "Step" to find majority element';
            draw();
        }

        function autoRun() {
            if (autoRunning) { clearInterval(autoTimer); autoRunning = false; document.getElementById("autoBtn").textContent = "Auto Run"; }
            else {
                autoRunning = true; document.getElementById("autoBtn").textContent = "Pause";
                autoTimer = setInterval(() => { if (!step()) { clearInterval(autoTimer); autoRunning = false; document.getElementById("autoBtn").textContent = "Auto Run"; } }, 700);
            }
        }

        document.getElementById("stepBtn").addEventListener("click", step);
        document.getElementById("autoBtn").addEventListener("click", autoRun);
        document.getElementById("resetBtn").addEventListener("click", reset);
        reset();
    </script>
</body>
</html>