[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^2) operations with arrays/strings

Basics

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

Exercise 1, Exercise 2

---

LeetCode #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

Time Submitted	Status	Runtime	Memory	Language
04/20/2022 00:41	Accepted	160 ms	54.1 MB	javascript

---

LeetCode LeetCode #692_Top K Frequent Words notes

Pseudo Code

// 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

Time Submitted	Status	Runtime	Memory	Language
04/20/2022 11:24	Accepted	93 ms	45.1 MB	javascript

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