O(n) Java solution using Hashtable

  • 2

    I'm not sure why I'm getting times ranging from 400-550, I figured this would be faster than a simple two line sorting solution. Here it is:

    import java.util.Hashtable;
    public class Solution {
        public int majorityElement(int[] nums) {
            if (nums.length < 2) return nums[0];
            Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>(); 
            for (int i = 0; i < nums.length; i++) {
                if (table.containsKey(nums[i])) {
                    table.put(nums[i], table.get(nums[i])+1);
                    if (table.get(nums[i]) > (nums.length) / 2) return nums[i];
                else table.put(nums[i], 1);
          return 0;  

  • -1

    This post is deleted

  • 0

    The question says "You may assume that the array is non-empty and the majority element always exist in the array," so there will always be a majority element. [0,1] would not be a test case.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.