I am super happy I solved myself, and did it slightly differently. Basically, I count opened and closed, and when closed > opened, I do a swap AND decrease closed AND increase opened counters. Accepted! =) def minSwaps(self, s: str) -> int: opened, closed = 0, 0 swaps = 0 for bracket in s: if bracket == '[': opened += 1 else: closed += 1 if closed > opened: swaps += 1 opened += 1 closed -= 1 return swaps
I just did this: class Solution: def minSwaps(self, s: str) -> int: flips, cSum = 0, 0; for b in s: if b == '[': cSum += 1; else: cSum -= 1; if cSum < 0: flips += 1; cSum = 1; return flips; Basically, if we ever have a negative sum, it means we have more closed brackets than we do open, so we have to make a swap and turn the ] into [, which means the current sum will be 1 again.
The simple intuitiion for this problem is that, 1. The number of open and closed brackets are same - given 2. They are just out of order, so we need to swap them - given 3. So how would you make it balanced, ? 4. It will become balanced once you swap the ones that are unbalanced. 5. So find out the brackets that are unbalanced, so we count closing brackets that dont have an associated open bracket. 6. We keep track of the maximum number of such closing brackets 7. since each swap would fix 2 of those closing brackets, we divide it by 2.
I am confusing why u did divide instead of minus since u said every swap remove 2. what I know so far is every swap will reduce by two because it will turn to be balanced and only left the unbalance one to swap/solve. For example, 3 -> 1 could be achieved by minus 2 why divide by two. i am stucking at there. pls help
i think theres people who can come up like this solution. Even after i solved nearly 300 leetcode and watched most of the tutorial of the videos, i could only start to solve the problem with a brute force, cannot come up with the optimized solution ever 😮💨
I CAN NEVER THINK OF THIS SOLUTION EVEN WITHOUT THE ALGO ....I SPENT 2 HOURS BUT COULDN'T THINK OF RESOLVING ALL TEST CASE IT WILL GET STUCK IN ONE OR ANOTHER CASE ....
I am afraid of Leetcode Weekly Contests because I don't know, I can solve it or not or maybe giveup in half-way. But I like the problems in leetcode and all other platforms. Don't judge me, I am an average human. Can anyone help me in this?
i used to think of myself as an average but since i've tried leetcode i come to know that i'm way below the bottom line 🙂i can't think of logics .... all the concepts of dp , recursive, tree or problems of knapsack or greedy approch i used to think of them in graphical way imagining in my head but during my academics i never even know those stuffs can be coded i hell have to idea how.... even being the easiest problem i get stuck quite often ....i wonder is it only me this stupid or there exists ppl ...i dont know how long will it take me to grab the problem solving flow or from where to begin with😭😭😭
I have coded for 8+ years now and I still like watching these videos
me too ,because we don't do this stuff in our daily work
goat
I am super happy I solved myself, and did it slightly differently. Basically, I count opened and closed, and when closed > opened, I do a swap AND decrease closed AND increase opened counters. Accepted! =)
def minSwaps(self, s: str) -> int:
opened, closed = 0, 0
swaps = 0
for bracket in s:
if bracket == '[':
opened += 1
else:
closed += 1
if closed > opened:
swaps += 1
opened += 1
closed -= 1
return swaps
Thank you!
Brilliant
To be honest your explanation even more intuitive. Thanks!
This is such a good solution
I thought about that approach, but i cant't physically explain on case with s = "]]][[["
I just did this:
class Solution:
def minSwaps(self, s: str) -> int:
flips, cSum = 0, 0;
for b in s:
if b == '[':
cSum += 1;
else:
cSum -= 1;
if cSum < 0:
flips += 1;
cSum = 1;
return flips;
Basically, if we ever have a negative sum, it means we have more closed brackets than we do open, so we have to make a swap and turn the ] into [, which means the current sum will be 1 again.
even I went with same way initially, just the thing is that it goes few ms slower than the another way which is given in video.
A good question for a contest but a bad one for an interview. It such a difficult solution to come to on your own.
I love the way he come up with the solution.
The simple intuitiion for this problem is that,
1. The number of open and closed brackets are same - given
2. They are just out of order, so we need to swap them - given
3. So how would you make it balanced, ?
4. It will become balanced once you swap the ones that are unbalanced.
5. So find out the brackets that are unbalanced, so we count closing brackets that dont have an associated open bracket.
6. We keep track of the maximum number of such closing brackets
7. since each swap would fix 2 of those closing brackets, we divide it by 2.
i love the way you explain. thanks for all your efforts.
I am confusing why u did divide instead of minus since u said every swap remove 2. what I know so far is every swap will reduce by two because it will turn to be balanced and only left the unbalance one to swap/solve. For example, 3 -> 1 could be achieved by minus 2 why divide by two. i am stucking at there. pls help
its the same thing bro, 100/2 = 50 means for every operation 100 is reduced by 2 so there are 50 such operations
Why only adding +1 to closing brackets why not vice versa i tried it but showing error
Why increment by one?
If we have odd number of unmatched, then
(unmatched+1)//2
alternative is math.ceil(unbalanced/2)
works for even number of unmatched too right? like for eg. " ] ] [ [ " requries only 1 which is ((maxClose = 2) + 1)/2 ? Tho math.ceil works too
Great explanation 👍👍👍
Amazing. I could have never thought of it... How to come up with approaches on our own?
Keep practising
i think theres people who can come up like this solution. Even after i solved nearly 300 leetcode and watched most of the tutorial of the videos, i could only start to solve the problem with a brute force, cannot come up with the optimized solution ever 😮💨
What is your current status?
but why increment by 1?
I think of it as (maxClose //2) + (maxClose%2)
If we have odd number of unmatched, alternative is math.ceil(unbalanced/2)
amazing！hope to solve neetcode all by following the series of video！
This one took years off my life
Best Explanation so far
do we really need maxClose in the code? It is always 0 and I think it's enough to do (close + 1 ) / 2.
actually he did not explain need of maxClose. For test case ][][][, your logic will fail
When you reach the end, close will be 0. So you need another variable
amazing explanation
Thanks but can you please elaborate why did we use max variable ?
to keep track of max of closecount at an instance
if we do not check the max variable, we may meet ]]][[[ and reach 0 in the end
I CAN NEVER THINK OF THIS SOLUTION EVEN WITHOUT THE ALGO ....I SPENT 2 HOURS BUT COULDN'T THINK OF RESOLVING ALL TEST CASE IT WILL GET STUCK IN ONE OR ANOTHER CASE ....
How did you come up with that?
great solution 🤟
Best explanation
good work.
its quite similar to Minimum Add to Make Parentheses Valid
Spoiler @ 4:32 MaxSwaps
It's wrong on many levels to ask such a question in an interview
Nobody cares about ur opinion....
very nice.
youu broo love you
Solve 0-1 knapsack, other tutorials on youtube are not that clear
watch aditya verma dp series
What happens if I just take open brackets. Won’t your solution return 0
this code doesn't work for multiple testcases
sorry, you must have made a mistake. this exact code worked for me.
class Solution:
def minSwaps(self, s: str) -> int:
stack = []
for ch in s:
if ch == '[':
stack.append(ch)
elif stack:
stack.pop()
return (len(stack)+1)//2
#approach_2:
class Solution:
def minSwaps(self, s: str) -> int:
size = 0
for char in s:
if char == '[': size += 1
elif size != 0 : size -= 1
return (size+1)//2
Mera dimaag kb chlega🥺🥺
I am afraid of Leetcode Weekly Contests because I don't know, I can solve it or not or maybe giveup in half-way. But I like the problems in leetcode and all other platforms. Don't judge me, I am an average human. Can anyone help me in this?
@@BhanuTejaPogiri-rj3qp Thank you!
i used to think of myself as an average but since i've tried leetcode i come to know that i'm way below the bottom line 🙂i can't think of logics .... all the concepts of dp , recursive, tree or problems of knapsack or greedy approch i used to think of them in graphical way imagining in my head but during my academics i never even know those stuffs can be coded i hell have to idea how.... even being the easiest problem i get stuck quite often ....i wonder is it only me this stupid or there exists ppl ...i dont know how long will it take me to grab the problem solving flow or from where to begin with😭😭😭
noice
annoying problem
Nice solution, can you please do video on 1055. Shortest Way to Form String from leetcode, I think there are multiple solutions possible for it.