Problem statement

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Solution

The idea is to traverse string twice: one from left to rigth and look for the smallest negative balance. This is number of ) brackets we need to add. If we do not have negative balance at any point, we need 0 ) brackets. Similar logic is for right to left traverse.

Complexity

It is O(n) for time and the same for space. Space can be reduced to O(1).

Code

class Solution:
    def minAddToMakeValid(self, s):
        lft = [0]
        for c in s:
            lft += [lft[-1] + (c == "(") - (c == ")")]
            
        rgh = [0]
        for c in s[::-1]:
            rgh += [rgh[-1] + (c == ")") - (c == "(")]
            
        return -min(min(lft), 0) - min(min(rgh), 0)