Beating AlgoExpert: Generate Document
Today’s challenge in beating AlgoExpert is a little more controversial in comparing speeds as the typical speed comparison is done using Big O notation, measuring for the growth rate as the input size grows. But sometimes that measurement isn’t effective. Consider an algorithm designed to solve the mastermind game or a sudoku puzzle. You could create different variations of the algo, but the input doesn’t grow in size so you can’t really measure the effectiveness by big O.
The problem I am presenting you today does have a growing input but we are going to optimize using lessons from Toyota’s very own Taiichi Ohno, perhaps the most influential industrial engineer of the 21st century and father of the Toyota Production System. This system is often referred to as Just In Time production, which worked to produce their output… you guessed it… just in time. I have mentioned it before and there is a lot of valuable lessons to be learned from it.
Today’s problem can be fond here on AlgoExpert and is also available on LeetCode here. The prompt: given two strings, document and characters, can document be created by the characters available in characters. I prefer LeetCode’s prompt though where the two strings are named ransomNote and magazine. To make things easier, we will use LeetCode’s variable names.
The Bad Method
When I first started coding, a friend gave me this problem as they just asked someone to solve it as part of an interview for Amazon. With novice thinking I attempted to solve it and iterated through the characters in ransomNote and checked to see if it existed in magazine, then removed the character as seen below.
This has its benefits as you are keeping your Big O memory usage down to 1, however, for each char in ransomNote, you have to iterate through all of magazine and the runtime can be costly if you have a large magazine string. Big O runtime: m*n where m is the length of magazine and n is the length of ransomNote.
The Algo Expert Solution
Their solution uses much more memory but keeps its iteration count down to one for magazine. By iterating through magazine first and building up a count of how many times each character appears in magazine, they can then iterate through ransomNote and deduct one from the count for each character. If they come across a character that has no more availability, the function returns false. Take a look below:
This does increase the Big O space complexity up to O(m) but it is worth the trade to reduce the Big O time complexity down to O(m+n). A great tradeoff, but you are still cycling through an entire a magazine to check the characters. I personally have never been involved with a ransom note, but I have picked up a magazine before and I do know that they are pretty darn long. I mean has anyone ever had the time to read one cover to cover? And what if we could see that all the characters used in the ransom note were all available on the cover, would we want to keep reading the whole magazine?
My “Just In Time” Solution
Similar to the solution above we track all the characters we come across, but the key is we only go as far as we need. We start by iterating through each character of ransomNote. If get to a character in ransomNote that doesn’t exist in characterCounts, we then continue iterating through magazine until we find what we are looking for, tallying up the character counts as we go. Once we find what we are looking for though, we stop and go to the next character of ransomNote. This can be seen below:
I know you’re thinking, technically it’s still the same Big O run time, because what if the characters aren’t in the magazine or the last one is located at the very end? Well yeah, then we are running the same speed as AlgoExpert’s code. But let’s be glass half full for a second and consider the case that all the characters are located at the beginning, we just saved ourselves a bunch of processing time. This saved time can be very important to the user who is trying to load information from an app or to the small businesses who needs to budget their use of micro services. More importantly, this saved time can be extremely important to someone who is kidnapped and held for ransom and now that you don’t have to read the entire magazine you have more time to go save whomever is in danger.
Thank you for reading and I hoped you enjoyed the content. Please like, share, subscribe, comment and dance like no one is watching. Until next time… keep coding smart.
