[LeetCode] Problem Solving Pattern_Frequency Counter

I am currently studying the Udemy course JavaScript Algorithms and Data Structures Masterclass and want to jot down some notes. This post is dedicated to the problem solving pattern — Frequency Counters.

Scenarios

In some problem sets we can see questions like “ how many times has a, b, c occurred,” “ find the most frequently appeared element” popping up. And that is the sign of frequency counters.

Key Takeaways

• Use objects or sets to collect values/frequencies of values
• Try to avoid nested loops or O(N²) operations with arrays/strings

Basics

Here is a Code snippet of a basic function same(), and validAnagram().

#49_Group Anagram notes

Pseudo Code

// ** don't mutate the parameter (original data) so that we can use it later 
// sort the strings first to make the amount of identical elements clear 
// construct map and map property initial values 
// find identical elements and push their original form to the array that belongs to that anagram

Solution

var groupAnagrams = function(strs) { 
  const sorted = strs.map(el => {
    return el.split('').sort().join('') 
  }) 
  const map = {} 
  sorted.forEach((el, idx) => {
    map[el] = map[el] || [] map[el].push(strs[idx]) 
  }) 
  return Object.values(map) 
}; 
console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"])) 
// [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]

Result

#692_Top K Frequent Words notes

Pseudo Code

// deal with edge case first 
// create map to count frequency for each element 
// create set to make sure the result will not contain duplicate elements 
// loop over the map and pick the top k elements 
// if k is bigger than any frequency, add if condition 
// for checking if Object.values(map) is same as its reversed version (which means they have the same frequency)

Solution

var topKFrequent = function(nums, k) {
   // edge case 
  if (nums.length === 1 && nums[0] === k) return nums 
  const map = {} 
  const result = new Set() 
  nums.forEach(el => { 
    map[el] = (map[el] || 0) + 1 
  }) 
  const values = Object.values(map).sort((a, b) => b - a) 
  for (let number in map) {
    if (map[number] >= values[k - 1]) result.add(Number(number)) 
  }
  if (!result.size && values === values.reverse()) return nums 
  return [...result] 
}; 
console.log(topKFrequent([1, 2, 3, 1, 1, 2, ], 2)) // [1, 2]

Result

Related LeetCode Problem Sets

[Easy] LeetCode #242 Valid Anagram [Easy] LeetCode #1636 Sort Array by Increasing Frequency

[Medium] LeetCode #49_Group Anagram

[Medium] LeetCode #347_Top K Frequent Elements

[Medium] LeetCode #692_Top K Frequent Words

[Medium] LeetCode #451_Sort Characters By Frequency

Originally published at https://icaughtacode-hexo-blog.netlify.app on April 20, 2022.