Skip to content
Get started

Peak depth times group count of a bracket scan

You validate the bracket string {[()]}[{}] with the standard stack method (push each opener, pop on each matching closer). Let DD be the maximum number of items on the stack at any instant, and let GG be the number of times the stack returns to empty during the scan. Report the product D×GD \times G.

Show hints (2)+
  1. Stack size = current nesting depth; its peak is DD.
  2. Each time the stack returns to empty ends one top-level group; count those for GG, then multiply.

Answer

Reveal answer →

6

Create a free account to see the full worked solution and track your progress.

Interview format: Market Maker, Trading Aptitude Tests

Related questions