Leetcode problem: minimum removal to make valid parentheses

Question

I was working on this problem on leetcode

Question

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or

It can be written as AB (A concatenated with B), where A and B are valid strings, or

It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted. 

Example 2:

Input: s = "))((" Output: "" Explanation: An empty string is also valid. 

My Solution

var minRemoveToMakeValid = function(s) { let myStack = []; let myObj = {}; // for storing index having invalid parentheses to be removed let out = ''; // O(n)?? for(let i = 0; i < s.length; i++){ let val = s[i] if(["(", ")"].includes(val)){ if(val == ')' && myStack[myStack.length -1]?.char == "("){ const rem = myStack.pop() delete myObj[rem.index] } else { myStack.push({ char: val, index: i }) myObj[i] = true } } } // O(n) for(let i = 0; i < s.length; i++){ if(!myObj[i]){ out += s[i] } } return out }; 

Isn't the above solution in O(N) time complexity? It seems so to me however the results show that it is not (the solution runtime is in bottom 8% percentile)

Why is this having such bad runtime even it seems like O(N)? or is it not so?

Answer 1

Performance

Your function is not O(n), because of the out += s[i] when constructing the result. Since JavaScript strings are immutable, every time you perform such a concatenation, it must construct a new string, which involves copying the out that it has constructed so far. When you do that in a loop, it becomes O(n²).

Instead, you want to work on an array, then use join() to build the resulting string all at once.

Data structures

myObj is the least informative name you could possibly pick for a variable. A better name might be isInvalidPos.

myStack is also not a wonderful name, but it does have the advantage of stating your intention to use the array as a stack. You use it to store all occurrences of ( and ), but really, you only care about storing (, since the only place where you inspect the contents is myStack[myStack.length -1]?.char == "(". So, in my suggested solution below, I've turned it into openParenPosStack.

Instead of building myObj, then writing a second loop that uses it to build out (the loop with the performance problem), why not build the output in the main loop?

Suggested solution

var minRemoveToMakeValid = function(s) { let openParenPosStack = []; // indexes of outstanding open parens let out = new Array(s.length); // array of valid characters in output for (let i = 0; i < s.length; i++) { switch (s[i]) { case '(': openParenPosStack.push(i); break; // assume invalid, until a close paren is encountered case ')': if (!openParenPosStack.length) { break; // close without matching open is invalid } out[openParenPosStack.pop()] = '('; // retroactively make the open paren valid // fall through default: out[i] = s[i]; // valid close paren, or misc character } } return out.join(''); }; console.log(minRemoveToMakeValid("lee(t(c)o)de)")); console.log(minRemoveToMakeValid("))(("));