Brackets matching using BIT

Posted by amit.codename13 on Stack Overflow See other posts from Stack Overflow or by amit.codename13
Published on 2010-02-27T20:47:57Z Indexed on 2010/04/17 8:03 UTC
Read the original article Hit count: 315

Filed under:

edit: I was trying to solve a spoj problem. Here is the link to the problem : http://spoj.pl/problems/BRCKTS

I can think of two possible data structures for solving the problem one using segment tree and the other using a BIT. I have already implemented the solution using a segment tree. I have read about BIT but i can't figure out how to do a particular thing with it(which i have mentioned below)


I am trying to check if brackets are balanced in a given string containing only ('s or )'s. I am using a BIT(Binary indexed tree) for solving the problem. The procedure i am following is as follows:

I am taking an array of size equal to the number of characters in the string. I am assigning -1 for ) and 1 for ( to the corresponding array elements.

Brackets are balanced in the string only if the following two conditions are true.

  • The cumulative sum of the whole array is zero.
  • Minimum cumulative sum is non negative. i.e the minimum of cumulative sums of all the prefixes of the array is non-negative.

Checking condition 1 using a BIT is trivial. I am facing problem in checking condition 2.

© Stack Overflow or respective owner

Related posts about algorithm