Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Pick based on two properties of the graph and one property of the query: if every edge has the same weight, breadth-first search (BFS) alone gives shortest paths in linear time; if weights differ but are never negative, Dijkstra's algorithm is the standard single-source choice; if a negative weight is possible (but no negative cycle), Dijkstra can give a wrong answer and Bellman-Ford is required instead; and if you need distances between every pair rather than from one source, Floyd-Warshall (a dynamic-programming algorithm that considers every node in turn as a possible shortcut between every pair) is the natural fit for all-pairs, or equivalently running Dijkstra from every node. A* only changes single-source, non-negative-weight search: it adds a heuristic estimate of remaining distance to prioritize expansion toward a specific goal, and it only helps, versus plain Dijkstra, when that heuristic is admissible (it never overestimates the true remaining cost), since an inadmissible heuristic can cause A* to return a path that is not actually shortest.

Structured elaboration

Decision order:

1. Are all edge weights equal (or is the graph unweighted)? Use BFS: $O(V + E)$, no priority queue needed at all.
2. Do you need distances between every pair of nodes, not just from one source? Use Floyd-Warshall, $O(V^3)$, or repeat Dijkstra from every source if the graph is sparse and there are no negative weights.
3. Otherwise, single-source with weights: are negative edge weights possible? If yes, use Bellman-Ford, $O(V \cdot E)$, which also detects a negative cycle if one exists (a cycle whose total weight is negative, which makes "shortest path" undefined, since you could loop it forever to keep decreasing the cost). If no, use Dijkstra, $O((V+E) \log V)$ with a binary heap.
4. If you additionally have a single, known goal node (not "distances to everywhere"), and a decent estimate of remaining distance, layer A* on top of Dijkstra's non-negative-weight assumption to reduce how much of the graph gets explored.

Why Dijkstra breaks under negative weights: once Dijkstra pops a node off its priority queue, it treats that node's distance as final and never revisits it, on the assumption that nothing already queued could possibly offer a shorter path, since all remaining edges only add non-negative weight. A negative edge violates that assumption directly: a longer-looking path discovered later can still turn out shorter once a negative edge is added to it.

What A's heuristic must guarantee*: admissibility, never overestimating the true remaining cost to the goal. Given an admissible heuristic, A* is guaranteed to still find a shortest path, exactly like Dijkstra, but it explores fewer nodes when the heuristic is informative, because it prioritizes nodes that look closer to the goal rather than merely closer to the start. (A stronger property, consistency, additionally guarantees a node is never re-expanded after being finalized, which is what lets A* implementations skip the "revisit and relax an already-closed node" bookkeeping that a merely admissible-but-inconsistent heuristic would otherwise require.) A straight-line (Euclidean) distance heuristic on a road network or grid is a classic admissible choice, since no real route can be shorter than the straight line.

Worked example

Bellman-Ford correctness under a negative edge, where Dijkstra gets it wrong:

import math

def dijkstra(adj, src):
    import heapq
    dist = {src: 0}
    finalized = set()
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in finalized:
            continue
        finalized.add(u)
        for v, w in adj.get(u, []):
            if v in finalized:
                continue
            nd = d + w
            if nd < dist.get(v, math.inf):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def bellman_ford(edges, nodes, src):
    dist = {n: math.inf for n in nodes}
    dist[src] = 0
    for _ in range(len(nodes) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle detected")
    return dist

# True shortest A->B is via C: 1 -> 4 + (-10) = -6, but Dijkstra finalizes
# B at distance 1 (direct edge) before C is even processed.
adj = {"A": [("B", 1), ("C", 4)], "C": [("B", -10)]}
edges = [("A", "B", 1), ("A", "C", 4), ("C", "B", -10)]
nodes = ["A", "B", "C"]

print("dijkstra:", dijkstra(adj, "A"))
print("bellman_ford:", bellman_ford(edges, nodes, "A"))

Running this prints:

dijkstra: {'A': 0, 'B': 1, 'C': 4}
bellman_ford: {'A': 0, 'B': -6, 'C': 4}

Dijkstra reports B at distance 1 (wrong: it finalized B via the direct edge before discovering the cheaper route through C), while Bellman-Ford correctly finds -6 via A to C to B.

A exploring fewer nodes than Dijkstra given an admissible heuristic*, on an open 20x20 grid from (0,0) to (5,5), using Manhattan distance as the heuristic:

import heapq

def neighbors(pos, size):
    x, y = pos
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < size and 0 <= ny < size:
            yield (nx, ny)

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def search(start, goal, size, use_heuristic):
    h = (lambda n: manhattan(n, goal)) if use_heuristic else (lambda n: 0)
    g = {start: 0}
    pq = [(h(start), start)]
    visited = set()
    expansions = 0
    while pq:
        _, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        expansions += 1
        if node == goal:
            break
        for nb in neighbors(node, size):
            ng = g[node] + 1
            if ng < g.get(nb, float("inf")):
                g[nb] = ng
                heapq.heappush(pq, (ng + h(nb), nb))
    return g[goal], expansions

size = 20
start, goal = (0, 0), (5, 5)
dist_astar, exp_astar = search(start, goal, size, use_heuristic=True)
dist_dij, exp_dij = search(start, goal, size, use_heuristic=False)
print("A* distance:", dist_astar, "nodes expanded:", exp_astar)
print("Dijkstra distance:", dist_dij, "nodes expanded:", exp_dij)

Running this prints:

A* distance: 10 nodes expanded: 36
Dijkstra distance: 10 nodes expanded: 61

Both find the same correct shortest distance (10), but A* reaches it having expanded 36 nodes against Dijkstra's 61, because the heuristic steered expansion toward the goal instead of outward in every direction equally.

Trade-offs & pitfalls

A common mistake is treating A* as "a different algorithm" from Dijkstra rather than as Dijkstra with a heuristic added to the priority; with a heuristic of zero everywhere (as in the comparison above), A* degenerates to exactly Dijkstra, which is a good way to check an A* implementation for bugs. A second pitfall is picking a heuristic that overestimates in some region "because it prunes more nodes": an inadmissible heuristic can make A* return a path that is not actually shortest, so any heuristic must be checked against the admissibility property, not just judged by how much it speeds things up. Practically, Dijkstra's own implementation constant matters too: with a binary heap, each edge relaxation that improves a distance costs $O(\log V)$ to sift, which under many decrease-key-style relaxations is the dominant cost; the common fix is not switching to a Fibonacci or pairing heap (both have amortized $O(1)$ or near-$O(1)$ decrease-key but carry higher constant factors and more complex implementations) but instead allowing duplicate, stale entries in a plain binary heap and lazily discarding them on pop, which is what the Dijkstra implementation above already does and is the standard practical choice.

Direct answer

Keep a resizable array of the stored values plus a hash map from value to that value's index in the array. Insert appends to the array in O(1); getRandom picks a uniformly random array index in O(1); the trick is delete, which must not leave a gap: swap the removed value with the array's last element, update that moved element's index in the hash map, then pop the last slot off in O(1).

Structured elaboration

• values: an array of the currently stored values, with no gaps.
• index_of: hash map from value to its current position in values.

insert(val): if val is already in index_of, return false. Otherwise append it to values and record its index.

remove(val): if val is absent, return false. Otherwise look up its index, overwrite that slot with the array's last element (updating that moved element's entry in index_of to the vacated index), then pop the array's last slot and delete val from index_of. Because the moved element simply changes which index it lives at, and every array slot is always occupied by exactly one live value, no gap is ever created and no shifting of the remaining elements is needed.

getRandom(): choose a uniformly random integer index in [0, len(values)) and return values[that index]. Since each stored value occupies exactly one slot and slots are chosen uniformly, every value has equal probability of being returned.

The reason a plain hash set cannot support getRandom in O(1) is that hash tables give you no way to address "the k-th element" directly: you would need to walk buckets, which is not O(1) and not uniform once buckets have different chain lengths. The array gives you that direct O(1) addressing that a hash table structurally lacks.

Worked example

import random


class RandomizedSet:
    def __init__(self):
        self.index_of: dict[int, int] = {}
        self.values: list[int] = []

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        idx = self.index_of[val]
        last_val = self.values[-1]
        self.values[idx] = last_val
        self.index_of[last_val] = idx
        self.values.pop()
        del self.index_of[val]
        return True

    def get_random(self) -> int:
        return random.choice(self.values)


random.seed(42)
rs = RandomizedSet()
print(rs.insert(1))
print(rs.insert(2))
print(rs.insert(3))
print(rs.remove(2))     # swaps 3 into index 1
print(rs.values)
print(rs.get_random())
print(rs.get_random())

Running this (CPython's random module, seeded) prints:

True
True
True
True
[1, 3]
1
1

Key points

• The swap-with-last trick is what keeps delete O(1): it avoids shifting every element after the removed one.
• Uniformity comes from the array having no gaps: random.choice over indices is exactly a uniform choice over the stored values.

Complexity

for insert, remove, and getRandom; $O(n)$ space for the array and hash map together.

Edge cases

• Removing the last element in the array: the "swap with last" step is swapping an element with itself, which is harmless.
• getRandom on an empty structure has no valid answer; guard it explicitly (raise, or document as undefined behavior) rather than letting random.choice throw an unhandled exception on an empty list.

Trade-offs & pitfalls

The most common mistake is deleting by shifting all elements after the removed index, which is correct but O(n), defeating the point. A second common mistake is deleting by using values.remove(val) in Python, which internally does that same O(n) scan-and-shift. The design absorbs a lighter-weight sibling problem well: an insertion-order-preserving set (for example, deduplicating items in a shopping cart while keeping display order) uses the same "array plus hash map of positions" composition, but it cannot use the swap-with-last trick, because swapping would destroy the insertion order it is trying to preserve. That variant instead needs either a tombstone marker left in place (with periodic compaction) or a doubly linked list plus hash map (the same structure used for an LRU cache), trading away the O(1) swap-delete for order preservation.

Direct answer

Reverse the whole array, then reverse the first k elements and the remaining n-k elements separately; three linear passes compose into the fully rotated result with no auxiliary array. The same reversal trick generalizes directly: reversing a string in place is the identical two-pointer, swap-from-both-ends routine, and rotating a square matrix 90 degrees in place is a transpose followed by reversing each row, both built on the same in-place-swap primitive as the array rotation.

Structured elaboration

Why three reversals produce a rotation. Reversing the entire array puts every element in fully reversed order. Reversing the first k elements of that reversed array un-reverses exactly the block that should now sit at the front, restoring its original relative order; reversing the remaining n-k elements does the same for the remainder. Normalizing with k %= n handles k values larger than the array's length or equal to zero.

Generalizing to a string. The same in-place two-pointer swap from both ends is exactly what reverses a string, provided the string is held in a mutable container (a list of characters, for example, since Python's own string type is immutable and cannot be reversed truly in place without first converting it).

Generalizing to a square matrix. Transposing swaps matrix[i][j] with matrix[j][i] for every i < j, turning rows into columns. Reversing each row afterward flips left to right. Combined, what was the first column read top to bottom becomes the first row read left to right, which is exactly a 90-degree clockwise turn.

Related in-place-preprocessing techniques (with an honest space caveat). Prefix-sum preprocessing builds an auxiliary array once, in $O(n)$ time, so that any later range-sum query answers in $O(1)$; this trades $O(n)$ extra space for fast queries, so it is not itself an O(1)-extra-space technique, even though it shares this family's "one linear pass, reuse the result" character. Product-except-self, by contrast, genuinely can be done with O(1) extra space beyond the required output array: a first pass fills the output with the running product of everything to each index's left, and a second pass multiplies in the running product of everything to that index's right, needing no separate auxiliary array at all.

Worked example

def rotate_array(nums: list[int], k: int) -> None:
    n = len(nums)
    if n <= 1:
        return
    k %= n
    if k == 0:
        return

    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)


def reverse_string_inplace(chars: list[str]) -> None:
    i, j = 0, len(chars) - 1
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1
        j -= 1


def rotate_matrix_90_cw_inplace(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7]
    rotate_array(arr, 3)
    print(arr)

    chars = list("hello")
    reverse_string_inplace(chars)
    print("".join(chars))

    m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    rotate_matrix_90_cw_inplace(m)
    print(m)

Running this prints [5, 6, 7, 1, 2, 3, 4], then olleh, then [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

Complexity

rotate_array: time $O(n)$ for the three reversal passes, since they compose additively into a single linear scan rather than multiplying; space $O(1)$ extra, using only the two index pointers inside each reversal call.
reverse_string_inplace: time $O(n)$, one pass with two pointers closing in from both ends; space $O(1)$ extra beyond the mutable character list itself.
rotate_matrix_90_cw_inplace: time $O(n^2)$ for an n-by-n matrix, since the transpose visits each of the $n^2$ cells once; space $O(1)$ extra, since both the transpose and the row reversals swap in place with no auxiliary matrix.

Edge cases

• k = 0, or k a multiple of the array's length once normalized via k %= n: rotate_array detects this and returns immediately without performing any reversals, since the array is already in its correct rotated position.
• Empty or single-element array or string: both rotate_array (via its n <= 1 guard) and reverse_string_inplace (via while i < j never firing) return immediately with nothing to do.
• A non-square matrix passed to rotate_matrix_90_cw_inplace: this implementation assumes a square matrix, and a non-square transpose changes the matrix's dimensions, so it cannot be rotated true in place this way.

Trade-offs & pitfalls

Forgetting k %= n for a k larger than the array's length either wastes work or, in a careless implementation, indexes out of range. The transpose-then-reverse-rows trick only works for a square matrix: transposing a non-square matrix changes its dimensions, so a genuinely non-square rotation needs a separate output buffer rather than a true in-place transform. Python's string immutability means a real in-place string reversal needs a mutable container (a list of characters, or a bytearray) first; there is no way to mutate a str object's characters directly.

Direct answer

Before writing any code, look for two structural signals: does the problem have overlapping subproblems and optimal substructure (an optimal solution is built from optimal solutions to smaller versions of itself)? If yes, it is a dynamic programming (DP) problem, not a greedy one. Within DP, whether you reach for memoization (caching recursive-call results, computed top-down) or tabulation (filling a table iteratively, bottom-up) is a secondary implementation choice, not a correctness question: both compute the same recurrence.

Structured elaboration

Signal 1: does a locally optimal choice guarantee a globally optimal one? Greedy algorithms make one irrevocable choice at each step and never reconsider it. That is only correct when the problem has the "greedy-choice property": committing to the best-looking option right now cannot make the final answer worse. You test this by trying to construct a counterexample where the locally-best choice forecloses a better global outcome (an exchange argument): if you can build one, greedy is wrong and you need DP; if every attempt to build a counterexample fails and you can sketch why (an exchange argument that any optimal solution can be rearranged to match the greedy choice without loss), greedy is likely correct.

Signal 2: overlapping subproblems and optimal substructure. If solving the problem for a larger input naturally requires solving the same smaller subproblem many times (for example, "the best way to reach state k" depends on "the best way to reach state k-1", but state k-1 also gets asked about from other paths), you have overlapping subproblems. If, in addition, an optimal solution to the whole problem is composed of optimal solutions to its subproblems (no locally-suboptimal subproblem answer can still lead to a globally optimal whole), you have optimal substructure. Both together mean DP applies: cache each subproblem's answer once, reuse it everywhere it recurs.

Signal 3: what does the recurrence look like? Write the recurrence in terms of "the answer for state X depends on the answer for smaller states Y, Z, ...", before touching code. If you can write this recurrence but it does not have an ordering where "smaller" always resolves before "larger" (a genuine dependency cycle), you likely need a different technique entirely (graph shortest-path with cycles, for instance).

Once you know it's DP: memoization vs tabulation. These are the same recurrence expressed two ways, not two different algorithms:

Worked example

Take "minimum coins to make amount 6 from denominations {1, 3, 4}" (the coin change problem). The recurrence is: minCoins(a) = 1 + min(minCoins(a - c) for c in coins if c <= a), with minCoins(0) = 0. Overlapping subproblems are visible immediately: computing minCoins(6) needs minCoins(5), minCoins(3), minCoins(2); computing minCoins(5) also needs minCoins(2). minCoins(2) gets requested from two different callers, so caching it once and reusing it is exactly what turns an exponential naive recursion into a linear-in-target one. That overlap is the tell that this is DP, not greedy: a greedy "always take the largest coin" would take 4 then 1 then 1 (3 coins), while the true optimum is 3 + 3 (2 coins), because taking the largest coin first forecloses the better pairing, a real exchange-argument counterexample, confirming greedy is unsafe here and DP (with either memoization or tabulation) is required.

Trade-offs & pitfalls

Key points

• The most common mistake is reaching for greedy because a locally-best choice feels right; the discipline is to actively try to break it with a counterexample before trusting it, not to trust it by default.
• A DP recurrence existing does not by itself tell you whether to memoize or tabulate; that choice depends on whether the reachable state space is sparse (favors memoization) or dense with a clean iteration order (favors tabulation), and on language-specific recursion-depth limits.
• Some problems only look like DP: if there is no genuine overlap (each subproblem is only ever needed once), plain recursion or divide-and-conquer is simpler and DP's caching buys you nothing.

Complexity

• These are meta-level signals, not a specific algorithm, so there is no single complexity here; once you commit to DP, complexity is (number of distinct states) times (work per state), whether computed top-down with a cache or bottom-up with a table.

Edge cases

• A problem with optimal substructure but no overlapping subproblems (each subproblem solved once) does not need DP's memoization; plain recursion or divide-and-conquer suffices and adding a cache only adds overhead.
• A problem where you cannot write a clean dependency order for tabulation (irregular, data-dependent state transitions) may force memoization even in a dense-looking state space, since an explicit iteration order is hard to construct correctly.

Direct answer

Kadane's algorithm makes one pass, keeping a running sum that resets whenever it would drop to zero or below (since a non-positive running sum can never help extend a future subarray), and tracks the best sum seen along the way. It still works when every number is negative because the running sum is initialized directly from the first element rather than from zero, so the algorithm falls back to reporting the single least-negative element rather than incorrectly returning an empty-subarray sum of 0. Adapting it to the maximum product instead of sum requires tracking a running minimum alongside the running maximum, since multiplying two negative numbers can turn the current running minimum into the new running maximum.

Structured elaboration

Why a single pass suffices (optimal substructure)

Let $best(i)$ be the maximum sum of a subarray ending exactly at index i. Either that subarray is just the single element at i, or it extends the best subarray ending at i-1: $best(i) = \max(nums[i],\ best(i-1) + nums[i])$. Because $best(i)$ only depends on $best(i-1)$, one forward pass that always keeps the running value non-negative (resetting to the current element whenever continuing the previous run would help less than starting fresh) computes every $best(i)$ without ever revisiting earlier elements.

Why it still works for all-negative input

If every number is negative, a running sum that is allowed to reset to 0 whenever it goes non-positive would settle on 0 forever, which is wrong: there is no such thing as an empty subarray sum of 0 among the valid answers here, since a subarray must contain at least one element. Initializing the running sum from nums[0] (not from 0) and comparing against best_sum from the very first element sidesteps this: the algorithm naturally reports the largest (least negative) single element when nothing better exists.

Adapting to maximum product

Sum and product behave differently under a negative number: adding a negative always makes a running sum smaller, but multiplying by a negative flips the sign, so the smallest (most negative) running product can become the largest running product on the very next multiplication. The fix is to track both a running maximum and a running minimum product ending at the current index, and at each step consider all three candidates (the current element alone, the running max times the current element, and the running min times the current element) for both the new max and the new min.

Worked example

def max_subarray_sum(nums: list[int]) -> tuple[int, int, int]:
    """
    Kadane's algorithm. O(n) time, O(1) extra space.
    Returns (best_sum, start_index, end_index), inclusive.
    """
    if not nums:
        raise ValueError("nums must be non-empty")
    best_sum = running_sum = nums[0]
    best_l = best_r = run_start = 0
    for i in range(1, len(nums)):
        x = nums[i]
        if running_sum <= 0:
            running_sum = x
            run_start = i
        else:
            running_sum += x
        if running_sum > best_sum:
            best_sum = running_sum
            best_l, best_r = run_start, i
    return best_sum, best_l, best_r


def max_subarray_product(nums: list[int]) -> int:
    """
    Track running max AND running min, since multiplying by a negative
    number can turn the running min into the new running max.
    O(n) time, O(1) extra space.
    """
    if not nums:
        raise ValueError("nums must be non-empty")
    best = curr_max = curr_min = nums[0]
    for x in nums[1:]:
        candidates = (x, curr_max * x, curr_min * x)
        curr_max, curr_min = max(candidates), min(candidates)
        best = max(best, curr_max)
    return best


if __name__ == "__main__":
    all_negative = [-3, -1, -4, -1, -5]
    print("all-negative sum:", max_subarray_sum(all_negative))

    mixed = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print("mixed sum:", max_subarray_sum(mixed))

    product_case = [2, 3, -2, 4]
    print("product [2,3,-2,4]:", max_subarray_product(product_case))

    product_flip = [-2, 3, -4]
    print("product [-2,3,-4]:", max_subarray_product(product_flip))

Running this prints:

all-negative sum: (-1, 1, 1)
mixed sum: (6, 3, 6)
product [2,3,-2,4]: 6
product [-2,3,-4]: 24

For the all-negative array [-3,-1,-4,-1,-5], the best single element is -1 at index 1, matching the printed (-1, 1, 1). For the mixed array [-2,1,-3,4,-1,2,1,-5,4], the best subarray is indices 3 through 6 ([4,-1,2,1], summing to 6), matching the printed (6, 3, 6). For the product case [2,3,-2,4], the best product subarray is [2,3] giving 6; a full sweep including the trailing -2,4 would only give $2\times3\times(-2)\times4=-48$, confirming stopping at [2,3] is correct. For [-2,3,-4], the running-minimum trick matters directly: [-2] alone gives -2, [-2,3] gives -6, but the full array [-2,3,-4] gives $(-2)\times3\times(-4)=24$, the printed maximum, which only surfaces because the running minimum after [-2,3] (which is -6) gets multiplied by the next -4 and becomes the new running maximum.

Complexity

Time: $O(n)$ for both the sum and the product version (a single pass). Space: $O(1)$ extra for both.

Edge cases

• Empty input has no valid subarray; decide and state the desired behavior (raising, as here, is a reasonable default) rather than silently returning 0.
• A single-element array returns that element itself for both the sum and product versions.
• All-zero input for the product version needs the running max/min reset logic to correctly treat 0 as its own candidate, since 0 can be both the best local product (better than continuing a negative run) and a reset point.
• Very large products can overflow fixed-width integer types in languages that have them; Python's arbitrary-precision integers sidestep this, but it is worth naming as a real constraint in a language like C or Java.

Trade-offs & pitfalls

The most common wrong turn on the all-negative case is resetting the running sum to 0 whenever it goes negative rather than initializing from nums[0] and tracking the best sum from the start; that silently produces the wrong answer (0) instead of the correct least-negative single element. The most common wrong turn on the product adaptation is tracking only a running maximum, by direct analogy with the sum version, and missing that a running minimum is equally necessary because of how sign flips interact with multiplication. This family of one-pass running-state techniques is related to, but not identical to, two other fixed-window restatements sometimes asked alongside it: a fixed-window moving average keeps a single running sum, adding the newest element and subtracting the one that just fell out of the window, which is a simpler O(1)-per-step update than Kadane's since the window boundary is known in advance rather than discovered by a reset rule; a fixed-window moving maximum cannot get away with a single running maximum at all, because the current maximum can itself fall out of the window, so it needs a monotonic deque (a double-ended queue kept in decreasing order, so the front is always the window's current maximum) to know the next-best candidate the moment the old maximum expires. Naming that distinction (which of these needs one running value, and which needs a small ordered structure) is the difference between a correct and an incorrect answer to that folded variant, not just a stylistic choice.