ORIGINAL CODING QUESTION
Minimum action-bracket insertions
Tokens 1 and -1 mean open and close brackets of one kind. Return the fewest bracket insertions needed to make the entire sequence balanced.
Original exercise · easy. Editorial role relevance does not imply a company has asked this question.
Input and output
n, then n integer values. Print one integer as described.
Constraints
1 ≤ n ≤ 200; tokens in {1,-1}.
Example 1
Input
3 1 1 -1
Output
1
One close bracket is missing.
Example 2
Input
2 -1 1
Output
2
Insert an open at the start and a close at the end.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
A close without an unmatched open needs an inserted open.
Hint 2
Track unmatched opens as a balance.
Hint 3
At the end each unmatched open needs one inserted close.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →