Forem: tracelit

LeetCode 3550: Multi Source Flood Fill — Step-by-Step Visual Trace

tracelit — Sun, 19 Apr 2026 03:54:54 +0000

Simulate multi-source BFS flood fill on a grid. Multiple colors spread simultaneously — when they collide, the maximum color wins.

Approach

Multi-source BFS. Start with all source cells. At each time step, expand to uncolored neighbors. Use a hash map to track the max color proposed for each cell. Apply winners and repeat.

Time: O(n * m) · Space: O(n * m)

Code

class Solution:
    def colorGrid(self, n: int, m: int, sources: list[list[int]]) -> list[list[int]]:
        ans = [[0] * m for _ in range(n)]

        current_layer = []
        for r, c, color in sources:
            ans[r][c] = color
            current_layer.append((r, c))

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while current_layer:
            next_layer_map = {}

            for r, c in current_layer:
                color = ans[r][c]
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < m and ans[nr][nc] == 0:
                        if (nr, nc) not in next_layer_map or color > next_layer_map[(nr, nc)]:
                            next_layer_map[(nr, nc)] = color

            current_layer = []
            for (nr, nc), max_color in next_layer_map.items():
                ans[nr][nc] = max_color
                current_layer.append((nr, nc))

        return ans

Interactive Trace

Step through this solution on TraceLit — watch next_layer_map build up at each BFS layer and see how color conflicts resolve.

LeetCode 3549: Smallest Stable Index II — Step-by-Step Visual Trace

tracelit — Sun, 19 Apr 2026 03:54:23 +0000

Same problem as Q1 but with larger constraints (up to 10^5). The O(n) approach with suffix min and prefix max is required.

Approach

Precompute suffix minimums. Scan left to right with a running prefix maximum. Return the first index where prefix_max - suffix_min <= k.

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

Code

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)
        if n == 0:
            return -1

        suff_min = [0] * n
        suff_min[-1] = nums[-1]
        for i in range(n - 2, -1, -1):
            suff_min[i] = min(suff_min[i + 1], nums[i])

        current_max = -float("inf")
        for i in range(n):
            current_max = max(current_max, nums[i])
            if current_max - suff_min[i] <= k:
                return i

        return -1

Interactive Trace

Step through this solution on TraceLit — set breakpoints to see exactly when the instability score drops below k.

LeetCode 3547: Smallest Stable Index I — Step-by-Step Visual Trace

tracelit — Sun, 19 Apr 2026 03:54:22 +0000

Given an integer array and threshold k, find the smallest index where prefix max minus suffix min is within k.

Approach

Precompute suffix minimums right to left. Scan left to right tracking prefix max. Check the instability score at each index.

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

Code

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)
        if n == 0:
            return -1

        suff_min = [0] * n
        suff_min[-1] = nums[-1]
        for i in range(n - 2, -1, -1):
            suff_min[i] = min(suff_min[i + 1], nums[i])

        current_max = -float("inf")
        for i in range(n):
            current_max = max(current_max, nums[i])
            if current_max - suff_min[i] <= k:
                return i

        return -1

Interactive Trace

Step through this solution on TraceLit — watch how suff_min builds up and current_max grows as the loop progresses.

LeetCode 3548: Count Good Integers on Path — Digit DP Visualized Step by Step

tracelit — Sun, 19 Apr 2026 03:46:28 +0000

If you've ever stared at a Digit DP solution and thought "I have no idea what's happening inside that recursion" — this one's for you.

We'll break down LeetCode 3548 step by step, trace through the memoization table as it builds up, and actually see how the DP states evolve.

The Problem

Given integers l, r, and a string directions consisting of 'D' (down) and 'R' (right), imagine a 4x4 grid. You start at (0,0) and follow the directions to trace a path. Each cell maps to a digit position in a 16-digit number.

Count how many integers in [l, r] have non-decreasing digits along the path.

Why This Is Hard to Debug

Digit DP is notoriously confusing because:

The state space is abstract: (index, is_tight, last_value)
The recursion tree is deep (16 levels)
The memo table fills up in a non-obvious order
A single wrong condition silently gives the wrong count

Step 1: Map the Path

Before any DP, we need to know which digit positions lie on the path.

path_set = set()
row, col = 0, 0
path_set.add(0)  # starting position
for d in directions:
    if d == 'D':
        row += 1
    else:
        col += 1
    path_set.add(row * 4 + col)

For directions = "DDRR", the path visits cells (0,0) → (1,0) → (2,0) → (2,1) → (2,2), which map to 1D indices {0, 4, 8, 9, 10}.

These are the positions where the non-decreasing constraint applies. All other positions are "free" — any digit works.

Step 2: The Digit DP Framework

We count how many valid 16-digit numbers exist from 0 to some limit:

def count_valid(limit: int) -> int:
    limit_str = str(limit).zfill(16)
    memo = {}

    def dp(idx, is_tight, last_val):
        if idx == 16:
            return 1

        state = (idx, is_tight, last_val)
        if state in memo:
            return memo[state]

        res = 0
        upper_bound = int(limit_str[idx]) if is_tight else 9

        for d in range(upper_bound + 1):
            if idx in path_set:
                if d >= last_val:
                    res += dp(idx + 1, is_tight and (d == upper_bound), d)
            else:
                res += dp(idx + 1, is_tight and (d == upper_bound), last_val)

        memo[state] = res
        return res

    return dp(0, True, 0)

The answer is count_valid(r) - count_valid(l - 1).

Understanding the Three States

State	Meaning
`idx`	Current digit position (0–15)
`is_tight`	Are we still bounded by `limit`? If the prefix so far equals `limit`'s prefix, we can't exceed `limit[idx]`. Once we go lower, we're "free" (`is_tight = False`) and can use digits 0–9.
`last_val`	The last digit placed at a path position. The next path digit must be `>= last_val`.

The Key Branching Logic

if idx in path_set:
    # This position is on the path — enforce non-decreasing
    if d >= last_val:
        res += dp(idx + 1, ..., d)  # update last_val
else:
    # Not on the path — no constraint, last_val unchanged
    res += dp(idx + 1, ..., last_val)

This is where most bugs happen. Common mistakes:

Updating last_val for non-path positions
Using > instead of >= (strictly increasing vs non-decreasing)
Forgetting to check is_tight when computing upper_bound

Step 3: Tracing Through the Memo Table

Let's trace count_valid(20) with path_set = {0, 4, 8, 9, 10}.

The recursion starts at dp(0, True, 0). Position 0 is on the path, limit_str = "0000000000000020", so upper_bound = 0.

Only d = 0 is valid (it's >= last_val = 0). We recurse to dp(1, True, 0).

Position 1 is not on the path. upper_bound = 0 (still tight). We place d = 0 freely and move on.

This continues until we hit position 4 (on the path again). Now the interesting branching starts.

The memo table builds bottom-up as recursion returns:

(15, True, 0) → 1    # base case: only one way to "finish"
(14, True, 0) → 1    # one digit left, tight, only d=0 works
...
(8, True, 0)  → 10   # position 8 is on path, branching begins
(4, True, 0)  → 10   # accumulated from subtree
(0, True, 0)  → 10   # final answer for count_valid(20)

The is_tight = False states are where the count explodes — once we go below the limit, we have full freedom for remaining digits.

Step 4: Putting It Together

return count_valid(r) - count_valid(l - 1)

For l = 10, r = 20:

count_valid(20) = 10
count_valid(9) = ?
Answer: the difference

Tips for Digit DP Problems

Always pad with leading zeros — str(limit).zfill(width) prevents off-by-one issues with shorter numbers.
The is_tight flag is the hardest part — draw out what happens when you're at the boundary vs. free. Once is_tight becomes False, it stays False for all deeper calls.
Trace the memo table — don't just read the code. Watch how states fill up. The order matters for understanding what each cached value represents.
Test with small inputs first — l=1, r=9 should be trivially verifiable by hand before you try larger ranges.

Interactive Trace

Want to step through every line of this solution and watch the memo dict build up in real time?

Open the interactive trace on TraceLit

You can set breakpoints on specific lines and jump between them to see exactly when each memo state gets cached and reused.

Python Tutor Alternative for LeetCode: Why TraceLit Exists

tracelit — Thu, 09 Apr 2026 07:55:04 +0000

If you've used Python Tutor to understand code execution, you already know how powerful visual tracing can be. But if you've tried using it for LeetCode problems — especially linked lists and trees — you've probably hit its limits.

What Python Tutor Does Well

Python Tutor is an incredible tool for learning programming fundamentals. It shows you:

How variables are stored in memory
How the call stack grows with function calls
How references and pointers work at the memory level

For intro CS courses, it's unmatched. There's a reason it's used by millions of students worldwide.

Where Python Tutor Falls Short for LeetCode

When you're grinding LeetCode for a technical interview, you need something different:

Feature	Python Tutor	TraceLit
Linked list rendering	Memory box diagram	Interactive graph with pointer labels
Binary tree rendering	Memory box diagram	Tree layout with L/R edges
Pointer tracking	Manual reference following	Auto-highlights head, curr, prev, slow, fast
LeetCode format	Doesn't understand `ListNode`/`TreeNode`	Built-in support, paste input like `[1,2,3,4,5]`
AI debugging	None	One-click bug detection with fix suggestion
Step controls	Forward only	Forward, backward, slider, auto-play

The Core Difference

Python Tutor shows you how memory works. TraceLit shows you how your algorithm works.

When you're debugging "why does my reverse linked list return the wrong answer", you don't need to see heap addresses. You need to see:

Where curr is pointing right now
What prev looks like after the pointer swap
The exact step where the list breaks

That's what TraceLit does.

Try It Yourself

Here's LeetCode 206 (Reverse Linked List) running in TraceLit. Watch how the pointers move at each step:

Open interactive visualization

Open TraceLit — free, no sign-up required.

When to Use Which

Learning Python basics → Python Tutor
Understanding memory and references → Python Tutor
Grinding LeetCode for interviews → TraceLit
Debugging linked list / tree problems → TraceLit
Building intuition for pointer manipulation → TraceLit

They're complementary tools. Python Tutor taught you how code executes. TraceLit helps you see your algorithm think.

TraceLit is free during beta. 130+ NeetCode 150 problems with step-by-step visual traces.

LeetCode 46: Permutations — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:06:06 +0000

Medium — Backtracking | Array | Recursion

The Problem

Given an array of distinct integers, return all possible permutations of the array elements in any order.

Approach

Uses backtracking with in-place swapping to generate permutations. At each position, we try placing each remaining element, recursively generate permutations for the rest, then backtrack by swapping elements back to their original positions.

Time: O(n! × n) · Space: O(n)

Code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start == len(nums) - 1:
                permutations.append(nums[:])  # Append a copy of the current permutation

            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]  # Swap elements
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # Backtrack

        permutations = []
        backtrack(0)
        return permutations

Watch It Run

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

LeetCode 235: Lowest Common Ancestor Of A Binary Search Tree — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:06:04 +0000

Medium — Binary Search Tree | Tree | Recursion

The Problem

Find the lowest common ancestor (LCA) of two given nodes in a binary search tree, where the LCA is the deepest node that has both nodes as descendants.

Approach

Leverage the BST property to recursively navigate the tree. If both nodes are smaller than current node, go left; if both are larger, go right; otherwise the current node is the LCA.

Time: O(h) · Space: O(h)

Code

class Solution:
    def lowestCommonAncestor(
        self, root: TreeNode, p: TreeNode, q: TreeNode
    ) -> TreeNode:
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

Watch It Run

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

LeetCode 309: Best Time To Buy And Sell Stock With Cooldown — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:05:30 +0000

Medium — Dynamic Programming | Array | State Machine

The Problem

Find the maximum profit from buying and selling stocks with a cooldown period of one day after each sale. You can complete multiple transactions but must wait one day after selling before buying again.

Approach

Use dynamic programming with three states: buy (maximum profit after buying), sell (maximum profit after selling), and cooldown (maximum profit during cooldown). Track the optimal profit for each state at every day by considering all possible transitions.

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

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        # Initialize variables to represent the maximum profit after each action.
        buy = -prices[
            0
        ]  # Maximum profit after buying on day 0 (negative because we spend money).
        sell = 0  # Maximum profit after selling on day 0 (no profit yet).
        cooldown = 0  # Maximum profit after cooldown on day 0 (no profit yet).

        for i in range(1, len(prices)):
            # To maximize profit on day 'i', we can either:

            # 1. Buy on day 'i'. We subtract the price of the stock from the maximum profit after cooldown on day 'i-2'.
            new_buy = max(buy, cooldown - prices[i])

            # 2. Sell on day 'i'. We add the price of the stock to the maximum profit after buying on day 'i-1'.
            new_sell = buy + prices[i]

            # 3. Do nothing (cooldown) on day 'i'. We take the maximum of the maximum profit after cooldown on day 'i-1' and after selling on day 'i-1'.
            new_cooldown = max(cooldown, sell)

            # Update the variables for the next iteration.
            buy, sell, cooldown = new_buy, new_sell, new_cooldown

        # The maximum profit will be the maximum of the profit after selling on the last day and the profit after cooldown on the last day.
        return max(sell, cooldown)

Watch It Run

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

LeetCode 20: Valid Parentheses — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:05:12 +0000

Easy — Stack | String | Hash Table

The Problem

Determine if a string containing only parentheses characters is valid, where every opening bracket has a corresponding closing bracket in the correct order.

Approach

Use a stack data structure to track opening brackets. Push opening brackets onto the stack, and when encountering closing brackets, check if they match the most recent opening bracket. The string is valid if the stack is empty at the end.

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

Code

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        parentheses_map = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in parentheses_map.values():
                stack.append(char)
            elif char in parentheses_map:
                if not stack or stack[-1] != parentheses_map[char]:
                    return False
                stack.pop()
            else:
                return False

        return not stack

Watch It Run

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

LeetCode 239: Sliding Window Maximum — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:04:39 +0000

Hard — Sliding Window | Deque | Queue | Array

The Problem

Find the maximum element in each sliding window of size k as it moves from left to right through an array. Return an array containing the maximum value for each window position.

Approach

Use a deque to maintain indices of array elements in decreasing order of their values. For each element, remove smaller elements from the back, add current index, remove indices outside the current window from front, and collect maximums when window is full.

Time: O(n) · Space: O(k)

Code

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k <= 0:
            return []

        result = []
        window = deque()

        for i, num in enumerate(nums):
            while window and nums[window[-1]] < num:
                window.pop()

            window.append(i)

            if i - window[0] >= k:
                window.popleft()

            if i >= k - 1:
                result.append(nums[window[0]])

        return result

Watch It Run

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

LeetCode 206: Reverse Linked List — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:04:36 +0000

The Problem

Given the head of a singly linked list, reverse the list and return the reversed list.

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

This is one of the most classic interview questions — simple enough to explain in 30 seconds, but tricky enough that getting the pointer manipulation right under pressure trips people up.

The Approach: Three Pointers

The iterative approach uses three pointers: prev, current, and next_node.

Start with prev = None and current = head
At each step:
- Save the next node: next_node = current.next
- Reverse the pointer: current.next = prev
- Move forward: prev = current, current = next_node
When current is None, prev points to the new head

Time: O(n) — single pass through the list
Space: O(1) — only three pointer variables

The Code

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        return prev

Watch It Run

The best way to understand pointer manipulation is to see it happen. TraceLit traces your code line by line and shows you exactly how prev, current, and next_node move through the list at each step.

Open interactive visualization

Try it yourself: Open TraceLit and step through the trace. You can also paste your own solution and test it with different inputs.

Key Insight

The trick is the order of operations. If you reverse current.next = prev before saving current.next, you lose the reference to the rest of the list. That's why next_node = current.next must come first.

This pattern — save, reverse, advance — shows up in many linked list problems:

LeetCode 92: Reverse Linked List II
LeetCode 25: Reverse Nodes in k-Group
LeetCode 234: Palindrome Linked List

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

LeetCode 191: Number Of 1 Bits — Step-by-Step Visual Trace

tracelit — Thu, 09 Apr 2026 07:04:03 +0000

Easy — Bit Manipulation | Math

The Problem

Given a positive integer n, count and return the number of set bits (1s) in its binary representation.

Approach

Use bit manipulation to check each bit position by performing bitwise AND with 1 to detect if the least significant bit is set, then right shift to examine the next bit. Continue until all bits are processed.

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

Code

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n = n >> 1
        return count

Watch It Run

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.