Frequency Counters Pattern¶
This pattern uses objects or sets to collect values/frequencies of values.
This can often avoid the need for nested loops or $O(n^2)$ operations with arrays/strings.
same(arr1, arr2)
¶
Write a function called
same
, which accepts two arrays. The function should return true if every value in the array has it's corresponding value squared in the second array. The frequency of values must be the same.
1 2 3 |
|
-
Solution 1 (naive)
- Time: $O(n^2)$
- Space: $O(1)$
1 2 3 4 5 6 7 8 9 10 11
const same = (arr1, arr2) => { if (arr1.length !== arr2.length) return false; for (let i = 0; i < arr1.length; i++) { let correctIndex = arr2.indexOf(arr1[i] ** 2); if (correctIndex === -1) return false; arr2.splice(correctIndex, 1); } return true; };
-
Solution 2 (refactor)
- Time: $O(n)$
- Space: $O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
const same = (arr1, arr2) => { if (arr1.length !== arr2.length) return false; const freqCount1 = {}; const freqCount2 = {}; for (let val of arr1) freqCount1[val] = (freqCount1[val] || 0) + 1; for (let val of arr2) freqCount2[val] = (freqCount2[val] || 0) + 1; for (let key in freqCount1) { if (!(key ** 2 in freqCount2)) return false; if (freqCount1[key] !== freqCount2[key ** 2]) return false; } return true; };
validAnagram(arr1, arr2)
¶
Given two strings, write a function called
validAnagram
to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.
1 2 3 |
|
-
Solution
- Time: $O(n)$
- Space: $O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13
const validAnagram = (arr1, arr2) => { if (arr1.length !== arr2.length) return false; const freqCount1 = {}; for (let val of arr1) freqCount1[val] = (freqCount1[val] || 0) + 1; for (let val of arr2) { if (!freqCount1[val]) return false; freqCount1[val]--; } return true; };
sameFrequency(num1, num2)
¶
Write a function called
sameFrequency
. Given two positive integers, find out if the two numbers have the same frequency of digits.
1 2 3 4 |
|
-
Solution
- Time: $O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
const sameFrequency = (num1, num2) => { strNum1 = num1.toString(); strNum2 = num2.toString(); if (strNum1.length !== strNum2.length) return false; const freqCount1 = {}; for (let val of strNum1) freqCount1[val] = (freqCount1[val] || 0) + 1; for (let val of strNum2) { if (!freqCount1[val]) return false; freqCount1[val]--; } return true; };
areThereDuplicates(...args)
¶
Implement a function called,
areThereDuplicates
which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in. You can solve this using the frequency counter pattern OR the multiple pointers pattern.
1 2 3 |
|
-
Solution 1 (frequency counter)
- Time: $O(n)$
- Space: $O(n)$
1 2 3 4 5 6 7 8 9 10
const areThereDuplicates = (...args) => { let lookup = {}; for (let val of args) { if (lookup[val]) return true; lookup[val] = (lookup[val] || 0) + 1; } return false; };
-
Solution 2 (multiple pointers)
- Time: $O(n\log n)$
- Space: $O(1)$
1 2 3 4 5 6 7 8 9 10 11
const areThereDuplicates = (...args) => { args.sort(); let i = 0; for (let j = 1; j < args.length; i++, j++) if (args[i] === args[j]) return true; return false; };
-
Solution 3
1 2 3
const areThereDuplicates = () => { return new Set(arguments).size !== arguments.length; };