Make the logic more obviously correct
This piece of code made me doubt if the logic is correct:
for(let entry of myMap){
if(entry[1][1] == 1){
return entry[1][0]
}
}
My first doubt was the iteration order of Map
entries. In most languages that I know, the iteration order of map data structures is undefined. I had to lookup in the docs to see that indeed Map
in JavaScript remembers the original insertion order of the keys. So far so good.
My second doubt was, ok so for the program to work correctly, the entries in myMap
would have to be inserted in the correct order. And they are, but I had to read and understand how myMap
is populated to be convinced.
My natural approach to find the first character would be to iterate over the input string:
for (let i = 0; i < s.length; i++) {
const [ index, count ] = myMap.get(s[i]);
if (count === 1) {
return index;
}
}
Written like this, I don't have any doubts about the iteration order of maps, or how myMap
was populated. It's evident that I'm iterating over letters in the correct order, so as long as myMap
contains what I think it does, this code looks correct.
Written like this, I realize one more thing. I don't need the index in the map entry anymore, since I already have it, in the i
variable. So I go ahead and change myMap
to contain only the counts of characters. At this point, I also rename some variables to names as they feel natural:
const counts = new Map();
for (let index = 0; index < s.length; index++) {
const letter = s[index];
if (!counts.has(letter)) {
counts.set(letter, 1);
} else {
counts.set(letter, counts.get(letter) + 1);
}
}
for (let index = 0; index < s.length; index++) {
const count = counts.get(s[index]);
if (count === 1) {
return index;
}
}
This turns out to be much faster than the previous version. The significant change is that the values in the map are simple integers instead of arrays.
Checking if a map contains a key correctly
Looking at this kind of code out of context, I would suspect a possible bug.
This is not the correct way to check if a map does not contain a key.
const val = myMap.get(s[i])
if(!val){
Because, if the map could contain falsy values, such as false
, or 0
, or ''
, or null
, or undefined
(... I hope I didn't miss anything!), then the condition would pass, and most probably that would not be intended.
The correct way:
if (!myMap.has(s[i])) {
The current code works fine because all the keys are guaranteed to be letters of the English alphabet, and none of them are falsy. As a matter of principle, it's good to build the habit of using the correct idiom when working with maps.