First 15 minutes spent creating this Pseudocode:
// identify opening brackets
// let opening = '[{('
// save them in an ordered list
// identify closing brackets
// let = ')}]'
// As closing brackets come up, check if the last item in the opening brackets list matches
// if it doesn't (provided we add opening brackets to list before closing brackets), return false
// if it does, remove that opening from the list, we're good.
// so for like, '[[}]', if we do that process, we 1) add a [ to openings, add another [ to openings, check if } is the last item in openings,
// And find it ISN'T, so we exit. Nice.
// Let's try {[]{}}. We add { to the openings array, [ too, then check if ] type bracket is the --
// Okay so little detail here, we need a mapping of openings ']':'[', etc. We use that to check, I didn't mention that.
// So given that, we check if ']''s mapping is the last item int he opening list, and we find it is, we can maybe pop it off
// For brevity, next character we have '{', that's an opening, so we add it to openings, then we have '}', we check the mapping of '}', which is '{' against
// The last opening,
// It's be 33% of the alloted time, I think we're good
// And we find that they correspond, same shit, we remove that last opening from the list. We should be left with an opening list of just { now, which gets resolved with the last process.
// Okay I feel great about that.
// I am gonna go back and just reread the problem and see if I have all the requirements correct.
// Okay sweet, looks like s consists only of paren characters, no characters etc.
// I think I addressed it, but the trickiest rule is that "open brackets must be closed in the correct order"
// Yeah, I think that's working. Let me just spam some edge cases over the next minute before I get started
// "[[[[[[[[[]]]]]]]]]", "}"
// Ooh there's one - what if we START with an open bracket?
// So like, yeah, I just need to make sure I handle that -
// If I try to check the "openings" and it's empty, we're done - I have to return false
// Okay that was fruitful. Let me try a few more ']}]' isn't really different
// '{[{[' okay so this has no closings. I ALSO need to make sure THIS returns false,
// And I think I truly may have missed this case
// I guess it was implied that I have a hanging return true at the end, but what I really have to do is check to make sure that the "openings" array gets completely emptied
// And only return true if it does.
// Okay crap, 50% done with time. Let's give this a shot
// One more weird case - what about an empty string? I don't have to worry about it because the string has at least one character
// oh my godddddd
// okay ten minutes to go. I got this.Used the next 15 minutes to write this
function isValid(str){
if (str.length < 1){
console.log("based on my understanding of requirements, this should not have happened: case A")
return false
}
let openChars = '[{('
let closeChars = ']})'
let openings = []
let key = {
'}': '{',
']': '[',
')': '('
}
for (let char of str){
if (openChars.includes(char) ){
openings.push(char)
}
if (closeChars.includes(char)){
let lastOpen = openings[openings.length - 1]
if (lastOpen !== key[char]) return false
openings.pop() // lastOpen DOES === the current char, so we can get rid of that opener and continue
console.log(openings)
}
}
if (openings.length){
return false
}
return true
}Reflections
I finished with 2.5 minutes to go and got a function that worked first try, which I feel really good about! I think that spending 15 minutes to calmly work through edge cases worked really really well. Normally I just start coding as think, and maybe this is more efficient in some ways —
I guess to be fair, I DID code some things as I went, which I think is a good idea.
Something I didn’t do is have a section in my leetcode that was actionable notes, which might have helped with organization.
I also think I did a good job of going with an available working solution instead of an eloquent solution. 30 minutes really isn’t much time.
Claude
I asked Claude how I could have improved things, and he suggested using Sets instead of strings, and using Maps instead of normal js objects. Those make sense and would be a great way to flex my understanding of these data sets (dishonestly, as I don’t use these too often at the moment), but don’t really seem that important.
What I did like was checking for even or odd numbered inputs for early returns.
He also suggested checking for closing brackets first…dont’ totally understand this approach:
for (let char of s){
if (bracketMap.has(char)){
if (openings.pop() !== bracketMap.get(char)) return false;
} else {
openings.push(char);
}
}This switch statement suggestion is really interesting though:
for (let char of s){
switch(char)
{ case '(': case '{': case '[':
openings.push(char);
break;
case ')': case '}': case ']':
if (openings.pop() !== bracketMap.get(char)) return false;
break;
}
}Update
Paul Winkler, a colleague of mine, noticed that I failed to handle an edge case that I did notice in my pseudocode, which was:
// Ooh there's one - what if we START with an open bracket?Although the initial code passes leetcode’s submission tests, I don’t seem to be handling this. Leetcode is pretty stringent, so I wondered how this could be. I checked the submission criteria:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
And found that a case of } would definitely fail criteria item #3, but maybe this is not a case that is run by leetcode. In fact, I think it must not be a case run by leetcode, since if it was I think this case might get an Out of bounds error on the second line here:
if (closeChars.includes(char)){
let lastOpen = openings[openings.length - 1]
if (lastOpen !== key[char]) return false
openings.pop() // lastOpen DOES === the current char, so we can get rid of that opener and continue
console.log(openings)
}But then I went and tested this case ] as well as []] just to be safe, and my function evaluated these as false after all. So, edge case handled…just not intentionally. My ego is a little bruised, since it seems I got a bit lucky, but that tracks a bit better with how leetcode is supposed to go.
First off, it turns out that getting the length of an empty array doesn’t through an error in JavaScript.
But it does mean that if there are no openings left, lastOpen is undefined and we’ll return false because there is no corresponding open tag to our closing tag! This applies even if we only have a single closing tag as our input string.
In summary, I lucked out, and that’s why this is the only leetcode that I have been able to approach blind and finish in 30 minutes. Luckily, because it was only the second one ever tried, the result was that I gained a huge amount of unearned confidence!
That confidence formed a sort of force field, protecting me from the grueling leetcode studying that followed, ultimately leaving me vulnerable, optimistic, and perfectly situated to fail my technical interview with Figma! So it goes.
Re-attempt 2: August 24
Remembered a little bit of this, mostly just that I had an object mapping closing to opening parens. And that I didn’t need an object doing the opposite.
Time: 9 minutes
let anOpener = false
let thang = {
"}": "{",
")": "(",
"]": "["
}
let opens = "{[("
let openers = []
for (const p of s){
if (opens.includes(p)){
anOpener = true
openers.push(p)
} else {
// closer territory
let partner = thang[p]
// check the last opener to see if it is the same as the closer
if (openers[openers.length - 1] === partner){
openers.pop()
} else {
return false
}
}
}
if (!openers.length && anOpener) return true
return false
};My initial small mistake is that I thought I might need 2 for loops.
Above, I talk about handling edge cases by luck. This came back to bite me - by running my code, I got hit by a single edge case I didn’t see coming, and it took me two tries to handle it.
My first attempt was naive - I quickly created the anOpener variable to check that there was at least one opener, a misguided attempt that did solve the case where I only got }, thinking of that as somehow unique. But the problem here isn’t that there’s just one closer and no openers, it’s more broadly how the closer shows up with no corresponding opener, which should always result in failure.
So here’s a slightly simplified version:
var isValid = function(s) {
let thang = {
"}": "{",
")": "(",
"]": "["
}
let opens = "{[("
let openers = []
for (const p of s){
if (opens.includes(p)){
anOpener = true
openers.push(p)
} else {
// closer territory
let partner = thang[p]
// check the last opener to see if it is the same as the closer
if (openers[openers.length - 1] === partner){
openers.pop()
} else {
return false
}
}
}
if (!openers.length) return true
return false
};