Python 3-line mathematically optimal solution with explanation, one-pass O(n) time O(1) space
3-liner:\npython\ndef minAddToMakeValid(self, S):\n    a = b = 0\n    for c in S: a, b = (a, b + 1) if c == \'(\' else (min(a, b - 1), b - 1)\n    return b - a 
3-liner:\n```python\ndef minAddToMakeValid(self, S):\n    a = b = 0\n    for c in S: a, b = (a, b + 1) if c == \'(\' else (min(a, b - 1), b - 1)\n    return b - a * 2\n```\nSome 1-liners with functional programming, just for fun:\n```python\ndef minAddToMakeValid(self, S):\n    return (lambda a,b:b-a*2)(*reduce(lambda t,c:(t[0],t[1]+1)if c==\'(\'else(min(t[0],t[1]-1),t[1]-1),S,(0,0)))\n\ndef minAddToMakeValid(self, S):\n    return (lambda a,b:b-a*2)(*reduce(lambda t,c:(lambda a,b:(a,b+1)if c==\'(\'else(min(a,b-1),b-1))(*t),S,(0,0)))\n```\nReadable version:\n```python\ndef minAddToMakeValid(self, S):\n    height = lowest = 0\n    for c in S:\n        height += 1 if c == \'(\' else -1\n        lowest = min(lowest, height)\n    return -lowest * 2 + height\n```\n---\n\n### Explanation:\n\nA parentheses string can be drawn as a mountain range if you change `(` to `/` and `)` to `\\`. Examples:\n```\n                                  /\\                 /\\/\\\n() = /\\    ()() = /\\/\\    (()) = /  \\    (()())() = /    \\/\\\n```\nTake a moment to convince yourself that a parentheses string is valid if and only if (a) the mountain range ends on the ground and (b) the mountain range never goes underground. Condition (a) says that the number of left and right parentheses must be equal; condition (b) says you can\'t have more right parentheses than left ones for any substring `S[:whatever]`. Here are some examples of invalid strings (I\'ve added `__` on both sides to show where the ground is):\n```\n             /\\/\\\n(()()   = __/    __   <-- invalid because doesn\'t end on the ground\n\n\n             /\\\n(()))(  = __/  \\  __  <-- invalid because goes underground\n                \\/   \n\n                 /\\\n))(((() = __    /  __ <-- invalid because doesn\'t end on the ground and goes underground\n            \\  /\n             \\/\n```\nTo make an invalid mountain range valid again, we need to (a) make sure it ends on the ground and (b) lift it above the ground. To make sure it ends on the ground, we keep track of `height`. To lift the entire mountain range above the ground, we just need to find out how low it goes underground, so we keep track of `lowest`. In the last example shown above, this is what we do:\n```\n                                              /\\ \n                                             /  \\\n       /\\                /\\             /\\  /    \\\n__    /  __  ==>  __    /  \\__  ==>  __/  \\/      \\__\n  \\  /              \\  /     \n   \\/                \\/            \n\n  ))(((()    ==>    ))(((())    ==>    (())(((())))\n                           ^           ^^        ^^\n                           |           ||        ||\n                           |           lift it above the ground\n                           |\n                           make it end on the ground\n```\nThe first (leftmost) picture shows that `height == 1` and `lowest == -2`. To make it end on the ground, we need to add a single `\\` (or `)`) at the end so that the mountain range starts and ends at the same height. Now we just need to lift the whole thing above the ground. Since the `lowest` point was `2` units below the ground, we need to add `//` (or `((`) on the left and `\\\\` (or `))`) on the right to lift the entire mountain range up. In total, we added `1 + 2 * 2` parentheses, which is `height + (-lowest) * 2`.
[]