← DSA Atlas
Dedicated problem page · #921

Minimum Add to Make Parentheses Valid

MediumStack and Expression ProcessingBalance counterGreedy counter (stack-free stack simulation)
Solve on LeetCode ↗
921
MediumStack and Expression ProcessingGreedy counter (stack-free stack simulation)Balance counter

Minimum Add to Make Parentheses Valid

Given a string s of parentheses, return the minimum number of parentheses (either '(' or ')') you must insert so that the string becomes valid. A string is valid when every opening parenthesis has a matching closing parenthesis in the correct order and vice versa.

Open official problem prompt ↗
In plain English

Count the fewest single-character parenthesis insertions that make the whole string balanced.

Picture it like this

Like reconciling a ledger of matched IOUs: each '(' is an open debt and each ')' pays one off; a payment with no debt to cover and any debts left unpaid at close each cost one correction.

Example
Input
s = "())"
Output
1
Why
One '(' inserted (e.g. "(())") matches the extra ')', making the string valid with a single addition.
Constraints
1 <= s.length <= 1000s consists only of the characters '(' and ')'
Pattern lesson

See the pattern, then code

Balance counter
Recognition clue

You only need the count of insertions, not the fixed string, so a running open/close balance replaces an explicit stack of open brackets.

↗
Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Track unmatched open brackets in a balance; a ')' with no open bracket available is an insertion we must count now, and any open brackets left over at the end each need one ')' added.

New words, made simpleKnow these before the algorithm
Balance
The number of '(' seen so far that have not yet been matched by a ')'.
Unmatched close
A ')' encountered while balance is zero, which can never be matched by anything to its left.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Explicit stack

Correct but the stack only ever needs its size, so it is wasteful memory.

Push '(' and pop on ')', count pops with an empty stack, then add the leftover stack size.

Time O(n)Space O(n)
Best choiceTwo counters

Captures all the stack tells us with a single integer — optimal in time and space.

Track unmatched open with balance and unmatched close with a separate counter.

Time O(n)Space O(1)
The rule we keep true

Invariant

At any point balance equals the number of currently unmatched '(' and open_needed equals the number of ')' already found that had no available match.

Why this is correct

Reasoning

Every ')' that cannot be matched forces a '(' insertion, and it is counted immediately and independently. Every '(' left unmatched at the end forces a ')' insertion. These two disjoint deficits are exactly the missing characters, and each insertion fixes precisely one, so their sum is minimal.

The algorithm in three movesSay these aloud before coding
1Keep balance for unmatched '(' and a counter for needed inserts

'(' -> balance=1

2On '(', increment balance

')' -> balance=0

3On ')', if balance > 0 decrement it, otherwise increment the needed-insert counter

')' -> no open, open_needed=1

4Return needed inserts plus leftover balance

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(0
)1
)2
1 · Read'('
2 · AskOpen?
3 · Update statebalance=1, open_needed=0
4 · ResultRecord an open bracket
Key takeaway

The final ')' has no matching '(', so one insertion is required.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Open bracket

    Each '(' increases the count of matches we still owe a ')'.

  2. 2
    Lines 8-12Close bracket

    Match against an open bracket if one exists, otherwise this ')' is unmatched and needs an inserted '('.

  3. 3
    Lines 13Sum the deficits

    Leftover balance is unmatched '(' needing ')', and open_needed is unmatched ')' needing '(' — together the minimum insertions.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Already valid string, e.g. "()" returns 0
  • All opens, e.g. "(((" returns 3
  • All closes, e.g. ")))" returns 3
  • Interleaved, e.g. "()))((" needing several insertions
!

Common beginner mistakes

  • Returning only balance and forgetting the unmatched closes
  • Decrementing balance below zero instead of counting an insertion
  • Confusing this with problem 1249 and trying to build the fixed string
  • Assuming the string can contain characters other than parentheses
Check your understanding

Why can the two deficits (unmatched opens and unmatched closes) simply be added rather than interacting?

More in Stack and Expression Processing

#20Valid ParenthesesMatching stack for bracket pairs#71Simplify PathStack of path components#150Evaluate Reverse Polish NotationOperand stack for postfix evaluation#155Min StackStack augmented with running minimum#224Basic CalculatorStack for parenthesized sign context#227Basic Calculator IIStack with deferred multiply/divide