[📝LeetCode #169] Majority Element

#leetcode #100daysofcode #java #array

🎀 The Problem

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:

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

👩‍💻 My Answer

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

Pro & Con

✅ Super short
🔺 Runtime & Memory
🔺 Not sure I can use Arrays.sort()

💋 Ideal (another) Answer

Approach - "Hash Table"

Tbh, I was quite satisfied with my Sorting method. It's only 2 lines and a unique approach. But I watched the YouTube video about this question.

It is the interview favorite question because it has many methods to solve, and the interviewers can prompt the interviewees to come up with more and more solutions.

Here is the link to the YouTube video that motivates me to learn other methods. I DO recommend watching this;))))
Nikhil Lohia's Merge Sorted Array Explanation

New Code

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap();
        int frequency = -1, i = 0, num = 0;

        if (nums.length == 1)
            return nums[0];

        while (frequecy == -1 || frequency < nums.length/2.0 && i < nums.length) {
            num = nums[i];

            if(!map.containsKey(num))
                map.put(num, 1);
            else {
                frequency = map.get(num)+1;
                map.replace(num, frequency);
            }
            i++;
        }

        return num;
    }
}

BUT it still beats 22% <<<<<< 100%. So, I found the 100% BEAT code in the solution on LeetCode. Here is the code:

class Solution {
    public int majorityElement(int[] nums) {
    int count=0, ret = 0;

    for (int num: nums) {
        if (count == 0) // if the number never appeared before
            ret = num;

        if (num != ret)
            count--;
        else
            count++;
    }

    return ret;
}
}

💡 What I Learned

How to use HashMap in java:

HashMap<Integer, Integer> map = new HashMap();
map.replace(KEY, NEW_VALUE);
map.containsKey(num);

How to categorize number type in java

3/2 -> 1
3/2.0 -> 1.5

DEV Community