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?

200_success · Accepted Answer · 2022-04-11 19:27:24Z

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("))(("));

Thanks. Your final solution has much better TC results. However, just for sake of testing I replaced the string out += s[i] with out.push(s[i]), keeping everything else same (out is now an array, I do return out.join('') at the end). But still there is no difference in time taken by my program. Why is that? — D_S_X
– D_S_X, Commented Apr 12, 2022 at 6:22
Also, i don't really understand how this line in your code is working : out[openParenPosStack.pop()] = '(' can you please explain more — D_S_X
– D_S_X, Commented Apr 12, 2022 at 6:57
Just a guess about the performance issue: did you allocate the array with the size hint like I did, with let out = new Array(s.length)? Or did you simply write let out = [], in which case out.push(s[i]) could still require a reallocation and copy? — 200_success
– 200_success, Commented Apr 12, 2022 at 8:26
out[openParenPosStack.pop()] = '(' does just what the comment says. Since openParenPosStack.pop() returns the index of the last '(' seen in s that hasn't already been matched by a valid ')', it retroactively copies that '(' from s to out at that position. — 200_success
– 200_success, Commented Apr 12, 2022 at 8:31
Tried both ways ... pretty similar results in both cases. Actually performs better with let out = [ ]. Regarding the explanation, doesn't pop() function return the value popped out? How do you get the index from output of pop? Maybe i'm missing something? — D_S_X
– D_S_X, Commented Apr 12, 2022 at 9:31

Stack Exchange Network

Leetcode problem: minimum removal to make valid parentheses

Question

My Solution

1 Answer 1

Performance

Data structures

Suggested solution

You must log in to answer this question.

Hot Network Questions

Leetcode problem: minimum removal to make valid parentheses

Question

My Solution

1 Answer 1

Performance

Data structures

Suggested solution

You must log in to answer this question.

Related

Hot Network Questions