# Short Java, generalizes with O(N) time and O(k) space

• I felt like torturing myself, so I rewrote my Python 6/7-liner in Java. If you want an explanation, please look there. Compared to Python it's awfully long and complicated, but for a Java solution I think it's fairly short. To generalize for the problem of searching elements appearing more than ⌊N/k⌋ times, just replace `3` by `k`.

``````public List<Integer> majorityElement(int[] nums) {
HashMap<Integer,Integer> ctr = new HashMap();

// Find up to two candidates
for (int n : nums) {
ctr.put(n, ctr.getOrDefault(n, 0) + 1);
if (ctr.size() == 3)
for (int c : new HashSet<Integer>(ctr.keySet()))
if (ctr.get(c) == 1)
ctr.remove(c);
else
ctr.put(c, ctr.get(c) - 1);
}

// Count the votes for the candidates
for (int c : ctr.keySet())
ctr.put(c, 0);
for (int n : nums)
if (ctr.containsKey(n))
ctr.put(n, ctr.get(n) + 1);

// Determine the actual winners
return ctr.keySet().stream()
.filter(c -> ctr.get(c) > nums.length / 3)
.collect(Collectors.toList());
}``````

• I was writing some generalized solution as well, when I realized... if we are going to use a map anyway... why don't we just store all elements and count them? It will be almost same time/space complexity, right?

• Similar, but O(N) space instead of O(k) space. And presumably k is (much) smaller than N.

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