Hoi hoi!

I’m @nyaomaru, a frontend engineer who struggles to make game sounds. 😿

Have you used DSA View View already? 👀👀

I Built a Tool to Visualize DSA. Let’s Learn Together! (DSA View View 👀👀)

Features a timeline to step backward mid-loop

nyaomaru

nyaomaru

nyaomaru

Follow

Jul 15

I Built a Tool to Visualize DSA. Let’s Learn Together! (DSA View View 👀👀)

#showdev #typescript #dsa #react

64 reactions

33 comments

7 min read

DSA View View allows you to understand DSA by visualizing how your implementation actually runs.

In the previous article, we looked at:

• Two Sum
• Binary Search
• Bubble Sort

Is Learning DSA Boring? Let's Use DSA View View 👀👀 (Two Sum, Binary Search, and Bubble Sort)

Visualizing execution logic changes mental models

nyaomaru

nyaomaru

nyaomaru

Follow

Aug 19

Is Learning DSA Boring? Let's Use DSA View View 👀👀 (Two Sum, Binary Search, and Bubble Sort)

#dsa #typescript #opensource #learning

50 reactions

9 comments

7 min read

This time, let's try three more classic problems:

• Valid Parentheses
• Reverse Linked List
• Maximum Depth of Binary Tree

These problems introduce three very different ideas:

Stack
Pointer manipulation
Recursion

And all three can become confusing when we only stare at the final code.

So let's view what actually happens. 👀

I'm still learning DSA too, so let's learn together! 😸

🥞 Valid Parentheses

Let's start with Valid Parentheses.

Suppose we have this string:

()[]{}

Every opening bracket has a matching closing bracket.

So this is valid. ✅

But this

([)]

is not valid. ❌

Why?

Because the brackets close in the wrong order.

(
  [
)
  ]

The [ should be closed before the (.

So how can we keep track of that order?

Use a Stack

A stack follows a simple rule:

The last thing we put in is the first thing we take out.

This is called LIFO (Last In / First Out)

Imagine stacking plates.

    🍽️  ← remove first
    🍽️
    🍽️

The last plate we put on top is the first one we can take.

Parentheses work in the same way.

If we see:

(
[
{

then the brackets must close in reverse order

}
]
)

So a stack is a very natural fit.

Here is the implementation:

function isValid(s: string): boolean {
  const stack: string[] = [];

  const pairs: Record<string, string> = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
      continue;
    }

    if (stack.length === 0) return false;

    const target = stack.pop();
    if (target !== pairs[char]) {
      return false;
    }
  }

  return stack.length === 0;
}

The important part is what happens to stack.

Let's use

([])

At first

stack = []

We see

(

It's an opening bracket.

Push it.

stack = ["("]

Next,

[

Push again.

stack = ["(", "["]

Then,

]

This is a closing bracket.

What should it close?

[

And what is currently on top of the stack?

[

Perfect. ✅

So we remove it.

stack = ["("]

Finally,

)

It should close

(

The top of the stack is also

(

Pop!

stack = []

We reached the end with an empty stack.

Valid! 🎉

What About an Invalid Example?

Consider

([)]

We start the same way.

(
↓
stack = ["("]

[
↓
stack = ["(", "["]

Then we find

)

A ) needs

(

But the top of our stack is

[

They don't match.

expected: (
actual:   [

So we immediately know the string is invalid.

Complexity

We walk through the string once.

Time:  O(n)
Space: O(n)

In the worst case, the stack may contain all opening brackets.

👀 Let's View View It

This is where the stack becomes much easier to understand.

When we only read.

stack.push(char);

And

stack.pop();

It can be easy to lose track of what is actually inside the stack.

Especially with something like.

({[]})

What is on top right now?

Which opening bracket are we trying to close?

Instead of remembering everything in our head, we can follow the stack changing step by step.

Conceptually, we can see:

(
↓
[(]

{
↓
[(, {]

[
↓
[(, {, []

]
↓
[(, {]

}
↓
[(]

)
↓
[]

That's the whole idea.

Remember the opening brackets, and always match the most recent one first.

Stack suddenly feels much less mysterious. 🥞😸

🔗 Reverse Linked List

Next, let's reverse a linked list.

Suppose we have

1 → 2 → 3 → 4 → 5

We want

5 → 4 → 3 → 2 → 1

At first glance, this sounds simple.

Just reverse it!

But linked lists are a little different from arrays.

With an array, the values live in positions like

0  1  2  3  4
↓  ↓  ↓  ↓  ↓
1  2  3  4  5

A linked list instead consists of nodes pointing to the next node.

1 → 2 → 3 → 4 → 5 → null

Each arrow matters. To reverse the list, we need to reverse those arrows.

1 ← 2 ← 3 ← 4 ← 5

And this is where things can get confusing.

Because if we change an arrow too early...

we may lose the rest of the list. 😿

Three Important Variables

A common iterative solution uses three variables

prev
current
next

Here is the implementation:

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let current = head;

  while (current !== null) {
    const next = current.next;

    current.next = prev;

    prev = current;
    current = next;
  }

  return prev;
}

It's short.

But there is a lot happening inside these few lines.

Let's follow it carefully.

We start with

1 → 2 → 3 → null

And

prev = null
current = 1

Step 1: Save the Next Node

First

const next = current.next;

So

next = 2

Why do we need this?

Because we're about to change

1 → 2

If we change that arrow without remembering 2, we lose access to the rest of the list.

So first

Save where we need to go next.

Step 2: Reverse the Arrow

Now

current.next = prev;

Originally

1 → 2

But prev is

null

So now

1 → null

The first arrow has been reversed.

Step 3: Move prev

Next

prev = current;

So

prev = 1

Step 4: Move current

Finally

current = next;

We saved 2 earlier.

So now

current = 2

Our state looks like this

null ← 1    2 → 3 → null
       ↑    ↑
      prev current

Then we do exactly the same thing again.

Save:

next = 3

Reverse

2 → 1

Move

prev = 2
current = 3

Now

null ← 1 ← 2    3 → null
           ↑    ↑
          prev  current

One more time

next = null

Reverse

3 → 2

Move

prev = 3
current = null

And now

null ← 1 ← 2 ← 3
               ↑
              prev

The loop stops because

current === null

And prev is the new head.

So

return prev;

Done! 🎉

Complexity

We visit each node once.

Time:  O(n)
Space: O(1)

We don't create another linked list.

We only move a few pointers.

👀 Let's View View It

This is exactly the kind of code that I find difficult to understand by reading alone.

These four lines:

const next = current.next;
current.next = prev;
prev = current;
current = next;

look simple.

But when I first see code like this, my brain starts asking.

Wait.

- Where is current now?
- Did we lose next?
- Which arrow changed?
- What exactly does prev point to?

😿

When we visualize each step, we can actually follow the pointers moving.

prev      current
 ↓           ↓
null         1 → 2 → 3

      ↓↓↓

null ← 1     2 → 3
       ↑     ↑
      prev current

      ↓↓↓

null ← 1 ← 2     3
           ↑     ↑
          prev current

      ↓↓↓

null ← 1 ← 2 ← 3
               ↑
              prev

The algorithm becomes much simpler when we stop thinking of it as four mysterious assignments.

It's really just

Save next
  ↓
Reverse arrow
  ↓
Move prev
  ↓
Move current
  ↓
Repeat

Nice! 🔗😸

🌳 Maximum Depth of Binary Tree

Finally, let's look at a tree.

Consider this binary tree.

        3
       / \
      9   20
         /  \
        15   7

What is its maximum depth?

The longest path from the root to a leaf contains three nodes:

3
↓
20
↓
15

So the answer is.

3

How can we calculate that?

Think About a Smaller Tree

Suppose we are standing at one node.

We don't really need to understand the entire tree at once.

We only need to ask.

How deep is the left subtree?

How deep is the right subtree?

Then choose the larger one.

And add 1 for the current node.

That's exactly what this implementation does.

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

The important idea is

Math.max(leftDepth, rightDepth) + 1;

But recursion can feel strange.

When we call

maxDepth(root.left);

where does the current function go?

And how do all those calls eventually become one number?

Let's follow a small example.

    1
   / \
  2   3
 /
4

We start at

1

But before 1 can know its depth, it asks its left child

maxDepth(2)

Node 2 asks

maxDepth(4)

Node 4 has no children.

So both sides eventually reach

null

And

maxDepth(null);

returns

0

Therefore node 4 can calculate

max(0, 0) + 1
= 1

Now we return to node 2.

Its left side has depth

1

Its right side is null

0

So

max(1, 0) + 1
= 2

Now return to node 1.

Eventually its right subtree also returns

1

So node 1 gets

leftDepth = 2
rightDepth = 1

And calculates

max(2, 1) + 1
= 3

Answer

3

🎉

The Interesting Part: Going Down and Coming Back Up

This is what makes recursion interesting.

First, the function calls go down the tree.

1
↓
2
↓
4
↓
null

But the answers are built while returning back up.

null → 0
4    → 1
2    → 2
1    → 3

So recursion isn't only

Keep calling the same function.

There are really two directions.

Go down
  ↓
Reach the base case
  ↓
Return values back up

The base case here is

if (root === null) {
  return 0;
}

Without it, the recursion would have no place to stop.

Complexity

Every node is visited once.

Time: O(n)

The recursive call stack depends on the height of the tree.

Space: O(h)

where h is the height of the tree.

For a balanced tree, that is roughly

O(log n)

In the worst case, if the tree looks like a linked list

1
 \
  2
   \
    3
     \
      4

the depth can become

O(n)

👀 Let's View View It

Recursion is probably my favorite example for visualization.

Because the final implementation is tiny

const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);

return Math.max(leftDepth, rightDepth) + 1;

But a lot is hidden inside those function calls.

When reading the code, it can feel like

maxDepth()
inside maxDepth()
inside maxDepth()
inside maxDepth()
...

Where are we now? 😿

When we step through the execution, we can follow both parts

Going down

1
↓
2
↓
4
↓
null

and then

Coming back

null → 0
↓
4 → 1
↓
2 → 2
↓
1 → 3

That makes the recursive idea much easier to see.

Ask the smaller subproblems for their answers, then use those answers to build the current answer.

🌳😸

🧠 What Did We Actually Learn?

These three problems look completely different.

But each one introduces a very useful way of thinking.

Valid Parentheses

Use a stack when the most recent item needs to be handled first.

What was the last thing I opened?

Reverse Linked List

When changing references, save what you still need before breaking the old connection.

Where do I need to go next before I change this pointer?

Maximum Depth of Binary Tree

Break a problem into smaller versions of the same problem.

Can I get the answers from my children and build my answer from them?

This is one reason I like learning these problems together.

The implementations are not very large.

But each one introduces a completely different mental model

Stack
Pointer
Recursion

And those mental models are much harder to learn than the syntax itself.

Sometimes the code tells us what happens.

But I also want to see how it happens.

I want to view it. 👀👀

🎯 Conclusion

In this article, we looked at:

• Valid Parentheses with a stack
• Reverse Linked List with pointer manipulation
• Maximum Depth of Binary Tree with recursion

And more importantly, we followed the state while each algorithm was running.

We watched change the stack.

stack.push() / stack.pop()

We watched move through a linked list.

prev
current
next

And we watched recursive calls travel down a tree and return their answers back up.

This is exactly the kind of thing I built DSA View View for.

You can write or load a TypeScript implementation, run it with your own inputs, and move backward and forward through the runtime.

If you are learning DSA too, try viewing one of these problems step by step.

Especially if a solution feels like

I understand every line individually... but somehow I still don't understand the whole thing. 😿

Seeing the runtime may connect those pieces together.

And if there is a DSA problem you want me to cover next, please let me know in the comments!

I still have many algorithms to learn myself. 😸

Let's train our DSA muscles together! 💪

If you like DSA View View, please give it a star ⭐

See you in the next article!