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.
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
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).
@@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
@@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 🙂
![Data Structures for Coding Interviews [In 10 Minutes]](http://i.ytimg.com/vi/_hiMlJDHQJ4/mqdefault.jpg)
At 4:22, I think we need to pop from stack item 4, not item 2. Great video as usual!
Woops, yea good catch
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.
thank you for your comment, I was confused and same to read comments if anyone else got confused :D
great explanation, loved it
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
I haven’t seen yet but you are the best, just come from your triangle problem, love your videos ❤ please upload more❤
Very good.
Clear information.
Add two closing parentheses on the end of the string being parsed and it breaks this algorithm.
What about "Foo(bar))(". That's valid since the number of ( matches the number of )
Theres a space o(1) solution thats expected
What is it?
@@pranavtiwari8682 look it up on LC discussion.
not how a stack works
Excellent explanation 👍
Thanks for your clear explanation!
No problem!
what platform did you use to code and run the solution? thanks great video BTW
you say stack but I see (FIFO) queue at 4:20
It was a mistake he made
Good explanation. Is converting the string to an array necessary? Strings in C#/Java also have indeces.
I do not think that it will work on all string variations.
thank you
Hi muinos....I am from India....please make more video.... 😎
More are on the way :)
Why set and why not simple array?
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).
@@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
@@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 🙂
Easy but fun
First here mike
Haha nice
stack.pop is char and how this is being added to set of integers..at line 16
indexToRemove.add(stack.pop());