Minimum Remove to Make Valid Parentheses - Leetcode 1249 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:24 - Drawing Explanation
10:41 - Coding Explanation
leetcode 1249
#neetcode #leetcode #python

[@gopalch.karmakar7137]

Even though I solve LeetCode problems daily on my own, I still find immense value in watching your NeetCode videos. Your insights and perspectives add depth to my understanding and help me approach problems from different angles. ❤

[@bekzodabdumutaliev1733]

Thanks for sharing your explanation, really appreciate that!

[@bekzodabdumutaliev1733]

this is needed for new learner

[@karthik_ujjuru]

awesome explanation thanks bro

[@phanthe3471]

a great explanation, I solved it today using a stack. But this way is giving another way of thinking

[@thisisnotok2100]

stack was may thought too

[@phanthe3471]

@@thisisnotok2100 Hello my same-thought bro 😊😄

[@rosefromdead]

i wonder why stack solution was not better, both of them have same time complexity and space complexity

[@phanthe3471]

@@rosefromdead i think the stack is good also.
The solution from neetcode is another way to consider

[@satyamjha68]

Solved it !

[@haydenthai935]

Death taxes and neetcode making a video on the leetcode daily ❤

[@pratiklondhe5167]

it would be also good to see how to optimize this code more

[@Amadorse]

awesome thanks

[@mnikhil8491]

can u create playlist of leetcode on the basis of topics like arrays , list , binary tree
u are great by the way

[@panzach]

Thanks for sharing! One small note for future videos is that the singular of "parentheses" is "parenthesis"

[@Murphyalex]

I've looked at numerous solutions today and I just can't believe that every video talks about a single "parenthesee". Does nobody know that it's one parenthesis, two parentheses etc.??

[@pushkarsaini2]

Please make a video on leetcode 31: next permutaion

[@rileysikes9285]

Glorious

[@priyanshagarwal8490]

Please make a video on 443. String Compression

[@greatbuuren]

Why not do `for c in reversed(res)`? I think it's just as Pythonic and might be easier to understand for beginners

[@JLSXMK8]

You can also do the same when joining the filtered characters into the final string too. I agree, that will probably be easier for beginners to understand.

[@greatbuuren]

Can you please show the most concise solution you can come up with?

[@kevinwang8632]

Why didn't we just do del res[index] instead of making another array called filtered?

[@nq2c]

The delete operation takes O(N) time because you have to shift every element of the array, making it inefficient!

[@sidhartheleswarapu]

Do you think using Java instead makes it harder to do these problems?

[@sadanandabanerjee4355]

Hi...sir , i am from india. I have complete more than 250 problems and pratice daily basis , POTD and some extra questions but when i participate on weekly and biweekly contest i can't solve more than one question .
Can you make any video about this..or any solution.
Thank you sir.

[@ShivendraPratap524]

sir what if there's a surplus of opening brackets "("

[@NeetCodeIO]

That's what the second loop is for

[@ShivendraPratap524]

@@NeetCodeIO thanks for the reply,
Actually I commented before the part of second loop,

[@annlaosun6260]

omg, how would you come up with the solution in an interview if you have never seen this question before.

[@spsc07]

how's the tooth pain?

[@NeetCodeIO]

Getting better, thanks for asking! :)

[@spsc07]

@@NeetCodeIO get well soon!

[@messi_codes]

You made it hard unnecessarily, just solve in following easy way it has same TC + SC
HAPPY TO BE DISCUSS IF YOU WANT TO :)
string minRemoveToMakeValid(string s) {
// get all invalids and its indexes in the stack
stack st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(')
st.push({s[i], i});
else if (s[i] == ')') {
if (!st.empty() and st.top().first == '(')
st.pop();
else
st.push({s[i], i});
}
}
string res;
while (!st.empty()) {
int idx = st.top().second;
st.pop();
s[idx] = '#'; // marking the indexes which we have to ignore in
// final result string
}
for (auto& c : s) {
if (c != '#')
res.push_back(c);
}
return res;
}

[@NeetCodeIO]

You have 3 loops, how is this more simple?

[@ashutoshjha6450]

class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = list()
spare = list()
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
elif s[i] == ')':
if len(stack) > 0:
stack.pop()
else:
spare.append(i)
res = ''
badChars = set(stack) | set(spare)
for i in range(len(s)):
if i in badChars:
continue
else:
res += s[i]
return res
my solution... It looks like O(n) but it was only better than 25%, what could be the reason?

[@fauzudheenabdulhameed8399]

I just kept track of the elements to be deleted along with the queue:
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
q = []
ind = []
for i in range(len(s)):
if s[i] == '(':
q.append(s[i])
ind.append(i)
elif s[i] == ')':
if q and q[-1] == '(':
q.pop()
ind.pop()
else:
q.append(s[i])
ind.append(i)
ind.sort(reverse=True)
for j in ind:
s = s[:j] + s[j+1:]
return s

[@nilavarasan5501]

string minRemoveToMakeValid(string s) {
stack index;
int i=0;
for(int j=0;j this is could potenially be the best-code for this sum

[@garsidrag]

as a terrible beginner myself, id say that res[::-1]: is something i had to look into because you kinda skipped over how it worked, idk if youd wanna bother wasting time explaining something like that, especially on a medium problem video, but i just mention it because of what you said towards the end of the video.

[@ameyakawade1038]

Is this solution is it efficient ? :
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
res = [""] * len(s)
st = 0
idx = 0
for ch in s:
if ch == "(":
res[idx] = ch
idx += 1
st += 1
elif ch == ")":
if st > 0:
res[idx] = ch
idx += 1
st -= 1
else:
res[idx] = ch
idx += 1
if st == 0:
return "".join(res)
cnt = st
i = idx - 1
while i >= 0 and cnt > 0:
if res[i] == "(":
res[i] = ""
cnt -= 1
i -= 1
return "".join(res)

[@aashishbathe]

Python more efficient solution -
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
count = 0
res = []
for char in s:
if char != ')':
res.append(char)
if char == '(':
count += 1
else:
if count > 0:
count -= 1
res.append(char)
if count != 0:
for i in range(len(res) - 1, -1, -1):
if res[i] == '(' and count > 0:
del res[i]
count -= 1
elif count == 0:
break
return ''.join(res)

[@NeetCodeIO]

Isn't del res[i] technically O(n)?

[@michael._.]

just assign res[i] = '', you don't need del

[@aashishbathe]

@@NeetCodeIO oh yes, I just checked it and it is technically O(N). It's because of the shift ig, but it just gave me a lesser time in submission. I do know it depends on leetcode servers. But I thought it would be more efficient. My bad.

[@aashishbathe]

@@michael._. this works very well indeed, thanks for letting me know. I previously did think of this, and assigned it as '-', but then had to replace it by space. Direct assigning as '' is smart.

[@spsc07]

in CPP
```
class Solution {
public:
string minRemoveToMakeValid(string s)
{
string ans;
stack tmp;
for(int i=0;i=0;--i)
{
if(!tmp.empty()&&tmp.top()==i)
tmp.pop();
else
ans+=s[i];
}
reverse(ans.begin(),ans.end());
return ans;
}
};
```

[@ankitagrawal4477]

In these code it shows memory limit exceeded

[@spsc07]

@@ankitagrawal4477 uhm idk man check again, Ill paste it
class Solution {
public:
string minRemoveToMakeValid(string s)
{
string ans;
stack tmp;
for(int i=0;i=0;--i)
{
if(!tmp.empty()&&tmp.top()==i)
tmp.pop();
else
ans+=s[i];
}
reverse(ans.begin(),ans.end());
return ans;
}
};

[@ankitagrawal4477]

@@spsc07 yes it works it showing MLE when I am writing the last else ans=ans+s[i] instead using shortcut