Frequency Counter Examples

Some examples that make use of the “frequency counter pattern” or “frequency counter approach”.

sameFreq()

Write a function called sameFreq, which accepts two arrays. It 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. The order doesn’t matter.

Unit Tests

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/05-problem-solving-patterns/sameFreq.test.ts[]

v1

TIME COMPLEXITY: O(n²). We have only one explicit for loop, but indexOf() is also a loop which can potentially go over the entire array. This implementation actually performs nested loops.

SPACE COMPLEXITY: O(1). Only the found index is stored each time. ys.splice() is not creating further arrays. Just reusing the same ys and making it smaller each time.

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/05-problem-solving-patterns/sameFreq-v1.ts[]

This solution involves looping while we have matching elements in xs. If end of the loop is reached without getting an index of -1 it means every element in xs has a matching squared element in ys.

1 That element is removed from ys so that one occurrence doesn’t ever match again. Important because the goal is to match the frequencies of squares of values in xs in ys.

v2

This solution first counts the frequencies individually and then compare those frequencies.

  1. Generate the frequencies of elements for both input arrays:

arr1 = [1, 2, 3, 1, 1, 3, 3, 3]
freq1 = { 1: 3, 2: 1, 3: 4}

arr2 = [1, 4, 9, 1, 1, 9, 9, 9]
freq2 = [1: 3, 4: 1, 9: 4]

Note that:

  • \(1 ^ 2\) is \(2\)

  • \(2 ^ 2\) is \(4\)

  • \(3 ^ 2\) is \(9\)

Then another loop checks if the squared keys in freq1 exist and have the same value in freq2. As soon as something doesn’t match, false is returned to indicate the two arrays do not meet the criteria; else return true.

TIME COMPLEXITY: \(O(n)\). Three non-nested loops is still linear time. Much better than two nested loops.

SPACE COMPLEXITY: \(O(n)\). Two other objects are created with potentially the same number of keys as xs and ys. So, the space taken inside the function is directly proportional to the input arrays size.

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/05-problem-solving-patterns/sameFreq-v2.ts[]

Three loops is much better than a loop inside a loop.

  • Two nested loops: \(O(n ^ 2)\) — quadratic.

  • Three loops one after the other: \(O(n)\).

Three loops is actually \(O(3n)\) but is simplified to \(O(n)\). It is still linear time.

anagram()

We’ll consider only lowercase characters from the English alphabet for this example. All other characters are to be ignored (including spaces).
Examples of anagrams
            tar = rat
            arc = car
          elbow = below
          state = taste
          cider = cried
          dusty = study
          night = thing
           inch = chin

      dormitory = dirty room
  school master = the classroom
   conversation = voices rant on
         listen = silent
     astronomer = moon starer
       the eyes = they see
    a gentleman = elegant man
        funeral = real fun

To solve it using the frequency counter pattern approach, we must see if the second string has the same frequency of letters as in the first string. For example “listen” is anagram to “silent” because each letter in “listen” has a corresponding frequency in “silent” (and vice-versa”.

Do not confuse anagrams with palindromes. Palindromes are words that are the same if spelled backwards, like “racecar”. If you reverse it, it is still “racecar”.

Unit Tests

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/05-problem-solving-patterns/anagram.test.ts[]

v1

TIME COMPLEXITY: \(O(n)\). We loop a couple times for the length of the input string. Not a nested loop.

SPACE COMPLEXITY: \(O(n)\). We create a frequency object of at most the size of the input. This object may be as large as the input.

This solution involves two main ideas:

  • Loop once creating a frequency object with the the frequencies of the characters on first string.

  • Loop once more, this time on the second string, and for each character, decrement 1 from it in the frequencies object created with the previous loop.

If we ever get a 0 count or undefined, it means we found that character in the second string more times than in the first string, which means the strings are not anagrams to one another.

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/05-problem-solving-patterns/anagram-v1.ts[]
1 In case char c does not exist in freqS1, it means it exists in s2 but not in s1, so the inputs are not anagrams. However, if it is 0 (which is also falsy), it is not an anagram either because it means we found that letter again (during this iteration of the loop) on s2 which means we would decrement it even more, making it -1. It means the current char doesn’t appear with the same frequency on both strings.

areThereDups()

Implement a function called areThereDups which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in.

Unit Tests

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/06-challenges/areThereDups.test.ts[]

v1

TIME COMPLEXITY: \(O(n)\). The input is potentially iterated from beginning to end.

SPACE COMPLEXITY: \(O(n)\). A frequency object is created which can potentially be as large as the input.

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/frequency-counter-examples.adoc - include::example$src/06-challenges/areThereDups-v1.ts[]