I'm reading a book about data structures and algorithms, and currently still learning and being challenged on time complexity. As of now, the book is showing examples of different algorithms and asking the reader to dissect them and attempt to figure out their time complexities.
A neat takeaway from the book was that more often than not, a double nested loop will almost always be O(n²), however, there are some cases where this will not be true. The book does a very good job of showing how algorithm times will eventually take longer than others, and that is what you need to keep in mind, in the long run, which is faster.
The book posed a challenge to write an algorithm that would find the first unique character in a string that has a time complexity of 0(N²). My initial thought was that the algorithm I write will have to loop through the string as we will not truly know if the character we come across is unique until we have checked the whole string. So I will be starting at the end of the string and working my way to the beginning. As I loop through the string, I make the following steps.
Step 1: I will be checking a hash map for a value with the character as a key. If it does not exist, I create a key with that character and set the value to 1. In the event the key-value pair exists, I will increment the value.
Step 2: I will check if that key-value pair has a value of 1, if it is I set a unique variable to be that character.
So, I reset my unique variable anytime I create a new key-value pair, which will have a value of 1. Since I am working backward, the last unique value I find will actually be the first unique value in the string. See the code with instructions below. In this example, I am running the algorithm on the string “minimum” the return value would be “n”. This was the best way I could think of to create this algorithm without looping over the string data multiple times.
