11 · Stacks, queues, intervals and 2D grids Code

LIFO/FIFO with list and deque · valid parentheses · sort-then-merge intervals · Battleship, Minesweeper and other grid scans without aliasing bugs

Why it matters for NPE. Valid parentheses, Battleships in a Board and Minesweeper are the most-named algorithm problems in firsthand NPE coding reports. Grids model racks, boards and bitmaps; intervals model maintenance windows and outages.

Primer: four small shapes that cover most "easy/medium" screens

A stack is a list you only touch at the end: append and pop(). A queue is a deque you push on one side and pop from the other. An interval is a (start, end) pair, and almost every interval question is "sort by start, then sweep". A grid is a list of lists you index as grid[r][c] and walk with a bounds check and a delta list. Battleship, Minesweeper and Valid Parentheses, the three problems named most often in firsthand NPE reports, are all built from these four shapes.

Watch

For the monotonic stack section, Daily Temperatures - Monotonic Stack - Leetcode 739 - Python (NeetCode, 11:52): 1:51 drawing, 9:25 code.

Stack with a list

stack = []
stack.append(x)      # push, O(1)
stack.pop()          # pop the top, O(1); IndexError on empty, so check first
stack[-1]            # peek
if not stack: ...    # empty test

Use a stack when the most recent unfinished thing is the one you need next: unmatched openers, pending operands, the path so far, "the last bar taller than me". If the problem says "nearest to the left" or "most recent", think stack.

Valid Parentheses (LC 20)

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}        # closer -> opener it must match
    stack = []
    for ch in s:
        if ch in pairs:                            # a closer
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                                      # an opener
            stack.append(ch)
    return not stack                               # leftover openers mean invalid

O(n) time, O(n) space in the worst case (all openers). The map is keyed by the closer so one lookup tells you both "is this a closer" and "what must be on top". The three failure cases to say out loud: closer with empty stack, closer that mismatches the top, and openers left at the end. Follow-up: "only one bracket type" turns into a counter that must never go negative and must end at zero.

Min Stack (LC 155)

class MinStack:
    def __init__(self):
        self.st = []                     # (value, min of everything at or below)

    def push(self, v):
        m = min(v, self.st[-1][1]) if self.st else v
        self.st.append((v, m))

    def pop(self):
        return self.st.pop()[0]

    def top(self):
        return self.st[-1][0]

    def get_min(self):
        return self.st[-1][1]

Every operation O(1). Storing the running minimum next to each value means popping never needs a rescan. The alternative is a second stack that only grows when a new minimum arrives; both are fine, say which you chose and why.

Evaluate Reverse Polish Notation (LC 150)

def eval_rpn(tokens):
    st = []
    ops = {'+', '-', '*', '/'}
    for t in tokens:
        if t in ops:
            b, a = st.pop(), st.pop()          # order matters: a op b
            if t == '+':   st.append(a + b)
            elif t == '-': st.append(a - b)
            elif t == '*': st.append(a * b)
            else:          st.append(int(a / b))   # truncate toward zero; a // b floors
        else:
            st.append(int(t))                  # handles '-3' too
    return st[0]

O(n). Two traps: popping in the wrong order for - and /, and using // which floors -7 // 2 to -4 when the problem wants -3.

Minimum Remove to Make Valid Parentheses (LC 1249)

def min_remove(s):
    chars = list(s)                       # strings are immutable; edit a list
    opens = []                            # indices of unmatched '('
    for i, ch in enumerate(chars):
        if ch == '(':
            opens.append(i)
        elif ch == ')':
            if opens:
                opens.pop()
            else:
                chars[i] = ''             # unmatched closer: drop it
    for i in opens:                       # whatever is still open never closed
        chars[i] = ''
    return ''.join(chars)

O(n) time and space. The stack holds indices, not characters, because the output needs to know where to delete. Letters pass straight through.

Monotonic stack: Daily Temperatures (LC 739)

Brute force is O(n²): for each day scan forward for a warmer one. The stack version keeps indices of days still waiting for a warmer day, with temperatures non-increasing from bottom to top. That is the invariant. When a new day arrives, every waiting day colder than it is resolved and popped.

def daily_temperatures(temps):
    res = [0] * len(temps)                # 0 = never gets a warmer day
    stack = []                            # indices; temps[stack] non-increasing bottom to top
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j                # day i is the first warmer day after j
        stack.append(i)
    return res

O(n): each index is pushed once and popped at most once, so the inner while does n pops in total across the whole run. Say that sentence; it is the thing interviewers want to hear about any nested loop over a stack. The same shape solves "next greater element", "stock span" and "largest rectangle in a histogram".

Queue with deque, and the "last N seconds" pattern

from collections import deque
q = deque()
q.append(x)        # enqueue at the right, O(1)
q.popleft()        # dequeue from the left, O(1); list.pop(0) is O(n)
q[0]               # peek oldest
q.appendleft(x), q.pop()   # it is double-ended; a BFS only needs append/popleft

A queue is the right container whenever items leave in the order they arrived: BFS frontiers (topic 13), sliding windows over time, and anything that says "in the last N seconds". The time-window problems are a family. Number of Recent Calls is the free one; Design Hit Counter, Moving Average from Data Stream and Logger Rate Limiter are premium, so the versions below use log and request terms you can practise without an account.

Number of Recent Calls (LC 933)

class RecentCounter:
    def __init__(self):
        self.q = deque()                  # timestamps, ascending because pings arrive in order

    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:      # evict everything older than the window
            self.q.popleft()
        return len(self.q)

Amortised O(1) per ping: each timestamp is appended once and evicted once. Memory is O(pings inside one window), not O(all pings).

Per-client rate limiter (the Hit Counter shape, in request terms)

from collections import defaultdict, deque

class RateLimiter:
    """Allow at most `limit` requests per client in any rolling `window` seconds."""
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.hits = defaultdict(deque)        # client -> timestamps, ascending

    def allow(self, client, now):
        q = self.hits[client]
        while q and q[0] <= now - self.window:
            q.popleft()
        if len(q) >= self.limit:
            return False
        q.append(now)
        return True

Follow-ups: "a million hits a second from one client" means one deque entry per hit is too much; store (second, count) pairs, or a fixed ring of 300 buckets indexed by now % 300 with the timestamp stored beside each count so stale buckets reset. "Many clients that stop talking" means the dict grows; evict idle clients on a timer or with an LRU (topic 17).

Log de-duplication (the Logger Rate Limiter shape)

class LogDeduper:
    """Print a given message at most once every `quiet` seconds."""
    def __init__(self, quiet=10):
        self.quiet = quiet
        self.next_ok = {}                     # message -> earliest timestamp it may print again

    def should_print(self, ts, msg):
        if ts < self.next_ok.get(msg, 0):
            return False
        self.next_ok[msg] = ts + self.quiet
        return True

No queue needed: one dict entry per distinct message, O(1) per call. Say that the dict is bounded by distinct messages, not by log lines.

Moving average of the last k latencies (the Moving Average shape)

class MovingAverage:
    def __init__(self, k):
        self.k, self.q, self.total = k, deque(), 0

    def next(self, v):
        self.q.append(v); self.total += v
        if len(self.q) > self.k:
            self.total -= self.q.popleft()    # keep a running sum, never re-sum the deque
        return self.total / len(self.q)

Intervals

Two intervals a and b overlap when a.start <= b.end and b.start <= a.end. Read it as "neither one ends before the other starts". With half-open intervals [start, end) both comparisons become strict.

Ask which one the interviewer means before writing the comparison. Getting it wrong is a silent off-by-one that costs the correctness score.

Merge Intervals (LC 56): sort by start, then sweep

def merge(intervals):
    out = []
    for start, end in sorted(intervals, key=lambda iv: iv[0]):    # sorted(): leaves the input alone
        if out and start <= out[-1][1]:        # overlaps or touches the last merged interval
            out[-1][1] = max(out[-1][1], end)  # max: [1,10] followed by [2,3] must stay [1,10]
        else:
            out.append([start, end])
    return out

O(n log n) for the sort, O(n) for the sweep, O(n) output. Sorting is what makes a single pass enough: once sorted by start, the only interval the current one can merge with is the last one written. Without the sort you need O(n²) or a different approach. The max handles an interval that is entirely inside the previous one.

Maintenance windows / outage minutes. "Here are the maintenance windows on a device as (start, end) minutes; how many minutes was it unavailable in total?" Merge first, then sum. With half-open windows the duration is end - start. Touching windows ([10,20) and [20,30)) can be merged or not; the total is the same, so merging with <= is safe here. "Longest single outage" is max(e - s for s, e in merged). "Was the device down at minute t" is a scan, or a binary search over the merged list (topic 17).

def outage_minutes(windows):            # windows: list of (start, end) half-open minutes
    return sum(e - s for s, e in merge(windows))

Insert Interval (LC 57): three phases

def insert(intervals, new):               # intervals sorted and non-overlapping
    out, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:          # 1. entirely before new
        out.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:         # 2. overlapping: absorb into new
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    out.append(new)
    out.extend(intervals[i:])                            # 3. entirely after
    return out

O(n) with no sort because the input is already sorted. If the interviewer removes that guarantee, append and call merge.

Non-overlapping Intervals (LC 435): greedy by end

def erase_overlap_intervals(intervals):
    removed, last_end = 0, float('-inf')
    for s, e in sorted(intervals, key=lambda iv: iv[1]):   # earliest end first
        if s >= last_end:            # LeetCode treats touching as non-overlapping here
            last_end = e             # keep it
        else:
            removed += 1             # it collides with a kept interval that ends earlier
    return removed

Keeping the interval that ends earliest leaves the most room for the rest; that is the exchange argument you give if asked "why does greedy work". Meeting Rooms (premium) is the same sort with a check that no adjacent pair overlaps; Meeting Rooms II is a min-heap of end times (topic 7).

2D grids

rows, cols = len(grid), len(grid[0])        # grid[r][c]: row index first, then column
def in_bounds(r, c):
    return 0 <= r < rows and 0 <= c < cols

DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]                 # up, down, left, right
DIRS8 = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if (dr, dc) != (0, 0)]

for dr, dc in DIRS4:
    nr, nc = r + dr, c + dc
    if in_bounds(nr, nc) and grid[nr][nc] == 1:
        ...

grid = [[0] * cols for _ in range(rows)]    # a fresh list per row
bad  = [[0] * cols] * rows                  # one row object repeated: bad[0][0] = 1 changes every row
copy = [row[:] for row in grid]             # copy a grid of ints without aliasing

row_total = sum(grid[r])                              # one row
col_total = sum(grid[r][c] for r in range(rows))      # one column
transposed = [list(col) for col in zip(*grid)]        # columns become rows

Say "rows by cols" and stick to r then c everywhere. Half of grid bugs are a swapped index or a bounds check that uses rows for the column. Write in_bounds once and call it; the interviewer sees structure and you stop retyping the condition.

Count cells that satisfy a condition, and search in a 2D array

def count_cells(grid, pred):
    return sum(1 for row in grid for v in row if pred(v))

def find_all(grid, target):
    return [(r, c) for r, row in enumerate(grid) for c, v in enumerate(row) if v == target]

count_cells(grid, lambda v: v > 90)                # ports above 90% utilisation
hot = find_all(status, 'DOWN')                     # (rack, slot) pairs that are down

O(rows × cols). A "nested loop" over a grid is linear in the number of cells, not quadratic in anything meaningful; say "O(rc)" or "O(cells)". If the rows are sorted the interviewer wants binary search per row (topic 17); if the whole matrix is sorted row- and column-wise, start top-right and step left or down.

Rotate Image (LC 48): transpose, then reverse each row

def rotate(m):                          # square, in place, clockwise
    n = len(m)
    for r in range(n):
        for c in range(r + 1, n):       # upper triangle only, or you swap everything back
            m[r][c], m[c][r] = m[c][r], m[r][c]
    for row in m:
        row.reverse()                   # counter-clockwise: reverse rows first, then transpose

Spiral Matrix (LC 54): four shrinking boundaries

def spiral_order(m):
    out = []
    top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):  out.append(m[top][c])
        top += 1
        for r in range(top, bottom + 1):  out.append(m[r][right])
        right -= 1
        if top <= bottom:                 # without this a single remaining row is read twice
            for c in range(right, left - 1, -1): out.append(m[bottom][c])
            bottom -= 1
        if left <= right:                 # same for a single remaining column
            for r in range(bottom, top - 1, -1): out.append(m[r][left])
            left += 1
    return out

Test on 1×n, n×1 and 3×4 in your head before saying done. Both problems are drills in writing bounds that stay correct as they shrink.

Worked in full: Battleships in a Board (LC 419)

Board of 'X' and '.'. Ships are straight lines, horizontal or vertical, at least one cell apart, so they never touch. Count the ships. Named in three firsthand NPE reports, once as "find n-tile ships in a 2D array" and once with a bomb-placement follow-up.

Approach 1, flood fill: scan every cell; on an unvisited X count a ship and DFS/BFS to mark its cells (topic 13). O(rc) time, O(rc) extra space for visited, or O(1) if you may overwrite the board. It is the general answer and works even if ships could bend.

Approach 2, count heads (the one to give first): each ship has exactly one cell with no X directly above it and no X directly to its left: the top-left end. Count those cells. One pass, no extra memory, no mutation.

def count_battleships(board):
    rows, cols = len(board), len(board[0])
    ships = 0
    for r in range(rows):
        for c in range(cols):
            if board[r][c] != 'X':
                continue
            if r > 0 and board[r - 1][c] == 'X':
                continue                       # continues a vertical ship counted above
            if c > 0 and board[r][c - 1] == 'X':
                continue                       # continues a horizontal ship counted to the left
            ships += 1
    return ships

O(rc) time, O(1) space. The trick depends on the guarantee that ships do not touch orthogonally. Say that dependency out loud, because the follow-ups attack it.

Follow-up 1: return the ship sizes

def ship_sizes(board):
    rows, cols = len(board), len(board[0])
    sizes = []
    for r in range(rows):
        for c in range(cols):
            if board[r][c] != 'X': continue
            if r > 0 and board[r - 1][c] == 'X': continue
            if c > 0 and board[r][c - 1] == 'X': continue
            # (r, c) is a head. Walk right if the ship is horizontal, else down.
            n = 1
            if c + 1 < cols and board[r][c + 1] == 'X':
                while c + n < cols and board[r][c + n] == 'X':
                    n += 1
            else:
                while r + n < rows and board[r + n][c] == 'X':
                    n += 1
            sizes.append(n)
    return sizes

def count_ships_of_size(board, k):          # "find the n-tile ships"
    return sum(1 for n in ship_sizes(board) if n == k)

Still O(rc): each cell is visited by the outer loop once and by at most one walk. A 1-cell ship takes the else branch and the while runs zero times, so it is reported as size 1 correctly. Return Counter(ship_sizes(board)) if asked "how many of each size".

Follow-up 2: ships may touch diagonally, or may touch at all

Diagonal contact does not break the head trick: it only looks up and left, and a diagonal neighbour is neither. Orthogonal contact does break it: two horizontal ships stacked on adjacent rows look like one ship to the up-check. If ships can touch, you need the flood-fill approach with a visited set, and you must ask which adjacency joins cells into one ship: 4-neighbour (ships touching corner to corner stay separate) or 8-neighbour (they merge). Then the count is the number of connected components, exactly Number of Islands in topic 13.

Follow-up 3: drop a bomb and count destroyed ships

Define the blast first ("the cell itself", "the 3×3 around it", "the whole row and column"). A ship is destroyed if any of its cells is in the blast. Label every cell with its ship id in one pass, then count distinct ids inside the blast.

def label_ships(board):
    rows, cols = len(board), len(board[0])
    label = [[0] * cols for _ in range(rows)]      # 0 = water; 1..k = ship id
    ships = 0
    for r in range(rows):
        for c in range(cols):
            if board[r][c] != 'X' or label[r][c]:
                continue                             # water, or already labelled by its head
            ships += 1                               # first unlabelled X in row-major order is a head
            dr, dc = (0, 1) if c + 1 < cols and board[r][c + 1] == 'X' else (1, 0)
            rr, cc = r, c
            while 0 <= rr < rows and 0 <= cc < cols and board[rr][cc] == 'X':
                label[rr][cc] = ships
                rr += dr; cc += dc
    return label, ships

def bomb(label, r, c, radius=1):
    rows, cols = len(label), len(label[0])
    hit = set()
    for rr in range(r - radius, r + radius + 1):
        for cc in range(c - radius, c + radius + 1):
            if 0 <= rr < rows and 0 <= cc < cols and label[rr][cc]:
                hit.add(label[rr][cc])
    return len(hit)                                  # distinct ships touched by the blast

Labelling is O(rc) once; each bomb is O(blast area). For many bombs that is the right split. For one bomb you could skip labelling and flood fill from each hit cell instead. "Ships remaining after the bomb" is ships - bomb(...); "sink only if every cell is hit" needs the sizes from follow-up 1 and a per-ship hit count.

Interview questions

Traps

• list.pop(0) as a dequeue inside a loop: O(n) per call, O(n²) overall. Use deque.popleft().
• Popping an empty stack: stack.pop() raises IndexError. Check if not stack first, or the closer-with-empty-stack case in Valid Parentheses crashes instead of returning False.
• Inclusive-end off-by-one: counting an interval's length as e - s when the ends are inclusive, or merging [1,3] and [4,5] as touching when the data is half-open. Decide the convention first.
• [[0] * c] * r: one row aliased r times. Also copy = grid is not a copy; use [row[:] for row in grid].
• Forgetting to sort intervals before the sweep, or sorting by end when the merge needs start (and by start when the greedy removal needs end).
• Mutating the grid or list while scanning it (deleting from a list inside for, writing marks into a board you were asked not to change). Ask "may I modify the input?" and say what you will do instead if not.
• Swapping r and c, or checking c < rows. Write in_bounds(r, c) once.
• Stack holding values when the output needs positions (Min Remove, Daily Temperatures): push indices.

Do before marking this topic done

1. Blank editor, 10 minutes: Valid Parentheses, then Minimum Remove to Make Valid Parentheses. Dry-run each on "(]", "((", "a)b(c)d" before calling it done.
2. Write RateLimiter(limit, window) from memory and dry-run 5 requests from one client at t = 0, 1, 2, 300, 301 with limit 3 and window 300. Then say what changes for a million requests a second.
3. Given windows = [(10, 20), (15, 30), (30, 40), (50, 55)] half-open minutes, return the merged windows and the total outage minutes (45). Then answer: longest single outage, and "was the device down at minute 40?"
4. Battleships, 15 minutes: count ships, return ship sizes, then bomb with a 3×3 blast. Dry-run on the board in the diagram above with a bomb at (1, 2).
5. Spiral order and rotate on a 3×4 and a 1×5 matrix, by hand, writing the boundary values after each side.

Practice: linked problems

Logged attempts feed the tracker. Open the problem in a new tab, solve in a blank editor, then log honestly.

• LC 933Number of Recent CallsEasy
• LC 56Merge IntervalsMedium
• LC 419Battleships in a BoardMedium
• LC 20Valid ParenthesesEasy
• LC 252Meeting RoomsEasy
• LC 346Moving Average from Data StreamEasy
• LC 359Logger Rate LimiterEasy
• LC 48Rotate ImageMedium
• LC 54Spiral MatrixMedium
• LC 57Insert IntervalMedium
• LC 150Evaluate Reverse Polish NotationMedium
• LC 155Min StackMedium
• LC 362Design Hit CounterMedium
• LC 435Non-overlapping IntervalsMedium
• LC 739Daily TemperaturesMedium
• LC 1249Minimum Remove to Make Valid ParenthesesMedium
• LC 253Meeting Rooms IIMedium

← 10 · Switching: MAC learning, VLANs, STP and LAG · all topics · 12 · Routing fundamentals, OSPF (vs BGP) and IS-IS →