DEV Community: noam sauer-utley

Solving Balanced Brackets in Javascript with Stacks

noam sauer-utley — Sat, 29 Feb 2020 21:31:09 +0000

GitHub Repo with completed solution code and test suite

What is the aim of the Balanced Brackets algorithm challenge?

“Given a string containing brackets, determine if all brackets have a matching counterpart. If all brackets in the string form balanced pairs, return true. If not, return false”

Note: I use the word “brackets” in this case to refer to parentheses, curly braces, square brackets, and angle brackets (‘), {, [, <, >, ], }, )’). Not every challenge might require you to include all four types!

The first time I looked at this problem, my first instinct was to try to just sort the string into substrings based on whether each character was an open or closing bracket and compare the lengths of the substrings.

That approach may work on the occasional simple string, but it breaks down pretty quickly. We need to know not only that there is a closing bracket for each opening bracket, but also that the specific type of opening and closing brackets match each other. Not only that, if we wanted this function to be useful for any sort of IDE syntax highlighting or other practical application, it would need to identify not only that the opening and closing brackets exist in the correct number and type, but also that they are arranged in the correct order — that every opening bracket has a matching closing bracket in the correct place in the string to actually close it.

This is what is meant by saying that brackets are “balanced” — not only do they exist in the correct number of matching pairs, but that those pairs are arranged correctly so that the closing brackets can balance the opening brackets.

My initial idea for sorting out the string into substrings and comparing substring lengths would clearly break down at multiple intervals of the challenge.

I needed another approach.

STACKS

The tool I ultimately used to solve this algorithm was a data structure I hadn’t used before.

I’ve written before about the benefits of using hash tables and recursive trees to break down complicated tasks. I know that data structures can make amazing tools for deconstructing problems that require algorithmic solutions.

But before trying to tackle this particular problem, I hadn’t had many encounters with stacks¹.

In Javascript, I like to think of them as an array with some restrictive rules.

Normally, arrays in Javascript can be manipulated in a really wide variety of ways. That’s what makes them so handy. That’s the reason why I start most algorithmic solutions by making an empty array. We’ll almost always need one as an environment for manipulating or organizing our data.

Stacks in Javascript are utilized by only operating on an array using the push and pop methods. These methods would push a new element onto the top of the stack, or pop it back off the top, respectively.

While the elements of a regular array can be accessed from any direction (unshifted off the front, pushed onto the back, sliced right into or out of the middle, or just edited in place), I think of a stack as being an array that’s been all sealed up so that it’s inaccessible, except for one door. New things can be pushed in through the door, but then only the most recently added thing, the one directly in front of the door, can be accessed or manipulated in any way. If that element is removed using array.pop(), then the element behind it is now available to be changed or removed. However, if it is not removed but instead a new element is pushed in through the door, the previously accessible element becomes inaccessible again.

This approach is called FILO, or First In Last Out.

(This sort of acronym may be familiar to anyone who’s worked in or around kitchens, which are inevitably ruled by the related but opposite law of FIFO, or First In First Out in the attempts to avoid food waste and spoilage.)

Why would we intentionally limit our lovely versatile arrays like this though?

Well, this process preserves a particular order — the elements can only be removed in the order that they were initially added, preserving the original order, or pattern.

Which is exactly what we need to do with our brackets — identify not only the number and type of brackets included in our string, but also their specific order.

So, we know that stacks allow you to manipulate data within an array, while preserving the original ordered patterns of the data, which sounds like what we need to do. Let’s set about actually using this tool in an algorithmic solution to our this challenge.

So, a bit of pseudocode to get us started:

let isBalanced = (input) => {
  iterate through input
    if the current element is an opening bracket, record the correct closing bracket
    if the current element is a closing bracket, check the record to make sure it is the correct closing bracket
  if all the opening and closing brackets are matched and in the correct order, return true, otherwise return false
}

I know that using a stack, I can preserve a record of the order of my brackets, which will allow me to check if they are all correctly balanced (all opening and closing brackets have a match, and they are in the correct order to balance each other) or not.

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    // record order on the stack
    // check this record to make sure the brackets are all balanced
  }
  return true ? true : false
}

First, I’m making a few workhorse variables for myself.

I’m saving a string listing all my potential opening and closing brackets to a variable named brackets.

Note: I am pairing the opening and closing brackets together in this string.
**This is important. **
My particular solution would not work if the bracket string were to be written as “[{(<]})>”, for example.
The brackets can be in any order by type (e.g. “()[]{}<>” and “<>(){}[]” are both perfectly fine), but the opening and closing brackets must be written together.

The next variable I’m creating is just an empty array, which we can call stack, as this will be our stack.

I’ve sketched out an initial loop through our input string, populated only by pseudocode at this point.

Note: this loop is iterating through the elements of input, not the indexes. Personally, I enjoy using for…in / for…of loops, but you can always use a more traditional for loop (e.g. “for (let i = 0; i < input.length, i++)”) and still utilize this solution with minor modifications if you prefer.

Our function’s only remaining job will be to return either true or false upon the loop’s resolution.

Time to actually develop our stack and put it to use!

First, another workhorse variable within the loop itself:

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)

    // record order on the stack
    // check this record to make sure the brackets are all balanced
  }
  return true ? true : false
}

bracketsIndex: I want to make sure the role of this variable is quite clear before moving forward!

We are iterating through input, the string of brackets that is passed into the function for testing.

bracketsIndex is NOT the index in input of the current bracket.*

bracketsIndex is looking up the index of the current _bracket _in our previously saved brackets variable. So if the first bracket in input were a “(“, its bracketsIndex would be 4. Its index in input is, of course, 0, but the index of “(“ in brackets is 4, so its bracketsIndex is 4.

Remember the bit about how the order of the brackets in the brackets string was important? We’re getting there.

So now, we have a variable, bracketsIndex, that can look up our current bracket in the brackets variable.

Now, we can finally start putting our stack to work.

Because of the way we organized our brackets reference string, we know that opening brackets have even indexes (0, 2, 4, & 6) and closing brackets have odd indexes (1, 3, 5, 7).

So, if our current bracketsIndex is even, we know that the current bracket is an opening bracket.

We can test for this using a modulo operator. Modulo operations, called in Javascript by the modulo operator, i.e. “%” (commonly called the percent sign), divide a first number by a second number, then return the remainder. So, one way to test for even or odd numbers is to run number % 2 === 0. Two will divide evenly into an even number, yielding a remainder of zero (returning true) while it will not into an odd number (returning false).

We can then push the location in brackets of the needed closing bracket onto the stack, by finding the bracket with index bracketsIndex + 1. Again, because of the way that we wrote our brackets string, an opening bracket will always be immediately followed by its matching closing bracket. Thanks to this, we can increment the bracketsIndex of any opening bracket to find the address of its closing match.

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)

    // if bracket is an opening bracket
     if(bracketsIndex % 2 === 0) {
       // push the closing bracket onto the stack
      stack.push(bracketsIndex + 1)
    } else {
      //do something
    }
  }
  return true ? true : false
}

Now, as we iterate through our input, our stack will keep a record of the closing brackets needed for the input string to be balanced.

Note: The bracketsIndex, an integer, is what is being pushed onto the stack, not the closing bracket itself.

Example: If our loop had iterated through the elements “(, <, [“, the stack would hold the indexes in brackets of “), >, ]” and thus would be [5, 7, 1].

Our loop will continue this task as long as we keep hitting opening brackets.

That’s cool. What happens when we hit a closing bracket though?

If the current bracket of input is a closing bracket, and therefore has an odd index, then (due to our conditional that runs based on the even/odd test of its bracketsIndex), a new task will run.

Array.pop() removes the most recent addition from our stack, changing the length of the array, and returns that removed element, allowing us to reference that element if needed.

So, If the current bracket is closing, we’ll pop the last element off the stack and compare the two. If our brackets are balanced, they should match.

This is the whole purpose of using the stack — as we iterate through our input string, the needed closing bracket is pushed onto the stack for each opening bracket, then popped off when the matching closing bracket is reached. If something in the stack breaks this pattern, then we know that our input string is not balanced.

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)

    if(bracketsIndex % 2 === 0) {
      stack.push(bracketsIndex + 1)
    } else {
      if(stack.pop() !== bracketsIndex) {
        return false;
      }
    }
  }
  // return true or false
}

Example: If our loop had iterated through the elements “(, <, [“, the stack would hold the indexes in brackets of “), >, ]” and thus would be [5, 7, 1].
If the following iteration hit the element “]”, then our expression would check stack.pop() (i.e. 1) against the bracketIndex of the current bracket (the current bracket being ] would have a bracketIndex of 1) and, as they are indeed equal, would return true, allowing it to move on to the next element in input. The stack going forward would be [5, 7], as the execution of stack.pop() permanently removed 1 from the stack array.

We need to check for one more thing though — when this loop resolves, the stack should be empty. If it’s not, that means there’s an extra unbalanced bracket or more left over.

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)

    if(bracketsIndex % 2 === 0) {
      stack.push(bracketsIndex + 1)
    } else {
      if(stack.pop() !== bracketsIndex) {
        return false;
      }
    }
  }
  return stack.length === 0
}

So, I check that stack has a length of zero in the final boolean return. The expression stack.length === 0 will return the boolean we need here.

If the whole loop runs without returning false and the stack is empty when it resolves, we know our input string is balanced and the function should return true. Otherwise, our function should return false.

Let’s run this function into the console and see what we get!

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)

    if(bracketsIndex % 2 === 0) {
      stack.push(bracketsIndex + 1)
    } else {
      if(stack.pop() !== bracketsIndex) {
        return false;
      }
    }
  }
  return stack.length === 0
}

isBalanced('()')
> true

isBalanced('()[]{}<>')
> true

isBalanced('([{<>}])')
> true

isBalanced('([])[{}]{(())}')
> true

isBalanced('(')
> false

isBalanced('()]')
> false

isBalanced('([])[{}]{(([))}')
> false

isBalanced('({)')
> false

isBalanced('([)]')
> false

isBalanced('([])[{}]{([)]}')
> false

Great! 🌟 I tested the isBalanced() function against a variety of balanced and unbalanced strings² and it returned the correct boolean for each one! Unlike my first idea, this function can successfully check for not only the correct number and types of brackets, but also check their specific order to make sure they match up correctly.

I still want to add one more element of functionality to our function. At the moment, if input contains anything other than pure brackets, our function will break. That’s not going to help us much if we actually wanted to create our own syntax bracket highlighter or other practical application of our function. So, we can add one more conditional into our loop.

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)

    if (bracketsIndex === -1){
      continue
    }

    if(bracketsIndex % 2 === 0) {
      stack.push(bracketsIndex + 1)
    } else {
      if(stack.pop() !== bracketsIndex) {
        return false;
      }
    }
  }
  return stack.length === 0
}

If the current element is not in brackets (which will yield an index of -1), we simply direct our loop to move on to the next character in our input string. This one change makes our function much more adaptable!

This algorithm challenge made me really appreciate using a stack, even though that particular data structure had been quite neglected in my previous experience. There are other ways to solve this, but a lot of them involve writing out a lot of repetitive code to test for each individual bracket type, which gave me lots of opportunities to make typos and get bored.

If you’re having a tough time visualizing the operation of the stack, I recommend adding some debuggers or console.log()s to this code, and watching the loop play out in your console.

Not sure where to start? You might try something like this:

let isBalanced = (input) => {

  let brackets = "[]{}()<>"
  let stack = []

  for(let bracket of input) {
    let bracketsIndex = brackets.indexOf(bracket)
    console.log(`The current element is ${bracket}, which has an index in input of ${input.indexOf(bracket)}, and matches the bracket with index ${bracketsIndex} in brackets`)

    if(bracketsIndex % 2 === 0) {
      stack.push(bracketsIndex + 1)
      console.log(`this is an opening bracket. The address of its matching closing bracket in brackets is ${bracketsIndex + 1}. Adding that index to the stack makes the stack ${stack}`)
    } else {
      console.log(`this is a closing bracket, so ${stack.pop()} is being popped off the stack`)
      if(stack.pop() !== bracketsIndex) {
        return false;
      }
    }
  }
  return stack.length === 0
}

Hopefully this algorithm challenge gives you the same opportunity it did me — the chance to understand how stacks work, and why they’re such useful tools for problems where a particular order needs to be preserved and checked against.

This article also addresses the queue data structure, which isn’t strictly relevant to this particular challenge but still nice to know about. While the article is not exclusively stack-focused, it’s one of my favorite stack summaries. I also like this one.
These strings are what I use in the test suite included in the GitHub Repo for this post, and the test file includes comments that can give you more info about what each different string is testing the function for.

Solving the Ransom Note Algorithm in Javascript

noam sauer-utley — Mon, 24 Feb 2020 00:17:36 +0000

GitHub repo with completed solution code and test suite.

What is the Ransom Note challenge?

‘Given two strings:

1. A source string, i.e. the “page”

2. A desired string, i.e. the “note”

determine if the desired “note” string can be created using only the letters found in the source “page”.’

A visual example of what we’re looking for would be this:

So, if we had a page of text, we could chop it up into all its separate letters, then glue them onto a new page to form a new word or phrase of our choosing.

Ok, so let’s get started!

I like to start with a little bit of pseudocode, just so I can write out my aims in a programming context.

let canMakeNote = (source, note) => {
    if (source contains all the letters needed to make note){
      return true
    }else{
      return false
    }
}

So here we have a function called canMakeNote, whose job is to see if the source string contains all the letters needed to create the desired note string. If that is true, it should return true, and if not, false.

However, “if source contains all letters needed to create note” is doing a lot of heavy lifting in the above pseudocode. Let’s start at the beginning.

We know one thing right away: If the source string is shorter than the note string, we will not be able to make the note. There’s no way that we’ll have all the letters we need.

So first things first, we’ll need to compare the length of our two strings. If the source string is too short, we won’t need to bother with anything else, and can immediately return false.

However, strings can be… messy.

They could include whitespaces, which I’m not going to track as if they were a letters — if I were cutting letters out of a newspaper or magazine and gluing them onto paper, I wouldn’t cut out and paste on spaces. Counting each whitespace as a letter could be an interesting variation of this challenge, but I’m not going to explore that in this solution.

So, if whitespaces don’t count as letters, they’ll distort our ability to measure the length of our strings. Not good.

Plus, the strings might contain both capital and lowercase letters. This won’t affect our judgement of the length of the strings, but it will become an issue further down the line when we begin attempting to compare the content of the strings. For our purposes, “A” is the same as “a”. After all, the iconic ransom note is defined by its higgledy-piggledy mix of upper and lower cased letters. The computer, on the other hand, sees “A” and “a” as completely different characters.

So that gives us two things we’ll need to account for as we compare our input strings, whitespaces and character case.

**Note: Some variations of this challenge will provide the input and desired output parameters in the form of arrays of letters, all tidy and ready to go. That’s great! If you run across a challenge like that, you can just skip this step! However, I wanted to provide a solution that accounts for input / desired output in string form.

To clean up our messy strings and transform them into something more convenient to our purposes, let’s make a helper function.

I’ll need to account for the whitespaces and character case, and, as this is an algorithmic challenge, I’m going to go ahead and transform our strings into arrays, so that each character will be individually separate, and our data will be in a convenient form for iteration, manipulation, and comparison.

First, I’ll pseudocode it out:

let clean = (input) => {
  remove whitespaces from input
  lowercase input
  transform input into an array
  return the cleaned & transformed input
}

So we’ve got a handy list of what our string cleaning helper function needs to do.

First, the whitespaces.

Whenever I need to identify and manipulate a certain character or characters in a string, I think of RegEx. RegEx is the shorthand reference for a“Regular Expression”. What is a that?

RegEx

A regular expression, regex or regexp (sometimes called a rational expression) is a sequence of characters that define a search pattern. Usually such patterns are used by string searching algorithms for “find” or “find and replace” operations on strings, or for input validation.

What can RegEx search patterns do? They’re great at collecting all the characters in a string that match a given search criteria, then collecting or manipulating them as directed. This can be incredibly handy, making things that would otherwise be laborious and complicated relatively quick. The tradeoff is that performing RegEx find and replace operations can be computationally expensive! Which should be considered when RegEx is being considered for manipulating extremely large strings. However, for our purposes at this time, RegEx is just what the doctor ordered.

I’ll be honest, I’m not an expert who’s memorized all the different RegEx patterns and their meanings. I know enough to be able to quickly recall my most-used patterns, but mostly, I’ve had great success with just developing the ability to identify when I’m looking at a problem that would be eased by the use of RegEx. Then, a quick google of the type of find and replace operation I want to perform with the keyword “RegEx” and perhaps the language of the code I’m currently writing usually yields results within the first few links.

In this case, I googled “javascript regex remove all whitespaces from string” and was promptly provided with the appropriate RegEx pattern for my needs.

OK, enough about RegEx! Back to our string-cleaning helper function.

I can combine Javascript’s ***replace*** method with my chosen RegEx pattern, to replace every whitespace in my string with nothing, therefore stripping them out entirely. The RegEx search pattern that I chose also removes line breaks, and any other sorts of “blank” characters it might encounter.

let clean = (input) => {
  input.replace(/\s/g,'')
  lowercase input
  transform input into an array
  return the cleaned & transformed input
}

input is the name of our argument, which can be any string passed into the function. /\s/g is the RegEx search pattern to identify all whitespaces / blank characters, and the empty string that follows tells **input.replace **that we want to replace the whitespaces with nothing. Altogether, this combo will strip all the blank characters from our input string.

Whitespaces handled. ✔️

Next on our list is character case.

Lucky for us, Javascript comes complete with its own ***toLowerCase*** method, which does pretty much what it says on the tin. When called on a string, it will transform all capital letters in the string to lowercase letter. So, our **clean* *function can accomplish the next task on our pseudocode list by calling this method.

let clean = (input) => {
  input.replace(/\s/g,'').toLowerCase()
  transform input into an array
  return the cleaned & transformed input
}

Okay, finally, we want to change our stripped and lowercased string into an array of characters, and return the final result.

Again, Javascript has the relevant method ready and waiting for us, as this is the exact purpose of the ***string.split()*** method. We have to tell the method where we want it to split the string, which we can do by including the trigger character in quotes within the parentheses after the method name. However, as we want to separate out each individual character (rather than splitting at each space, for example, to separate out words, or at final punctuation marks to separate sentences), we put nothing inside the quotes.

So, our final clean function looks like this:

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

While the GitHub repository for this article includes a testing suite, I also like to use the browser console to quickly check my functions and make sure they’re returning what I want. Let’s see what this clean function returns when given a quote.

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

let quote = "Aut Viam Inveniam Aut Faciam"

clean(quote)

> (24) ["a", "u", "t", "v", "i", "a", "m", "i", "n", "v", "e", "n", "i", "a", "m", "a", "u", "t", "f", "a", "c", "i", "a", "m"]

🌟 Great! This is exactly the result we wanted. We now have a cleaning function that can take in a string, downcase any capitals, remove all whitespaces, and return a handy array ready to go for our comparison needs.

In order to effectively compare our now-transformed strings, we need to track two data elements: the individual characters that we either have available or need, and also frequency with which each character we either have available or need occurs.

The source text may, for example, contain the letter “e” — but what if our desired output text needs five “e”s? An instance of a matching letter alone is not enough to decide that the source text has what we need.

In Frequency Analysis, this is a routine challenge, which is often met with the use of Histograms, which are quite similar to Bar Charts.

These graphical tools are a visual representation of the exact two pieces of data we need to track — letter and frequency of occurrence.

Now, unfortunately I can’t simply show a histogram to my computer. However, I can use a non-graphical data structure to communicate the same information that’s in my histogram.

Speaking of Data Structures, the more algorithms I solve, the more I appreciate the Hash Table. The data structure that allows the storage of key-value pairs is often an effective and efficient tool in tasks that require comparing lots of little bits of data. If you’d like to see another example, my set of solutions to the Two Sum Problem includes a hash-based solution, which is by far the most efficient of the three solutions I explore.

So when I see a challenge that requires the storage of paired pieces of data, it feels intuitive to at least try storing those pieces of data as key-value pairs.

Let’s pseudocode out this specific task, just as we’ve done before:

let makeHistogram = (input) => {
    let histogram = {}

    assign each letter of input to a key in histogram
    assign the occurrence frequency of that letter to the corresponding value

    return histogram
}

So we’re setting out to create a hash object which can mimic a frequency occurrence histogram. In it, we want to save each character to a key, then store that character’s occurrence frequency (the number of times it’s repeated) to the value attached to that key.

Since we’re needing to check each letter, we should start by iterating through our input. I’m assuming the input is an array of relevant lowercase characters, as that’s what our previous clean helper method returns.

For each letter, I’ll need to determine if we’ve already encountered it before. If it’s the first instance of that letter in the array, we need to make a new key in our histogram hash object, and assign it the value 1, for one occurrence. If the letter has occurred earlier in the array and therefore has already had a key created for it, we should not make a new key, but rather add 1 to the existing key’s value.

So, with a bit more pseudocode, we can sketch out our loop structure:

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        if the letter has been encountered before,increment the value of the key corresponding to letter by one 
        else create a key for it and assign a value of one
    }  
    return histogram
}

As I only have two behavior patterns to choose from, I can write out the conditional statement for this using a ternary operator.

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        letter in histogram ? histogram[letter] += 1 : histogram[letter] = 1
    }  
    return histogram
}

In this code, the section before the ? is the if statement. This is what we’re checking for as we iterate through the input array — for each letter of input, we’re checking to see if it already exists in histogram. If it does, the first operation which comes right after the **? *(adding one to the value which corresponds to the letter’s key) should be performed. Otherwise, the second operation which comes after the *: **(creating a key for the letter and assigning it a value of one) should be performed.

Just as we did with our clean helper function, let’s throw this into the console and see what it outputs.

let quote = "Aut Viam Inveniam Aut Faciam"

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

let cleanedQuote = clean(quote)

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        letter in histogram ? histogram[letter] += 1 : histogram[letter] = 1
    }  
    return histogram
}

makeHistogram(cleanedQuote)

> {a: 6, u: 2, t: 2, v: 2, i: 4, m: 3, n: 2, e: 1, f: 1, c: 1}

🌟 Great! This returns a hash object containing each letter from the given input as a key, and the occurrence frequency of that letter as the corresponding value.

We’ve now organized our data into a structure that we can efficiently test. Enough with the helper functions, we’re finally ready to do something with the very first pseudocode function we wrote!

let canMakeNote = (source, note) => {
    if (source contains all the letters needed to make note){
      return true
    }else{
      return false
    }
}

So this was our original pseudocode.

First things first, we know we’ll be returning a boolean. Let’s go ahead and create a variable for that return value — I’m going to call it boolean for ease and give it a default value of false.

Then, we can use our clean function to clean up our input.

That will give us two arrays, the lengths of which we can compare. That way, just as we originally stated, if the source is longer than the note, we’ll want to move forward, but if it’s not? We don’t need to do anything else and can immediately return false. Since we initialized our boolean variable with a value of false, we can just return it.

Thus far, we could write that out like this:

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        use histogram to see if source contains all the letters needed to create note
    }
    return boolean
}

This is much closer to a working function than the pseudocode we started with, but there’s still a big vague chunk in the middle.

That’s okay though, that’s what our makeHistogram function is for!

We can call makeHistogram twice, inputting our cleaned arrays, and get two hash objects, which we can now compare.

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        let sourceHistogram = makeHistogram(source)
        let noteHistogram = makeHistogram(cleanedNote)
        for(let letter in noteHistogram){
            if (the value of the key letter in sourceHistogram is greater than or equal to the value of the key letter in noteHistogram){
                boolean = true
            } else {
                boolean = false 
                break
            }
        }
    }
    return boolean
}

There’s still a bit of pseudocode standing in, but we can now iterate through the keys of the cleaned & hashed note text, and check each one against the cleaned and hashed source text. As a hash key provides a specific place in memory to directly check, this is a very efficient way to compare these pieces of data.

As we iterate through the note object, if the check against the source object reveals that it contains the correct character in the correct amounts, the boolean should be assigned the value true. If this check fails, the boolean should be assigned the value false and we can use the ***break*** statement to immediately exit the for loop, which will trigger the boolean return, thus causing our function to return false.

However, if each character key checked returns true, the for loop will resolve with the boolean still assigned the value true, then and only then will our function return the value true.

All that’s left to do then is to write the code for testing the values of the hash objects.

We need to check for two things:

1: That the source hash object has a key matching the current letter.

2: If true, that the corresponding value is greater than or equal to the value of corresponding to the current letter key in the note hash object.

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        let sourceHistogram = makeHistogram(source)
        let noteHistogram = makeHistogram(cleanedNote)
        for(let letter in noteHistogram){
            if (sourceHistogram[letter] && sourceHistogram[letter] >= noteHistogram[letter]){
                boolean = true
            }else{
                boolean = false 
                break
            }
        }
    }
    return boolean
}

Okay, this looks promising, let’s throw everything into the console and see what we get.

let quote = "Aut Viam Inveniam Aut Faciam"

let clean = (input) => {
    return input.replace(/\s/g,'').toLowerCase().split("")
}

let makeHistogram = (input) => {
    let histogram = {}

    for(let letter of input){
        letter in histogram ? histogram[letter] += 1 : histogram[letter] = 1
    }  
    return histogram
}

let canMakeNote = (source, note) => {
    let boolean = false

    let cleanedSource = clean(source)
    let cleanedNote = clean(note)

    if (cleanedSource.length >= cleanedNote.length){
        let sourceHistogram = makeHistogram(source)
        let noteHistogram = makeHistogram(cleanedNote)
        for(let letter in noteHistogram){
            if (sourceHistogram[letter] && sourceHistogram[letter] >= noteHistogram[letter]){
                boolean = true
            }else{
                boolean = false 
                break
            }
        }
    }
    return boolean
}

// let's try a word that only needs letters contained within our quote
canMakeNote(quote, "acuminate")

true

// okay, now a word that requires one more letter "e" than our quote possesses
canMakeNote(quote, "cuneate")

false

🌟 Great!

I really love this algorithm challenge because I think it’s a perfect use case for one of my favorite algorithm-solving tools, the humble hash. I hope this solution illustrates how useful a hash table can be, and that this approach is helpful to all your algorithm-solving challenges!

Find All Permutations of a String in Javascript

noam sauer-utley — Fri, 14 Feb 2020 16:03:37 +0000

Published by ∞ Level Up Coding
Featured by ★ Medium Curated

GitHub repo with completed solution code and test suite.

Given a string, return all permutations of the string.

When I sat down to solve this problem, I found it to be a great algorithm challenge. Why? While the task of manipulating a string may seem familiar on its surface, actually finding a complete solution requires us to handle some unexpected complexity, which provides the opportunity to utilize a recursive tree and build a bit of familiarity with the master theorem.

Note: There is more than one way to solve this problem. The solution model I explore here utilizes tools and concepts that I find broadly valuable for the solution of algorithmic challenges, and methods that I find intuitive for string manipulation within Javascript.

First things first: What is a permutation?

per·mu·ta·tion

Learn to pronounce

noun

a way, especially one of several possible variations, in which a set or number of things can be ordered or arranged.

So every string has a number of permutations into which its characters could be re-arranged. A string permutation is similar to an anagram. However, it does not need to be an existing word, but can simply be a re-arrangement of the characters.

An example of permutations of something other than a string would be this:

For just three colors, we can have six different permutations, or ordered combinations of those colors.

Another example of permutations would be a combination lock:

Uh-oh. The whole point of combination locks is that a relatively small amount of numbers can create a large enough number of ordered combinations to prohibit casual opening.

Suddenly, this whole string-manipulation problem seems a bit more intimidating.

So we’ve figured out what a permutation is, and established that (depending on the length of the string) we may be looking for a lot of them. Where to start?

When I see a challenge like this, my first instinct is two do two things:

1: Make an empty array. If my final solution may return more than one “correct” element (in this case, permutations), I’ll need a place to store them before I return the complete solution.

2: Iterate! If I need to find all the ordered combinations of characters in a string, creating a loop to iterate through all the characters in a string seems like a decent place to start.

let findPermutations = (string) => {

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // do something
  }
  return permutationsArray
}

Before we jump straight into our iteration, let’s knock a few things out of the way.

What if the user enters an empty string, or an integer, or tries to run the function without entering anything at all? We can’t get all the permutations of a string if there’s no string.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // do something
  }
  return permutationsArray
}

The new line of code will return an error message if the argument input into the function is falsey, or if it is not a string.

Okay, great!

But what if the string is really short? Like only-one-character short? That’s also a scenario where we don’t really need to mess with the whole iterating and pushing things into an array bit. If our string is, for example, just “a”, it only has one permutation — “a”. We can just return “a”.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // do something
  }
  return permutationsArray
}

Alright, now that’s out of the way, we can get back to our iterative loop.

The structure of our function in its current state now looks a bit similar to something called the master theorem.

The Master Theorem

What is the master theorem?

It is a set of steps for breaking down potentially complex challenges into a set of smaller problems. Many problems or technical challenges fall into the category of Divide and Conquer Algorithms, which require the would-be solver to break a piece of data down into smaller pieces until the pieces are simple enough to be solved directly.

Written out in pseudocode, it looks like this:

procedure p( input x of size n ):

if n < some constant k:

Solve x directly without recursion

else:

Create a subproblems of x, each having size n/b

Call procedure p recursively on each subproblem

Combine the results from the subproblems

A few important things happen here:

1: a conditional checks if the size of the input is smaller than a constant.

2: if the input is larger than said constant, the input is broken down into smaller pieces until they are all small enough to run the procedure on directly

3: when this is done, the results of all the pieces post-procedure can be combined and returned as a single large bit of data.

This approach to breaking down problems is often visualized as a tree (especially as this is often helpful for establishing down a problem’s time complexity. You can read more about time complexity and the master method here).

Want to read more about recursive trees and the master theorem? I like this synopsis from Cornell.

Note how similar this structure is to the following diagram of our specific challenge of finding all permutations of a string:

While our current function isn’t exactly the same as the abstracted pseudocode of our master theorem, we have established the logical path of returning one solution if our input is smaller than a constant (in our case, if string.length is less than 2), and if not, creating a list of subproblems to solve.

If you’ve flattened out nested arrays before, this approach may feel familiar. It’s can be a good starting point for a wide variety of challenges — it won’t be the relevant method for every problem, but provides a nice place to start.

Note: This approach does utilize recursion.

You can read more about recursion here, here (code examples in javascript), here (code examples in javascript), here (code examples in ruby), and here (code examples in python).

Okay, back to our code.

Now, if we want to utilize the master theorem approach, we can update our plan to something a bit more clear than // do something.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // Create a subproblems of string, each having size n/b
    // Call procedure p recursively on each subproblem
    // Combine the results from the subproblems
  }
  return permutationsArray
}

For ease, I’d like to assign the current element we’re iterating over to the variable char.

So the first thing we’re supposed to do is break our string down into sub-problems.

To start, we have our current character, aka string[i], aka char. To begin breaking down the rest of the string, we need to collect the remaining characters.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    let char = string[i]
    let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length)

    // Call procedure p recursively on each subproblem
    // Combine the results from the subproblems
  }
  return permutationsArray
}

Just as we assigned our current character to the variable char, let’s assign the remaining characters to the variable remainingChars.

Note: There are many different ways one might collect the remainingChars. This is just one method.

To collect those characters, we can use the string method slice. Substring is a similar method, so if you’re more familiar with that, you can use it instead. Slice is non-destructive, so we don’t need to worry about mutating our original string — the result we get by slicing our string will be its own new string.

So we’ll slice the characters from index 0 (the first character in the string) to index i (our current character, char). Then, we’ll join the characters from index i + 1 (the next character after char) to index string.length (the last character in string).

So now we have two smaller strings — char and remainingChars.

What now?

Well, let’s consult the master theorem:

Call procedure p recursively on each subproblem

So we’re going to call our findPermutations function on our remainingChars string.

Then what?

Combine the results from the subproblems

I knew we’d need that empty array.

Okay, so what does this look like in JavaScript?

let findPermutations = (string) => {
  if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    let char = string[i]

    let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length)

    for (let permutation of findPermutations(remainingChars)){
      permutationsArray.push(char + permutation) }
  }
  return permutationsArray
}

So we’ve done a few things here.

We recursively called findPermutations on remainingChars. For each result of that function, which I assigned to a variable named permutation, we can push a string that is the combination of char and permutation into our permutationsArray.

findPermutations("abc")

(6) ["abc", "acb", "bac", "bca", "cab", "cba"]

So let’s see what we get when we return permutationsArray.

Okay, great! When given the input “abc”, our findPermutations function returns all six permutations!

Let me try one more thing though.

findPermutations("aabc")

(24) ["aabc", "aacb", "abac", "abca", "acab", "acba", "aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "baac", "baca", "bcaa", "bcaa", "caab", "caba", "caab", "caba", "cbaa", "cbaa"]

Well, that’s not good. If a character in our string repeats, we get each permutation twice. Lots of strings have repeating characters.

let findPermutations = (string) => {
  if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    let char = string[i]

    if (string.indexOf(char) != i)
    continue

    let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length)

    for (let permutation of findPermutations(remainingChars)){
      permutationsArray.push(char + permutation) }
  }
  return permutationsArray
}

There are a lot of different ways to remove superfluous elements, but I chose to use Javascript’s indexOf method to identify if the current character has already been run through our findPermutations method. indexOf returns the first index of a character, so if we’ve already run findPermutations for an “a”, for example, the indexOf(“a”) will be different than the index of char, the current, later “a”.

If this is true, we can continue, which will essentially skip the current iterative loop and move on to the next.

Let’s run findPermutation with this addition.

findPermutations("aabc")

(12) ["aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa", "caab", "caba", "cbaa"]

Perfect! 🌟 A master theorem based approach allowed us to quickly break this problem down into bite sized pieces and begin returning correct results, leaving only a few tweaks needed here and there to deliver our solution in exactly the desired format.

Review:

So what was our master theorem based approach again?

1: Establish a base case — if our input’s size is less than a certain constant, solve it directly without recursion.

2: If the input is bigger than said constant, break it down into smaller pieces.

3: Call the function recursively on the pieces, until they are small enough to be solved directly.

4: Combine the results from the pieces, and return the completed solution.

I have found this model to be a really handy tool that reliably provides me with a place to start when tackling algorithmic challenges. While not specifically applicable to every algorithm problem, and not always the most performant or elegant solution, it’s a reliable workhorse model that can serve you well!

The GitHub repo containing the solution code also comes with a test suite, so you can practice or play around with finding alternate solutions for this problem if you like.

If you want to explore further, you could try using the solution model utilized above to find all the combinations of a combination lock? Does it work? Do you need to make any changes?

Solving The Two-Sum Problem in Javascript, Three Ways

noam sauer-utley — Fri, 14 Feb 2020 15:22:08 +0000

Published by ∞ Level Up Coding
Featured by ★ Medium Curated

This Github repo contains my completed code for all three solution models.

What is the Two-Sum Problem?

“Given an array of integers and a target number, return the two integers that add up to the target number”

Notes:

The desired result can be returned in a few different forms — I’ve seen queries ask either for the indices of the addends (aka their locations in the array), or for the addends themselves.

Additionally, some challenges are structured so that only one pair of numbers will add up to the sum.

In my solutions, I will be returning all discrete successful addend pairs.

I will briefly address approaches for adapting my solutions to return a single addend pair or array indices rather than addends themselves.

I will use the array [2, 3, 4, 3, 6, 7], and the sum integer 6 to test all solutions.

1: BRUTE FORCE

For my first solution, I’m not prioritizing elegance or performance, merely attempting to hack a working solution. Once I have some working raw material and an initial understanding of the mechanics of finding my desired numbers, then I can play with my solution to address time complexity, etc.

As I know I may need to find multiple correct number combinations, I start with an empty array, and plan to pass my successful number combos into it, then return the array of number combos.

If it were established at the beginning of a challenge that each sum + array combo could only have one successful solution, I could skip this step and instead return the correct addends once found.

let bruteForceTwoSum = (array, sum) => {

  let nums = []

  // find addends
  // pass them into nums array for storage

   return nums
}

First, I need to find the successful combos.

let bruteForceTwoSum = (array, sum) => {

  let nums = []

      for(let x in array){
        for(let y in array){
            // see if array[x] + array[y] === sum
            // save successful combos to nums array
        }
      }     
   return nums
}

I start by creating two loops, allowing me to iterate through every combination of numbers in the array. Now I can test the combos to see if any of them add up to sum.

let bruteForceTwoSum = (array, sum) => {

  let nums = []

      for(let x in array){
        for(let y in array){

          if (array[x] + array[y] === sum){
            nums.push([array[x], array[y]])
          }

        }
      }     
   return nums
}

If they do, I want to save them in my container array, which I’ll return after closing out my loops.

If I wanted the indices instead of the number elements themselves, I could instead push x & y to the nums array.

When run in the console, this function returns:

let array = [2, 3, 4, 3, 6, 7]
let sum = 6

bruteForceTwoSum(array, sum)
0: (2) [2, 4]
1: (2) [3, 3]
2: (2) [3, 3]
3: (2) [4, 2]
4: (2) [3, 3]
5: (2) [3, 3]

✔️ This function is finding and returning both [2, 4] and [3, 3].

✖️ It’s also returning them multiple times each. Not what we want.

I could try to check the nums array before pushing new number combos in, but the nested array format I’ve used makes this a hassle.

Note: It is perfectly reasonable to check nums.flat(Infinite) for the current elements, but I chose a slightly less computationally expensive option.

function bruteForceTwoSum(array, sum){
    let nums = []

    let prevNums = []

    for(let x in array){
        for(let y in array){
            if (array[x] + array[y] === sum){
                if(!!nums.length){ 
                    if (!prevNums.includes(array[x]) && !prevNums.includes(array[y])) {
                        prevNums.push(array[x])
                        nums.push([array[x], array[y]])
                    } 
                } else {
                    nums.push([array[x], array[y]])
                    prevNums.push(array[x])
                }
            }
        }
    }
   return nums
}

I’ve added an additional array prevNums for the sole purpose of storing found numbers, and can now check if a number has already been found & added before pushing it into nums. I only do this if nums is not empty.

What does this return?

let array = [2, 3, 4, 3, 6, 7]
let sum = 6
bruteForceTwoSum(array, sum)

0: (2) [2, 4]
1: (2) [3, 3]

Great! This is exactly the result I want. 🌟

2: BINARY SEARCH

Okay, so I have my first layer. I can find the combinations in an array that add up to a given sum, and return them in a clean, readable, non-redundant format.

However, what if my array were not [2, 3, 4, 3, 6, 7], but an array of thousands of numbers. Maybe even tens of thousands? Based on my first solution model, I’d have to iterate through endless combinations of numbers, even if my sum was still only 6.

That’s a huge waste of computing energy.

I’m not going to get too deeply into the concept of time complexity here, but I want to find a solution that will scale up better than my initial brute force model, due to requiring fewer computations.

In order to do that, I’m going to use a binary search.

I’m going to write a helper function to perform the binary search itself, then a second function that will utilize it to find the the correct addends for our given sum.

let binarySearch = (array, target, start=0, end=array.length-1) => {}

I’ll pass four parameters into the binarySearch helper function:

array: This is the same array we’ve been iterating through. However, any array passed into this function will need to be sorted low to high in order for this function to work!
target: This is the number we’re looking for — when applied in the twoSum solution, this will be the second addend in a pair.
start: The index at which we start iterating.
end: The index at which we stop iterating.

First things first, I want to find the middle of the array. If it contains an even number of elements, I’ll need to round down.

let binarySearch = (array, target, start=0, end=array.length-1) => {
    let midPoint = ~~(start + (end - start)/2)
}

I’m using the

(start + (end — start)/2)

method to get the midpoint so as to avoid some potential edge case errors as explained here.

I want to round the midpoint down to the nearest integer. I could use

Math.floor(start + (end — start)/2)

to handle my rounding, but the bitwise operator ~~ can do the same job of rounding down to the nearest integer a bit more quickly.

Since I’m going to be testing for several different cases in this function, I’m going to use a switch statement instead of an if/else statement.

let binarySearch = (array, target, start=0, end=array.length-1) => {
    let midPoint = ~~(start + (end - start)/2)

    switch(true){
        case array[start] === target:
            return array[start]
        case array[midPoint] === target:
            return array[midPoint]
        case array[end] === target:
            return array[end]
        case end - start === 0:
            return false 
    }
}

As I’m trying to make this approach a bit more efficient, I’m starting with a few cases that have relatively low time complexity cost.

I check for the cases where:

1: The first number is the target number.
2: The middle number is the target number.
3: The last number is the target number.
4: The array or array section through which I want to iterate is empty.

If none of these cases are true, I can move on to the iterating.

To do so, I’ll add two more cases:

let binarySearch = (array, target, start=0, end=array.length-1) => {
    let midPoint = ~~(start + (end - start)/2)

    switch(true){
        case array[start] === target:
            return array[start]
        case array[midPoint] === target:
            return array[midPoint]
        case array[end] === target:
            return array[end]
        case end - start === 0:
            return false
        case array[midPoint] > target:
            return binarySearch(array, target, start+1, midPoint-1)
        case array[midPoint] < target:
            return binarySearch(array, target, midPoint+1, end-1)    
    }
}

If the middle number is bigger than the target, I know that our target number is somewhere between array[start] and array[midpoint]. Therefore, I recursively call our binarySearch function on a new set of numbers, which will be only the elements between array[start] and array[midpoint].

Additionally, as we’ve already checked array[start] and array[midpoint] against to see if either matches our target number in our initial cases, we can exclude those from our list, leaving only the elements between array[start+1] and array[midpoint-1].

This will find a new start, end, and midpoint, and repeat the function on the now-halved collection of elements.

The last case is for if the middle number is smaller than the target number. In this case, we recursively call binarySearch on the collection of elements between array[midpoint+1] and array[end-1].

The logic to this is similar to the previous case — if the target number is greater than the midpoint in a sorted array, we can be confident that it won’t be in the first half, and can skip iterating through those, only looking in the second half of the array (minus the midpoint and end, which we’ve already checked for a match).

Using this recursive approach, we can find the desired number in an array by repeatedly halving the array, thus performing significantly fewer calculations than we would were we to iterate through an entire array every time we wanted to see if it contained a single element.

let binarySearch = (array, target, start=0, end=array.length-1) => {

    let midPoint = ~~(start + (end - start)/2)

    switch(true){
        case array[start] === target:
            return array[start]
        case array[midPoint] === target:
            return array[midPoint]
        case array[end] === target:
            return array[end]
        case end - start === 0:
            return false
        case array[midPoint] > target:
            return binarySearch(array, target, start+1, midPoint-1)
        case array[midPoint] < target:
            return binarySearch(array, target, midPoint+1, end-1)    
    }
    return false
}

Finally, I’ve added a return statement which allows this function to return false if the desired value is not present.

If this function works as desired, it will repeat until it either finds and returns the desired element or returns false, if the element is not present in the given array. Thus, the return value of the binarySearch function is either the desired element if it is present or false.

let array = [2, 3, 4, 3, 6, 7]

binarySearch(array, 9)
> false

binarySearch(array, 4)
> 4

Great! Now we have our working helper method 🌟

How do we apply this to our two-sum problem though?

We know that we need to start with a sorted array in order to use a binary search, so we’ll begin by sorting our initial array.

Then, we can set up the same basic structures we used previously, by creating two empty arrays: one for storing nested arrays containing our successful combinations of addends, and another for storing the elements in those combinations on the accessible top layer for later checking.

We’ll want to find all those combinations of elements, store them in our nums array, then return that array at the end, just like last time.


let binarySearchTwoSum = (array, sum) => {
    let sortedArray = array.sort()

    let nums = []
    let prevNums = []

    // find our number combos that add up to sum
    // check to see if we've already found them
    // if not, add them to nums

    return nums
}

This time, however, we won’t be creating nested loops to iterate through.

This time, we’re only iterating through our array once.

For each element, the value addend will be assigned to the number that would equal sum minus the element.

So, for a sum of 6 and an element of 2, addend would be the integer 4.

let binarySearchTwoSum = (array, sum) => {
    let sortedArray = array.sort()

    let nums = []
    let prevNums = []

    for (let i in sortedArray){
      // if sortedArray includes sum minus sortedArray[i], find it
      // push sortedArray[i] and the found number into nums
      // make sure no redundant numbers are pushed
    }
    return nums
}

That gives us a target integer, which is exactly what our binarySearch function needs.

So this time, we’ll use the binarySearch helper function to do the work for us.


let binarySearchTwoSum = (array, sum) => {
    let sortedArray = array.sort()

    let nums = []
    let prevNums = []

    for (let i in sortedArray){
        let addend = binarySearch(sortedArray, sum-sortedArray[i])
        if (!!addend && !prevNums.includes(array[i]) && !prevNums.includes(addend)){
            nums.push([sortedArray[i], addend])
            prevNums.push(addend)
        }
    }
    return nums
}

This way, instead of nesting iterators, we find what the second number in any given combo would be, then use the more efficient binary search method to see if that number is anywhere in our array.

Just as we did previously, we can use the prevNum array as a vehicle to store and check for previously found solutions, so we aren’t returning redundant combinations.

let array = [2, 3, 4, 3, 6, 7]
let sum = 6

binarySearchTwoSum(array, 6)

0: (2) [2, 4]
1: (2) [3, 3]

Great! This also returns our desired result 🌟

3: HASH

Using a binary search made our last solution more efficient than the brute force nested loops solution, but is it possible to improve even more?

There’s another tool available to help us efficiently check whether or now our desired addend exists in our array: a hash table.


let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      // for each array element, find its addend
      // see if addend is in array
      // if so
      // push array element and addend to nums
    }
    return nums
}

This time, we’re starting with an empty object, storageHash, in addition to our empty nums array.

Just as we did previously, we want to iterate through our array, and find the remainder of sum minus each element. Then, we want to see if that remainder exists in array. If it does, we’ll push both the remainder and the element into the nums array, which we’ll eventually return after our loop resolves.


let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      let addend = sum - array[i]

       // if addend is in array
            nums.push([addend, array[i]])
        }
    }
    return nums
}

We can find the desired addend by subtracting the current element from sum, but how can we tell if it exists in the area without using another nested loop or our binary search function?

let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      let addend = sum - array[i]

       // if addend is in array
            nums.push([addend, array[i]])
        }
          numsObj[array[i]] = i
    }
    return nums
}

Let’s start using storageHash.

With each iteration, we’ll add a new key-value pair to storageHash: a key of array[i] (the element), and a value of i (the index).

let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      let addend = sum - array[i]

        if (addend in storageHash){
            nums.push([addend, array[i]])
        }
        storageHash[array[i]] = i
    }
    return nums
}

Now, when we find a new addend, and want to check and see if it exists in our array, we can look up that key in storageHash. This is a nice operation to do, as it only requires checking a single specific place in memory, and doesn’t require iterating through a collection of connected elements.

If the key exists in storageHash, then we know that number also exists in array.

Thus, we can safely combine the addend we’ve checked against storageHash with our current array element, and add them to our nums array for later return.

Let’s test it out in the browser console:

let array = [2, 3, 4, 3, 6, 7]

hashTwoSum(array, 6)

> 0: (2) [2, 4]
> 1: (2) [3, 3]

Great! That gives returns our desired result. 🌟

Rather than iterating through every possible combination of array elements, or even finding the desired addend for each element and searching the array for it (even with something as relatively efficient as a binary search), we can now look up each potential addend directly using our hash table.

This approach is also nice because it doesn’t require sorting the initial array, or stripping superfluous correct combinations from the final array.

That’s it! Hopefully these solutions help you tackle the challenge of finding the two array elements that add up to a given sum.

If you’d like to read more about a variety of approaches to solving this problem and their respective benefits, I really like this writeup (warning: automatic pdf download!).

Getting Sleep() with Promises in JS

noam sauer-utley — Mon, 04 Nov 2019 22:40:01 +0000

Note: this post was originally published on Medium in November, 2019

Recently, I started building a very basic single page app to illustrate Fetch API usage in a cute and simple way.

When the user clicks a button styled like a tennis ball, a new dog image is fetched from the Dog API, and given a name fetched from the Namey API.

The dog’s image is loaded onto the page, and with each fetch, a name is added onto a list of fetched dogs.

However, once a few dogs were fetched, the document content stretched down quite far, and required a bit of scrolling to view. I decided to add a handy little link in the page footer which would scroll the viewer right up to the top, and re-fire the fetch cycle.




    function scrollAndThrow(){
        //smooth scroll back to top left corner of window
        window.scroll({
            top: 0, 
            left: 0, 
            behavior: 'smooth' 
           })
        // then click the button to trigger a new round of fetch   
        button.click()
    }

We can just scroll up the window, then trigger a newclick event on the button we’ve assigned to the variable button.

However, the the combo of the page scrolling up and the image fetch simultaneously re-firing looks pretty messy.

Yikes.

I wanted a way to slow things down, so the user would only see one thing happening on the page at a time.

I knew that if I could just pause for half a second between the scroll and the API Fetch, everything would look much smoother.

Suddenly, I missed Ruby’s sleep method. It was so nice to be able to schedule events to the exact time I wanted them to run!

I decided there had to be a way to construct my own dupe of that handy little method.

If you’re not familiar with JS Promises, it’s important to first understand that while Javascript is single-threaded (meaning it can only process one statement at a time), it is also asynchronous (meaning it can start processing a new statement before the previous statement has resolved, allowing it to multitask time-consuming processes in the background.).

Javascript uses Promises to track the resolution of those background processes, allowing us to set certain statements to run only when a time-consuming process has resolved and returned its completed result.

This is great for handling fetch requests and other time consuming processes, but it also gives us a way to tell our app to wait to process certain statements until exactly when we want them to be run.

I realized that I could exploit this functionality by building a Promise around Javascript’s built-in setTimeout() method.

Let’s make a promise:

setTimeout() takes in two parameters:

1: A function to be executed after the timer expires.

2: The time, in milliseconds (thousandths of a second), the timer should wait before the specified function or code is executed. If this argument is omitted, a value of 0 is used, meaning execute “immediately”, or more accurately, as soon as possible. Note that in either case, the actual delay may be longer than intended



return new Promise(resolve => setTimeout(resolve, ms))

We can create a new Promise, and tell setTimeout to pass the Promise resolve statement as setTimeout’s first parameter. setTimeout will delay for ms milliseconds, then resolve the promise. If we throw this in a function, we now have a handle little delay function ready to go!



 function sleep(ms) {
        // add ms millisecond timeout before promise resolution
        return new Promise(resolve => setTimeout(resolve, ms))
      }

Great! Now we made our replacement for Ruby’s sleep method.

Now let’s put it to use.

I decided to take advantage of one of ES6’s fresher bits of syntax for Promise handling: Async/await.



  async function delayedClick(){
        // await sleep function promise
        await sleep(700)
        // once resolved, click button
        button.click()
    }

delayedClick() knows from the get that it’s awaiting a promise resolution. We’re using our brand new sleep() function as the awaited promise, passing in our desired number of milliseconds (in this case, 700ms , or 7/10ths of a second ). Once that promise resolves, we can enter the action we want delayedClick() to enact. In this case, we’re going to click the button that re-starts the fetch and display cycle.

Now that we have our delay and desired action plugged into a method, we can plug delayedClick() into our existing scrollAndThrow() method as a replacement to button.click() to slow things down and clean up the onscreen process.




    function scrollAndThrow(){
        // smooth scroll back to top left corner of window
        window.scroll({
            top: 0, 
            left: 0, 
            behavior: 'smooth' 
           })
        // use sleep function promise to initiate 700 millisecond delay
        // then click button and initiate new fetch cycle
        delayedClick()
    }

The result: no more jaggedy mid-scroll fetch return and image load!

Much nicer!

Sometimes, it’s just good to get some sleep!

Notes:

Want to fetch a dog? Check out the repo here.
For dog pics, I used the Dog API: https://dog.ceo/dog-api/ .
for random first names, I used the muffinlabs Namey API: https://namey.muffinlabs.com/
Using Node.js? Turns out that there’s a handy little module built by Wes Bos that keeps this functionality ready to go for you. Check out Waait: https://www.npmjs.com/package/waait.

Finding the Top N per Group with SQL

noam sauer-utley — Sat, 19 Oct 2019 20:16:54 +0000

Note: this post was originally published on Medium in October, 2019

Solving Top N per Group with SQL

Getting to Know SQL

When I first encountered SQL, everything about it felt… strange. Trying to use it felt alien in some way I couldn’t quite put my finger on.

Trying to understand what was so different about this language, I spent some time reading aboutDeclarative vs. Imperative Programming, as well as Codd’s A Relational Model of Data for Large Shared Data Banks (Warning: PDF download link), and some basic info about Set Theory.

It quickly became obvious how powerful and elegant SQL could be when it came to handling larger volumes of data. I could just tell SQL exactly what data I wanted, and it would utilize efficient sets to select it, instead of iterating through each individual object and getting swamped.

Still, the #1 most helpful thing I did was spend a weekend writing queries and seeing the results, tweaking things and observing the changes.

I was introduced to Five Thirty Eight’s collection of data[¹][²] about The Daily Show with Jon Stewart through a Flatiron School bonus lab[³], and found it a perfect playground to query around, using beginner-friendly SQLite.

After parsing the CSV data into a SQLite database, I started trying to pull out simple bits of data.

First, as a test run, I wrote a simple query selecting all the shows from 1999.

I printed the results to my console, and received a neat list of info about all 166 episodes from 1999. Success!

I then tried a more specific query, and asked for the five guests with the most repeat appearances. A quick google search determined that the results I received were accurate. So far so good!

I tried again, querying the top occupation for guests, and got back “Actor” (unsurprising).

I played around with more simple queries, getting all the appearances from certain celebs, getting the number of guests with the same first name, the year with the most guest appearances overall, etc.

I was getting the hang of this SQL thing!

Then I tried a more advanced query. Instead of asking for the top guest or occupation out of the whole table, I wanted to find the top occupation per year. I figured it would be a little bit more complicated, but not much.

Except, when I started trying to write that query, I could only get a single result. I could get the most popular occupation of the whole database, or the year with the most different occupation, or something else that represented the database as a whole, but I couldn’t get a list of data representing information from each individual year.

I had no idea how to direct SQL to get the data I wanted.

I needed SQL to get me a layered result — to organize the data by year, then order the information from each year and return specific positions from that ordered list as results.

Every approach I could think of involved iterative sorting, which I knew wouldn’t be an effective use of this declarative, set-based tool.

Suddenly, SQL wasn’t feeling as friendly anymore.

I did some googling, and found a surprising volume of Stack Overflow[⁴] posts devoted to finding ways to communicate this exact sort of layered demand to various SQL database types. I was intrigued.

I did a little research, and learned that SQLite 3 added a handy window function called Rank that allows you to partition the rows of a SQL query’s result according to the criteria of your choice, then order those partitions as needed.

This was exactly the tool I needed!

Using Rank to Solve Top N per Group in SQLite

Let’s start with the innermost subquery, as set selection starts with the innermost subquery and refines outward.

First things first, we want to select occupation and year from our table “shows”, and get a count of the episode guest’s occupations, which we’ll reference as occupation_count. The results are grouped by year, then by occupation, so that we can get that occupation count per year.

        SELECT occupation, year, COUNT(occupation) AS occupation_count
        FROM shows
        GROUP BY year, occupation

This gives us the base data we want to organize and select from — SQL can ignore everything else.

Next, our middle subquery should use Rank to partition this data by year, making each year’s data into its own set. Then, it will create a ranking within each year, ordered by occupation_count, which we’ll call occupation_count_rank.

      SELECT occupation, year, occupation_count,
      RANK () OVER (
        PARTITION BY year
        ORDER BY occupation_count DESC
      ) occupation_count_rank
      FROM (
        SELECT occupation, year, COUNT(occupation) AS occupation_count
        FROM shows
        GROUP BY year, occupation
      )
      GROUP BY year, occupation

Now, we’ve got out occupations ranked in descending order by frequency, per year. This is also grouped by year first, then by occupation, as we want our query result to be ordered within those groups.

We’re already quite close to our desired query result, thanks to Rank, so our outer query can be quite simple. It simply selects the occupations from the result set supplied by the previous subquery, and returns only the occupations where the occupation_count_rank is equal to one. As we ordered our rank in descending order, the occupation with the highest count will be first.

    SELECT occupation
    FROM (
      SELECT occupation, year, occupation_count,
      RANK () OVER (
        PARTITION BY year
        ORDER BY occupation_count DESC
      ) occupation_count_rank
      FROM (
        SELECT occupation, year, COUNT(occupation) AS occupation_count
        FROM shows
        GROUP BY year, occupation
      )
      GROUP BY year, occupation
    )
    WHERE occupation_count_rank = 1;

If we throw this query into a heredoc and plug it into a ruby method, we can easily view the query result in the console.

Our query result? It’s just “actor”, seventeen times in a row. One for each year in our table. Which, again, unsurprising.

Okay, not super exciting. Still, that means that all three layers of our query are doing their jobs, and organizing the data to get exactly the results we want!

What if we didn’t want to just see actor listed out 17 times though?

Let’s shake things up a little.

    SELECT year, occupation
    FROM (
      SELECT occupation, year, occupation_count,
      RANK () OVER (
        PARTITION BY year
        ORDER BY occupation_count DESC
      ) occupation_count_rank
      FROM (
        SELECT occupation, year, COUNT(occupation) AS occupation_count
        FROM shows
        GROUP BY year, occupation
      )
      GROUP BY year, occupation
    )
    WHERE occupation_count_rank <= 5;

Here, we’ve kept both of our subqueries the same, only changing our outermost query. Instead of selecting just the occupation, let’s select the occupation AND the year, so we can keep things nice and organized. Then, instead of selecting only the occupation with occupation_count_rank equal to 1, we’re selecting the top five occupations for each year[⁵].

This gives us a lot more information! SQL returns the 5 most popular occupations for daily show guests, and also notes the year for us, so we don’t lose track halfway down the list.

Let’s make sure this is actually flexible — we can return the top one or top five per group, but let’s change what we’re returning.

Let’s write another similar query, this time querying the “genre” column of our database, which describes the genre of the guest’s Daily Show appearance. Let’s keep it clean this time, and only return the genre (not the year), and ask for the top 3 genres per year.

``` SELECT genre
FROM (
SELECT genre, year, genre_count,
RANK () OVER (
PARTITION BY year
ORDER BY genre_count DESC
) genre_count_rank
FROM (
SELECT genre, year, COUNT(genre) AS genre_count
FROM shows
GROUP BY year, genre
)
GROUP BY year, genre
)
WHERE genre_count_rank <= 3;



This tells us that “Acting” is usually in first place, but as the years go by, the more general “Media” begins to take over. “Comedy” and “Music” usually fill the remaining spot for the first years, but later in the 00’s, “Politician” becomes increasingly common, revealing a shift in the show’s tone.

Thanks, SQL.

![Lt. Uhura happily holds a purring tribble up to her ear.](https://cdn-images-1.medium.com/max/245/1*rAostJnbsZvaDH_Ac9wvwA.gif)

I queried a SQLite database in the above examples, but most popular SQL software include the RANK() function. If your preferred SQL software doesn’t have a rank function, I’d recommend looking into using a temporary table as a workaround, as explained [here](http://allenbrowne.com/ranking.html#temptable).

Notes & Links:

[1]: [Every Guest Jon Stewart Ever Had On 'The Daily Show'](https://fivethirtyeight.com/features/every-guest-jon-stewart-ever-had-on-the-daily-show/)



[3]: If you are a Flatiron Student and would like to talk about this lab, feel free to contact me via [Twitter](https://twitter.com/thevoidbutcozy).

[4]: Support labor unions in tech!

[5]: In the case of a tie, Rank will return both tied elements, and skip the value that would have held the second element were it not tied. If this will cause issues for you, look into using [Dense Rank() ](https://www.sqlitetutorial.net/sqlite-window-functions/sqlite-dense_rank/)instead!