January 23, 2026 (12d ago)

Basic Hashing

Highest Occurring Element in an Array

class Solution {
    public int mostFrequentElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
		
        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
		
        int maxFreq = 0;
        int candidate = -1;
        for (Map.Entry<Integer, Integer> itr : map.entrySet()) {
            int e = itr.getKey();
            int freq = itr.getValue();
			
            if (freq > maxFreq) {
                candidate = e;
                maxFreq = freq;
            } else if (freq == maxFreq && e < candidate) {
                candidate = e;
            }
        }
		
        return candidate;
    }
}

The algorithm uses a hash map to count the frequency of each element in the array. After populating the map, it iterates through the map's entries to find the element with the highest frequency. A tie is broken by choosing the smaller element.

Time Complexity: O(n), where n is the number of elements. This is because it iterates through the array once to build the map and once through the unique elements in the map (which is at most n).

Space Complexity: O(k), where k is the number of unique elements in the array, for storing the frequency map.

Second Highest Occurring Element

class Solution {
    public int secondMostFrequentElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (var x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
		
        int candidate1 = -1, candidate2 = -1;
        int freq1 = 0, freq2 = 0;
        for (var entry : map.entrySet()) {
            int e = entry.getKey();
            int freq = entry.getValue();
			
            if (freq1 < freq) {
                candidate2 = candidate1;
                freq2 = freq1;
                candidate1 = e;
                freq1 = freq;
            } else if (freq1 == freq) {
                candidate1 = Math.min(candidate1, e);
            } else if (freq2 < freq) {
                candidate2 = e;
                freq2 = freq;
            } else if (freq2 == freq) {
                candidate2 = Math.min(candidate2, e);
            }
		}
		
        return candidate2;
    }
}

First, a hash map is used to calculate the frequency of each element. Then, the code iterates through the map to find the elements with the highest and second-highest frequencies, handling ties by selecting the smaller element. It maintains two pairs of variables: (candidate1, freq1) for the most frequent and (candidate2, freq2) for the second most frequent.

Time Complexity: O(n) for iterating through the array and then the map.

Space Complexity: O(k) for the hash map, where k is the number of unique elements.

Sort Characters By Frequency

class Pair {
    char c;
    int freq;
	
    public Pair(char c, int freq) {
        this.c = c;
        this.freq = freq;
    }
}
 
class Solution {    
    public List<Character> frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
		
        for (var c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
		
        List<Pair> pairs = new ArrayList<>();
        for (var entry : map.entrySet()) {
            pairs.add(new Pair(entry.getKey(), entry.getValue()));
        }
		
        pairs.sort((a, b) -> {
            if (b.freq == a.freq) return a.c - b.c;
            return b.freq - a.freq;
        });
		
        List<Character> res = new ArrayList<>();
        for (var pair : pairs) {
            res.add(pair.c);
        }
		
        return res;
    }
}

This algorithm sorts characters from a string based on their frequency. It involves three main steps:

  1. Count the frequency of each character using a hash map.
  2. Store the character-frequency pairs in a list.
  3. Sort the list, primarily by frequency in descending order, and secondarily by character in ascending order for ties. Finally, it constructs the result list from the sorted pairs.

Time Complexity: O(n + k log k), where n is the length of the string and k is the number of unique characters. O(n) to build the frequency map and O(k log k) to sort the pairs.

Space Complexity: O(k) to store the map and the list of pairs.