Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Stack

Matching and cancelling

Lesson · 9 min read · Stack · Matching and cancelling

Whatever was opened last has to be closed first. Brackets and colliding asteroids are both that rule, and a stack is the structure that follows it.

The last one opened is the first one closed

If you're checking whether a string of brackets is balanced, the thing I'd want you to notice is that a closing bracket can only ever match the most recent opening bracket that's still open. In {[()]} the ) belongs to the ( immediately before it, and once that pair is gone the ] belongs to the [, and so on outwards. So you keep the opening brackets that haven't been closed yet on a stack, and when a closing bracket arrives you compare it with the top.

There are only three ways it can go wrong, and you'll want to check all of them in an interview. The closing bracket can arrive when the stack is empty (nothing to close), it can be the wrong shape for the top (a ] on top of a (), or the string can finish while something is still open.

Balanced brackets

balanced(s)

  1. Start with an empty stack.
  2. For each character: if it opens, push it. If it closes and the stack is empty or the top is a different shape, return false. Otherwise pop.
  3. At the end return true only if the stack is empty.

I've seen a lot of people forget the last check and return true for a string like the one in the trace below. The stack still has a bracket on it at the end, so the answer's false.

Checking "{[()]}(", which closes everything except the last bracket.

  1. Step 1 / 8
    s
    {0i[1(2)3]4}5(6
    stack
    {0
    open1

    '{' opens a bracket. Push it; it waits for its partner.

  2. Step 2 / 8
    s
    {0[1i(2)3]4}5(6
    stack
    {0[1
    open2

    '[' opens a bracket. Push it; it waits for its partner.

  3. Step 3 / 8
    s
    {0[1(2i)3]4}5(6
    stack
    {0[1(2
    open3

    '(' opens a bracket. Push it; it waits for its partner.

  4. Step 4 / 8
    s
    {0[1(2)3i]4}5(6
    stack
    {0[1
    open2

    ')' closes '(', which is on top of the stack. Pop it.

  5. Step 5 / 8
    s
    {0[1(2)3]4i}5(6
    stack
    {0
    open1

    ']' closes '[', which is on top of the stack. Pop it.

  6. Step 6 / 8
    s
    {0[1(2)3]4}5i(6
    stack
    empty0
    open0

    '}' closes '{', which is on top of the stack. Pop it.

  7. Step 7 / 8
    s
    {0[1(2)3]4}5(6i
    stack
    (0
    open1

    '(' opens a bracket. Push it; it waits for its partner.

  8. Step 8 / 8
    stack
    (0
    answerfalse

    The string is finished but 1 bracket is still open. Unbalanced.

Cancelling instead of matching

The asteroid problem looks quite different at first, but it's the same structure. Each asteroid moves right (positive) or left (negative) at the same speed, and two of them only ever meet when a right-mover is followed by a left-mover. Consequently the asteroids moving right are waiting for something to hit them, and the one that arrives first is always going to hit the most recent of them. That's exactly the bracket rule again with a collision where the match used to be.

When a left-mover arrives you compare it with the top of the stack. If the top is smaller it explodes and the left-mover carries on to the next one, if they're the same size they both explode, and if the top is bigger the left-mover's gone. A left-mover that empties the stack (or finds another left-mover on top) survives for good, because nothing to its left can ever catch it.

TimeO(n)
SpaceO(n)

Every asteroid goes onto the stack once and comes off at most once, so the inner loop that keeps popping doesn't make it quadratic. The same goes for the brackets.

Asteroids [10,2,-5,3,-3,-12], where the 12 moving left clears everything.

  1. Step 1 / 10
    asteroids
    10021-5233-34-125
    stack

    I'd go left to right and keep a stack of the asteroids that haven't exploded yet.

  2. Step 2 / 10
    asteroids
    10021-5233-34-125
    stack
    100

    10 is moving right, and nothing behind it can ever catch it up, so it goes on the stack.

  3. Step 3 / 10
    asteroids
    10021-5233-34-125
    stack
    10021

    2 is another right-mover, so it goes on top and it's the first thing the next left-mover will hit.

  4. Step 4 / 10
    asteroids
    10021-5233-34-125
    stack
    100

    -5 hits the 2, and since 2 is the smaller of the two it explodes while -5 keeps on going.

  5. Step 5 / 10
    asteroids
    10021-5233-34-125
    stack
    100

    This time -5 runs into 10, which is bigger, so it's -5 that goes.

  6. Step 6 / 10
    asteroids
    10021-5233-34-125
    stack
    10031

    3 is another right-mover, so it goes on top and it's the first thing the next left-mover will hit.

  7. Step 7 / 10
    asteroids
    10021-5233-34-125
    stack
    100

    -3 and 3 are the same size so they take each other out.

  8. Step 8 / 10
    asteroids
    10021-5233-34-125
    stack

    -12 hits the 10, and since 10 is the smaller of the two it explodes while -12 keeps on going.

  9. Step 9 / 10
    asteroids
    10021-5233-34-125
    stack
    -120

    Nothing's left in front of -12 that moves towards it, so it goes on the stack and won't hit anything again.

  10. Step 10 / 10
    stack
    -120

    What's left, from bottom to top, is [-12].

Problems in this module