✅NO STACK (SC: O(1))✅||🔥Simple & EASY Soln🔥|| Beats 100% - With Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe intution is very simple. We check if the expression is balanced at any point whil
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe intution is very simple. We check if the expression is balanced at any point while we traverse through the string. To check for extra `)`, we just check while we are moving left to right, it is currently balanced and we get closing parenthesis `)`, then it is surely extra. Then we check for extra `(` by traversing right to left. At any point if it unbalanced and we get another `(`, we can surely say that is extra. We mark both type of extra parenthesis while traversing. And then count them at last in another traversal.\n\nAt any point unbalanced_open keeps the count of unbalanced open parenthesis `(`. If +ve, there is extra `(`. If -ve, there is extra `)`.\n\n---\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThe steps to approach this problem is ->\n\n1. Keep a variable that counts unbalanced or extra `(`. Here `unbalanced_open`.\n2. Traverse the string left to right.\n    - If `s[i]` is a `(` increase `unbalanced_open` by one.\n    - If `s[i]` is a `)`\n        - If the expression is already balanced (`unbalanced_open==0`) we can mark it extra by `s[i]=\'#\'`.\n        - Otherwise decrease `unbalanced_open` by one.\n3. Traverse the string right to left.\n    - If `s[i]` is a `(` and the expression is already unbalanced with opening parenthesis`(` (`unbalanced_open>0`)\n        - we can mark it extra by `s[i]=\'#\'`.\n        - Reduce unbalanced_open by one.\n4. Iterate through the string, and if any char is marked `s[i]==\'#\'`, increase `count` by 1.\n\n---\n# Bonus\nThere is a very similar problem to this. You can checkout [that](https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/solutions/4980922/no-stack-simple-intution-bonus-tips-simple-2-traversal-c-soln-beats-99-with-explanation) with very same logic.\n\n---\n# Complexity\n- Time complexity: ***O(n)***\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: ***O(1)***\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n# Code\n```\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int unbalanced_open=0;\n        for(char &c:s){\n            if(c==\'(\')unbalanced_open++;\n            else if(c==\')\'){\n                if(unbalanced_open==0)c=\'#\';\n                else unbalanced_open--;\n            }\n        }\n        for(int i=s.size()-1; i>=0; i--){\n            if(unbalanced_open>0 && s[i]==\'(\'){\n                s[i]=\'#\';\n                unbalanced_open--;\n            }\n        }\n        int count=0;\n        for(int i=0; i<s.size(); i++)\n            if(s[i]==\'#\')\n                count++;\n        return count;\n    }\n};\n```\n\n---\n\n\n***HOPE MY ANSWER HELPS. BY THE WAY, ONE UPVOTE WOULD MAKE MY DAY.***\n\n![dea9605d2a30ab9ade42d3fa17c208db.jpg](https://assets.leetcode.com/users/images/3a985ed0-6352-4d67-9a9d-169ffec8276d_1712392043.8603547.jpeg)\n
['C++']