Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Correctness requires every node's value to respect the bounds imposed by all of its ancestors, not just its immediate parent and immediate children. Carry a (low, high) exclusive range down the recursion, tightening it at each step, and reject any node whose value falls outside its inherited range. This is $O(n)$ time and $O(h)$ space, where h is the tree's height.

Structured elaboration

The naive bug. A common but incorrect check only compares a node to its immediate left and right children:

def is_valid_bst_naive(node):
    if not node:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_valid_bst_naive(node.left) and is_valid_bst_naive(node.right)

Consider the tree below: root 10, left child 5, right child 15, and 15's own children are 6 and 20.

graph TD
  A[10] --> B[5]
  A --> C[15]
  C --> D[6]
  C --> E[20]

Every local comparison passes: 5 < 10, 15 > 10, 6 < 15, 20 > 15. The naive check therefore reports this tree as a valid binary search tree (BST). But it is not: node 6 sits in the right subtree of the root (10), so every value in that subtree, including 6, must be greater than 10. It is not. The naive check has no memory of the root's bound by the time it looks at 6, because it only ever compares a node to its direct children.

The fix. Carry the inherited bounds explicitly, tightening them one level at a time:

def is_valid_bst(root):
    def helper(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return helper(node.left, low, node.val) and helper(node.right, node.val, high)
    return helper(root, float("-inf"), float("inf"))

An equally correct, structurally different alternative is an iterative inorder traversal that checks the visited sequence comes out strictly increasing; it relies on the fact that inorder traversal of a genuinely valid BST always produces sorted values, so it catches the same violation without ever carrying explicit bounds.

Worked example

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_valid_bst_naive(node):
    if not node:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_valid_bst_naive(node.left) and is_valid_bst_naive(node.right)


def is_valid_bst(root):
    def helper(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return helper(node.left, low, node.val) and helper(node.right, node.val, high)
    return helper(root, float("-inf"), float("inf"))


if __name__ == "__main__":
    root = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))
    print(is_valid_bst_naive(root), is_valid_bst(root))

Running this prints True False: the naive, buggy check wrongly calls the tree valid, and the bounds-checked version correctly rejects it.

Complexity

Time: $O(n)$, since each node is visited exactly once by the bounds-checking recursion (or the equivalent iterative inorder-traversal alternative).
Space: $O(h)$, where h is the tree's height, from the recursion call stack; this is $O(\log n)$ for a balanced tree and $O(n)$ worst case for a completely skewed one.

Edge cases

• Empty tree (root is None): trivially valid, since the base case of the recursion returns True immediately.
• Single-node tree: trivially valid regardless of its value, since there are no bounds to violate.
• Duplicate values: must be rejected with a strict inequality (low < node.val < high); a BST with <= semantics on one side is a different, looser invariant that must be stated explicitly.

Trade-offs & pitfalls

This naive-check bug is one of the most common mistakes in BST-validation answers precisely because it looks correct on any small, balanced example where an ancestor's bound never actually gets violated by a distant descendant; it takes a specific counter-example like the one above to expose it.

Direct answer

Reach for a hash map whenever you need the fastest average lookup, insert, and delete and do not care about the order keys come out in. Reach for an ordered structure (a balanced binary search tree, BST for short, meaning a tree kept balanced so its height stays logarithmic; or a skip list, a linked structure with multiple randomly-built "express lane" levels that gives logarithmic search without needing tree rebalancing) whenever you need range queries, sorted iteration, or predecessor/successor lookups, since a hash map fundamentally cannot answer those without scanning every entry.

Structured elaboration

Concrete case where a hash map wins: an in-memory cache keyed by an exact request signature, for example caching a computed response by its full input hash, where every lookup is "does this exact key exist" and there is no notion of "keys near this one" that would ever be queried. The $O(1)$ average lookup directly minimizes latency, and there is nothing to give up, since ordering was never needed.

Concrete case where giving up hash-map speed pays off: a scheduler that needs "the next event after this timestamp." That is a successor query, unsupported by a hash map without scanning every key, but native to an ordered structure in $O(\log n)$. Trading average-case $O(1)$ for guaranteed $O(\log n)$ is a clear win here because the operation the hash map cannot do at all is the operation the system needs on every scheduling step.

Trade-offs & pitfalls

A hash map's worst-case degrades to $O(n)$ under pathological collisions, though modern implementations mitigate this with randomized hash seeding; an ordered structure's $O(\log n)$ is a hard guarantee regardless of key distribution, which matters if an adversary can influence which keys get inserted (for example, in a public-facing API). A common mistake is reaching for an ordered structure "just in case sorted output is needed later," which pays the $O(\log n)$ tax on every single operation for a benefit that may never be used; the right trigger is a concrete, recurring range or predecessor/successor query in the actual access pattern, not a hypothetical one. It is also common to forget that some hash map implementations preserve insertion order as an incidental property (not a sorted, comparison-based order), which is a much weaker guarantee than a true ordered structure's ability to iterate or range-query by key value.

Direct answer

A plain binary search that stops as soon as it finds any matching element can land on any of several equal occurrences, not necessarily the first one. To find the boundary instead, keep searching left even after finding a match: record the match as a candidate answer, then continue narrowing into the left half, so the search only stops once the range has collapsed and the leftmost qualifying index is guaranteed to be the last one recorded.

Structured elaboration

Approach

• Define the search as finding the first index i such that arr[i] >= target (a "lower bound"), over a half-open range [lo, hi) where hi starts at len(arr).
• At each step, compute mid. If arr[mid] >= target, mid could be the answer, but there might be an earlier index just as good, so shrink hi to mid (keep looking left) rather than stopping. If arr[mid] < target, the answer must be strictly to the right, so move lo to mid + 1.
• The loop invariant: every index below lo is known to be < target, and every index at or above hi is not yet ruled out only because it isn't needed anymore. When lo == hi, that boundary is exactly the first index >= target.
• To get the first and last index a value actually occupies, call this lower-bound search twice: once for target, and once for target + 1 (whose result, minus one, gives the last index of target). This is exactly the "first event at or after a given time" query run against a timestamp-ordered log or time series: the same lower-bound primitive, just with timestamps standing in for the sorted values.

def lower_bound(arr, target):
    """
    First index i such that arr[i] >= target, or len(arr) if none exists.
    arr is sorted ascending and may contain duplicates.
    """
    lo, hi = 0, len(arr)  # half-open search space [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid       # mid could be the answer; keep looking left
        else:
            lo = mid + 1   # mid is too small; answer must be to the right
    return lo


def first_and_last(arr, target):
    first = lower_bound(arr, target)
    if first == len(arr) or arr[first] != target:
        return (-1, -1)
    last = lower_bound(arr, target + 1) - 1
    return (first, last)

Key points

• The invariant "never stop early on a match, keep narrowing left" is what prevents landing on an arbitrary occurrence of a duplicated value.
• A half-open range [lo, hi) with hi = mid on a match (not mid - 1) avoids the classic off-by-one that causes an infinite loop when lo and hi become adjacent.

Worked example

log = [1, 3, 3, 3, 5, 8, 8, 10]. lower_bound(log, 3) returns 1 (the first of the three 3s). lower_bound(log, 4) returns 4 (no 4 exists, but index 4 holds 5, the first value >= 4, sitting between the run of 3s and the 5). lower_bound(log, 11) returns 8 (one past the end, since nothing is >= 11). first_and_last(log, 8) returns (5, 6) (the two 8s). first_and_last(log, 6) returns (-1, -1) (6 is not present at all).

Trade-offs & pitfalls

Complexity

Time: $O(\log n)$ per lower-bound search; finding both the first and last index of a value costs two searches, still $O(\log n)$ overall.
Space: $O(1)$.

Edge cases

• Empty array: lo starts equal to hi (both 0), the loop never runs, returns 0, meaning "insert here" or "not found."
• Target smaller than every element: returns 0.
• Target larger than every element: returns len(arr).
• Target absent but between two existing values: returns the index of the next-larger value, the correct insertion point even though the value itself isn't present.

Writing the comparison as arr[mid] == target and stopping immediately is what causes an ordinary binary search to return an arbitrary occurrence, since equal-valued matches don't distinguish which one was found. For very large or on-disk sorted data, such as a timestamp-indexed log too big to hold in memory, the same lower-bound logic still applies as long as an element can be fetched by index in roughly constant time (a memory-mapped file, fixed-width records, or a block index all work); if only sequential reads are available, an exponential-search-style probe would be needed first to find a bounding block before binary searching within it.

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.

Direct answer

A plain stack already gives $O(1)$ push, pop, and top because those operations only ever touch the top element. The trick for $O(1)$ minimum retrieval is to keep a second, parallel stack that tracks what the minimum would be after each push: whenever you push a value onto the main stack, you also push the smaller of that value and the previous minimum onto the min-stack, so its top is always the correct current minimum, and popping both stacks together keeps them in sync without ever rescanning.

Approach

• Maintain two stacks of equal length at all times: stack holds the real values, min_stack holds, at each position, what the minimum was after that push.
• push(x): append x to stack. Append x to min_stack if min_stack is empty or x is less than or equal to its current top; otherwise append the current top again (repeating the still-current minimum).
• pop(): pop from both stacks together; the value from stack is returned, the value from min_stack is discarded.
• get_min(): return min_stack's top directly.

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]


if __name__ == "__main__":
    s = MinStack()
    s.push(5)
    s.push(3)
    s.push(7)
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 5
    print(s.top())       # 5

Running this prints 3, 3, 5, 5: after pushing 5, 3, 7 the minimum is 3; popping 7 (the top) leaves the minimum still 3; popping 3 next leaves only 5, so both the minimum and the top become 5.

Key points

• Using <= (not strict <) when deciding whether to push a new minimum is what makes duplicate minimum values work correctly: if two entries tie for the minimum and you only recorded the first, popping it would incorrectly raise the recorded minimum before the still-present duplicate is gone.
• An alternative "encoded delta" trick stores a single stack, keeping only a running minimum variable, and pushes a value relative to that minimum instead of the raw value, updating the running minimum on push/pop as needed. It roughly halves auxiliary storage but is more error-prone to implement correctly, especially in fixed-width-integer languages (C++, Java) where the encoded delta itself can overflow if the gap between the pushed value and the previous minimum is large.

Complexity

Time: $O(1)$ for every operation (push, pop, top, get_min). Space: $O(n)$ auxiliary for $n$ elements (two stacks, each up to size $n$; a larger constant factor than a single stack, but still linear).

Edge cases

• pop or top on an empty stack should raise or otherwise signal an error rather than reading past the end.
• Duplicate values at the current minimum: handled correctly only if the min-stack push condition uses <=, not <.
• A single-element stack: get_min() must equal top().