Solving Meta's 2022 Most Asked Interview Question

Meta's most asked coding interview question in 2022 is the problem "Minimum remove to make valid parentheses". The problem involves the use of a stack and set data structure.
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos

[@hnkien]

At 4:22, I think we need to pop from stack item 4, not item 2. Great video as usual!

[@AlgosWithMichael]

Woops, yea good catch

[@goahnary]

Right. That would be a queue. This works but I think a proper stack makes the most sense when you get to the final result as it removes unmatched pairs.

[@correabuscar]

great explanation, loved it

[@clot4764]

I haven’t seen yet but you are the best, just come from your triangle problem, love your videos ❤ please upload more❤

[@DominikLoeffler1]

Great explanation! It should be emphasized that "set" here really means a hash table data structure (line 4 in the code). One might be tempted to use a set that's ordered, e.g. std::set in C++ which implements a binary search tree, rebalancing itself with each insert/erase/find. While the latter could be used and would still achieve correctness, it would do so at O(log(N)) vs. the former which does it at O(1). In other words, overall complexity with an ordered set would be much worse at O(N log(N)), after the usual dropping of constants

[@MrMakemusicmike]

Very good.
Clear information.

[@hosseinbafekr6205]

Thanks for your clear explanation!

[@AlgosWithMichael]

No problem!

[@furquan5974]

Excellent explanation 👍

[@JackAbou2]

what platform did you use to code and run the solution? thanks great video BTW

[@EMdragonKnight]

Good explanation. Is converting the string to an array necessary? Strings in C#/Java also have indeces.

[@Gangrelguy]

Add two closing parentheses on the end of the string being parsed and it breaks this algorithm.

[@mikedelta658]

thank you

[@zaza.javakhishvili]

I do not think that it will work on all string variations.

[@correabuscar]

you say stack but I see (FIFO) queue at 4:20

[@user-hd4sl]

It was a mistake he made

[@destiny-fox1990]

Theres a space o(1) solution thats expected

[@pranavtiwari8682]

What is it?

[@destiny-fox1990]

@@pranavtiwari8682 look it up on LC discussion.

[@SmokingNoir]

not how a stack works

[@SC2Edu]

Easy but fun

[@sameer9368]

Hi muinos....I am from India....please make more video.... 😎

[@AlgosWithMichael]

More are on the way :)

[@ravividap1227]

Why set and why not simple array?

[@nitishjoshi2637]

In case of an array, you will have to iterate over it to find if it contains the index, which becomes an O(N) operation. In case of a Set, you don't need to iterate and the operation is O(1).

[@ravividap1227]

@@nitishjoshi2637 i did it with arrays 😀 declared an array of size input string length then store unique value at indexes to identify. I could still do it in order of N overall time complexity

[@nitishjoshi2637]

@@ravividap1227 Yes, the overall time complexity will not change, as the worst case would still be O(N). But if you are looking to optimize your code during interviews or otherwise, using a HashSet would definitely help 🙂

[@rugvedwagh9434]

First here mike

[@AlgosWithMichael]

Haha nice

[@vinayyelleti2714]

stack.pop is char and how this is being added to set of integers..at line 16
indexToRemove.add(stack.pop());