Algorithmic task: dynamic bracket sequences

Task

We have a string of length N consisting of opening and closing brackets ‘(‘ and ‘)’. We perform several operations on that string. Each operation is one of the following:

• Set i-th symbol to ‘(‘
• Set i-th symbol to ‘)’

After each operation we need to output “1” if the string is a correct bracket sequence and output “0” if not.

Example: input string is “((((“, requests are: replace 3rd symbol with “)”, replace 4th symbol with “)”. In that case the output is [0, 1], because after the first operation string becomes “(()(“, and after the second operation the string becomes “(())”.

Time complexity: log(N) per 1 operation

Solution

Correct bracket sequences

First, as a reminder, let’s understand what makes any sequences with brackets to be a correct bracket sequence. First of all, the count of opening brackets should match the count of closing brackets.

However, this is not enough. For example, the string ‘)(‘ is not a correct sequence, even though the count of brackets match, there’s 1 opening bracket and 1 closing bracket.

Therefore, there’s one more condition needed that makes the sequence correct: each prefix should have count of opening brackets to be greater or equal to count of closing brackets.

All in all, we have 2 conditions:

• (1) Overall count of opening brackets = count of closing brackets
• (2) Each prefix of the string has count of opening brackets >= count of closing brackets.

Handling overall bracket balance

How do we quickly check those conditions (1) and (2) after an update operation is performed?

It is relatively easy to see how we can quickly check condition (1). For checking condition (1), we need to store just one variable which is count of opening brackets. We can update the value of that variable on each operation with O(1) time complexity. After that, we can check that count of opening brackets = N / 2, which would mean that count of opening and closing brackets match each other.

That means we can check condition (1) in O(1) time per operation.

Handling prefix bracket balance

The tricky part though is how to check condition (2) very fast? For doing that, let’s represent the bracket string as a prefix balance array, where the i-th element is equal to the bracket balance of the i-th prefix of the string (bracket balance is the difference between count of opening and count of closing brackets).

For example, if we have string “(())()”, then its prefix balance array is [1, 2, 1, 0, 1, 0], which corresponds to balances of prefixes “(“, “((“, “(()”, “(())”, “(())(“, “(())()”.

Condition (2) means all elements of the prefix balance array are non-negative (>= 0). In other words, min(prefix balance array) >= 0.

Now let’s digress a bit and understand how the prefix balance array changes when we update one bracket. If the k-th bracket is being updated, it does not influence prefixes from 0 to k — 1. It only influences prefixes after k-th by offsetting them.

For example, if a string was “(())()()” and we update the 5-th symbol to “)”, the string becomes “(())))()”. The array changes like this:

• Previous prefix balance array: [1, 2, 1, 0, 1, 0, 1, 0]
• New prefix balance array: nnn [1, 2, 1, 0, -1, -2, -1, -2]

First 4 elements stayed the same, whereas all elements from 5-th to the last one decreased by 2, because the 5-th element influenced all prefix balances after 5-th by the same offset -2.

Therefore, when update happens, it applies a constant offset to the tail of the prefix balance array:

• When a bracket is updated from ‘(‘ to ‘)’, the offset is -2
• When a bracket is updated from ‘)’ to ‘(‘, the offset is +2.

How to offset the tail of the prefix bracket array in log(N)?

So to reformulate the condition (2), if we agree to store the prefix balance array somewhere, we need to be able to update its postfix by the constant offset when update operation happens. After that we need to quickly calculate the min of that array and check that it is non-negative. All of that in log(N) time.

But how is this possible? In order to offset the postfix of the array we normally need O(N) time. Also, in order to compute the minimum value and check that it is non-negative we also need O(N) time. How do we do it in log(N) time?

The answer is we are going to use a special data structure, which is called a lazy segment tree.

If you’ve never heard of the Segment Tree data structure, we recommend to first get familiarized with this data structure before reading on (for example, you can find the description of this data structure here).

Lazy segment tree is the same as regular segment tree, but we will also allow storing addons in the nodes of the tree. Each node corresponding to interval [a, b] can store addon X, which means that all elements in the interval [a, b] are incremented by X.

This way, we can easily offset any subsegment of the array in log(N) time using such a segment tree. In order to do that, we just do a regular segment tree traversal of the subsegment and update the addons on the final nodes of the traversal by adding our offset value to them.

This segment tree can then be used to quickly in log(N) time calculate the minimum of the array.

Outline of the final algorithm

We store

• Count of opening brackets
• Lazy segment tree over prefix bracket balances

When we perform update operation on the string, we

• update count of opening brackets. This has O(1) time complexity
• ask the lazy segment tree to offset the tail of the prefix bracket balances. This has O(log(N)) time complexity

After that, we check that

• Opening brackets count = N / 2. This has O(1) time complexity.
• The minimum of prefix bracket balances is >= 0. We get the minimum from the root node of the lazy segment tree. This has O(1) time complexity.

If both checks succeeded, we conclude that this is a correct bracket sequence.

Appendix & Credits

Article is written by Verbetcetera.

Verbetcetera’s mission is to help people with various backgrounds to get a new job at FAANG and other IT companies. Check our Telegram channel about software engineering in English and our main channel in Russian for interview question solutions and a lot of useful tips for interview preparation.