Abstract / Summary

Add the fewest parentheses to make a string of parentheses valid by balancing unmatched opening and closing brackets.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (900k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic problem of determining the minimum number of parentheses that must be inserted into a string to make it a valid parentheses sequence. It processes the input in a single pass, maintaining two counters: one for the number of insertions required when an unmatched closing parenthesis appears, and another for the current nesting depth of open parentheses. At the end of the scan, any remaining open parentheses are accounted for, yielding the total number of insertions needed.

Core Logic

The algorithm begins by initializing two integer variables. The first, insert, tracks how many insertions have been forced by encountering a closing parenthesis that does not have a matching opening counterpart. The second, nesting, records the current depth of unmatched opening parentheses.

insert = 0
nesting = 0

The main workhorse is a for loop that iterates over each character in the input string s. For each character, the code distinguishes between an opening '(' and a closing ')'.

When an opening parenthesis is seen, the nesting depth is simply increased:

if c == "(":
    nesting += 1

When a closing parenthesis is encountered, the nesting depth is decreased. If this decrement would drive nesting below zero, it indicates that there is no matching opening parenthesis available. In that situation the algorithm resets nesting to zero (to keep the depth non-negative) and increments insert to reflect the need for an additional opening parenthesis before the current character.

else:
    nesting -= 1
    if nesting < 0:
        nesting = 0
        insert += 1

After the loop finishes, any positive value left in nesting corresponds to unmatched opening parentheses that must be closed. The final result adds these remaining opens to the previously counted insertions:

return insert + nesting

Edge Cases Handled

The implementation gracefully handles several edge conditions without special-case code:

• Empty string - The loop body never executes, leaving both counters at zero, and the function correctly returns 0.
• All opening parentheses - The nesting counter accumulates the total number of opens, while insert stays at 0. The final return adds the entire nesting value, representing the required closing insertions.
• All closing parentheses - Each closing parenthesis triggers the nesting < 0 branch, resetting nesting to 0 and incrementing insert. The final addition of nesting contributes nothing, so the result equals the length of the string, which is the exact number of opening parentheses needed.
• Interleaved mismatched pairs - Whenever a closing parenthesis appears without a preceding open, the algorithm records an insertion and continues processing, ensuring that later opens are counted independently.
• Already valid sequence - The nesting depth never drops below zero, so insert remains 0. At the end, nesting returns to 0, yielding a final result of 0.

These scenarios are covered by the same logical flow, demonstrating the robustness of the single-pass design.

Performance Considerations

The solution operates with a single linear traversal of the input string. By updating two integer counters in place, it avoids any auxiliary data structures such as stacks or lists. This minimal memory footprint ensures that the algorithm runs with constant additional space, regardless of input length.

The decision to reset nesting to zero immediately after it becomes negative eliminates the need for backtracking or storing positions of unmatched parentheses. This early correction keeps the state simple and prevents the counters from growing into negative territory, which could otherwise require extra checks later in the loop.

Overall, the approach delivers an efficient, low-overhead computation that scales directly with the size of the input string.

Imagine you are building a little house made of brackets. Every time you see an opening bracket, it is like starting a new room that needs to be finished. You start with zero extra pieces needed and zero rooms currently open.

As you go through the string, if you find an opening bracket, you add one to your room count because a room is now open. If you find a closing bracket, you are closing one of those rooms, so you take one away from the room count.

Sometimes you might find a closing bracket when there are no rooms open yet. That is a problem because you cannot close a room that does not exist. Whenever this happens, you have to grab an extra opening bracket from your box to fix it, which means adding one to the count of pieces you had to insert.

If you get to the end of the string and some rooms are still open, you must also add those to your total because every room that is open needs a closing bracket to be finished. By doing this, you find out exactly how many total brackets you need to add to make everything match up perfectly.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java				Python		TS
	WalkCCC	C++	Java				Python
	leetcode.ca	C++	Java	JS			Python	Go	TS
	LeetcodeHelp	C++	Java				Python
	Progiez	C++	Java				Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	gouthampradhan		Java
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007						Python
	suxrobGM				C#
	varunu28		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality