Ransom Note Challenge— two different approaches
Why data structures are important in solving coding problems.
Introduction
When I didn’t know data structures, nested for-loops were my bread and butter for solving, or more accurately brute-forcing, coding challenges. In this article, I’ll show you how I tackled a relatively easy coding challenge in two different ways and why one method is better than the other. But before getting started you must know about big O notation and why it’s important.
Big O Notation
Big O Notation, simply put, shows us how efficiently our code would perform in worst-case scenarios. When data is very tiny, the difference is minimal, but as the size of input data increases, so too does the relative difference between each Big O complexity to linear, quadratic, exponential, or even factorial levels. These complexities are represented, you guessed it, by a big O. See the picture below for a visual representation of each one.
The Coding Challenge
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letter from magazine and false if otherwise.
Approach One: Nested For-Loops
When I first looked at this problem, I thought it was simple enough. All I have to do is iterate through each character in ransomNote and compare them one by one to each character in magazine while avoiding complications like overcounting duplicate letters.
To keep the explanation of this approach brief, look at my complete code below along with the comments for each step of the way:
public static boolean canConstruct(String ransomNote, String magazine) {
/*First check if the ransomNote string is larger than magazine, if
that's the case then it is already impossible and therefore false */
if (ransomNote.length() > magazine.length()){
return false;
}
/*Next we create String builder objects containing our two string
arguments. This way we can modify them in our for-loops*/
StringBuilder rString = new StringBuilder(ransomNote);
StringBuilder mString = new StringBuilder(magazine);
/*Nested for loops where the outer-loop represents the character
index for ransomNote, and the inner-loop for magazine*/
for (int i=0; i< rString.length(); i++){
for (int j=0; j< mString.length(); j++){
/*This if-statement will check if the character found in each
String index are equal to each other */
if(rString.charAt(i)==mString.charAt(j)){
/*If equal we use the following stringbuilder method
to replace that character with an empty space*/
rString.setCharAt(i,' ');
mString.setCharAt(j, ' ');
}
}
}
/*Once the loops are finished we convert our ransomNote stringbuilder
object back to a regular string */
ransomNote = rString.toString();
/*Finally we check if our String is blank (not empty) and return true
if it is*/
if (ransomNote.isBlank()){
return true;
}
/*Otherwise, we return false */
return false;
}Most of the comments in my code above are self-explanatory, but you probably have a few questions. For example, why did I not use the String method replace(old char,new char) instead? The problem with this is this method replaces ALL instances of a character which will then mess up the entire checking process in the if-statement. Stringbuilder’s setCharAt(index,new char) doesn’t have this problem. In addition to this, there is also the approach of deleting each character that has been found equal, but this would mess with the for-loops as they rely on the length of the string to decide whether it needs to loop again. Also, the reason I set the equal characters to blank in the first place is to avoid overcounting duplicate characters which will give us an incorrect result. It’s an easier way of tracking which characters have been found without a repeat character messing it all up. Once the ransomNote StringBuilder object is completely blank, that confirms that magazine contains all letters needed to construct the word it holds.
Now, why is this method considered inferior? Nested for-loops are needlessly complex and cause a run-time of quadratic proportions, also known as O(n²) in Big O notation, which is not what we want when optimization and efficiency are key goals for every software engineer. So, let’s look at a better approach.
Approach Two: HashMap
A HashMap data structure stores data sets in key-value pairs as opposed to an index like an array would. This method of collecting allows HashMaps to find a value, or piece of data, in a constant time of O(1) using its contains method. Compare this with something like an ArrayList, which would need a for-loop to iterate through its entire index to find that same data in a linear time of O(n). This would depend on how big the data set is and how far away the piece of needed data is from the beginning/end of the ArrayList.
Now look at the completed code below and its comments:
public static boolean canConstruct(String ransomNote, String magazine) {
/*Same as last time we check the length of the ransomeNote string
against magazine to decide if it's impossible from the getgo */
if (ransomNote.length() > magazine.length()){
return false;
}
/*We create a HashMap that will store a Character key,
paired with an Integer value */
HashMap<Character,Integer> letterMap = new HashMap<>();
/*For-loop to iterate through each character in magazine string
and put the data into our HashMap*/
for(int i=0; i<magazine.length(); i++){
/* if-else statement to put each character as a key, and the amount
of time it shows up in the String as a value paired with it*/
if(letterMap.containsKey(magazine.charAt(i))){
letterMap.put(magazine.charAt(i),letterMap.get(magazine.charAt(i))+1);
}else{
letterMap.put(magazine.charAt(i),1);
}
}
/*For-loop to iterate through each character in ransomNote string */
for(int i=0; i<ransomNote.length(); i++){
/*if statement checks whether our HashMap contains the character
found in ransomNote string at index i*/
if(letterMap.containsKey(ransomNote.charAt(i))){
/*if it does contain the character then we update our HashMap by
decreasing the value paired with that character key*/
letterMap.put(ransomNote.charAt(i),letterMap.get(ransomNote.charAt(i))-1);
/*if a key's value ever drops to -1 then we know that
ransomNote contains an extra repeat of a character that we
don't have in magazine, so we return false*/
if(letterMap.containsValue(-1)){
return false;
}
/*If the character isn't found in our HashMap at all then we also
return false as then it's impossible to construct the String*/
}else{
return false;
}
}
/*Once getting out of the for-loop is a success then that means the HashMap
is carrying a sufficent amount of characters needed to construct the
ransomNote string, so we return true*/
return true;
}In the first for-loop, we have an if-else statement that checks whether our HashMap keyset has the character found in index i of String magazine. If it already has this character then it just adds 1 to the value of this pair. If not then it’ll add the character along with a value of 1. This allows us to have each character as a key and the corresponding value representing the amount of that character we have. The purpose of the next for-loop is already explained well in the comments above.
Using this HashMap approach we’ve reduced our complexity from O(n²) to O(n). There is a vast difference in access time here that is more noticeable the bigger the size of the input data is. You also might be wondering if using two for-loops or nested if-statements increase the complexity: In either of these cases, the complexity remains the same, so we’re good. Can this code be improved further? Of course, it can, but I’ll let you figure that out on your own.
Conclusion
I hope I was able to convince you a little bit at least about the importance of understanding data structures, their advantages, and how to leverage that in your code. Now go out there and get to coding with data structures!
Thanks for reading. If you enjoyed this feel free to leave feedback and maybe your own take on how you’d improve my code!
