Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Use binary (fast) exponentiation: repeatedly square the base and, on each bit of n that is set, multiply that squared value into the running result. This computes $x^n$ in O(log|n|) multiplications instead of O(n). A negative exponent is handled by inverting the base once up front (1/x) and treating the exponent as positive from then on.

Structured elaboration

Core idea: writing n in binary decomposes the power into a product of the base raised to each power-of-two position where n has a set bit:
$x^n = \prod_{i \,:\, \text{bit}_i(n)=1} x^{2^i}$
Squaring the base once per bit position produces exactly the $x^{2^i}$ terms needed, in the same single pass that reads the bits of n.

def my_pow(x: float, n: int) -> float:
    """
    Compute x**n via binary (fast) exponentiation in O(log|n|) time, O(1) space.
    Handles negative exponents and the 32-bit min-int edge case (in fixed-width languages).
    """
    if x == 0.0:
        if n > 0:
            return 0.0
        if n == 0:
            return 1.0
        raise ZeroDivisionError("0 cannot be raised to a negative power")

    exponent = n
    base = x
    if exponent < 0:
        base = 1.0 / base
        exponent = -exponent

    result = 1.0
    while exponent:
        if exponent & 1:
            result *= base
        base *= base
        exponent >>= 1
    return result


print(my_pow(2.0, 10))
print(my_pow(2.0, -3))
print(my_pow(3.0, 0))
print(my_pow(-2.0, 5))

Output:

1024.0
0.125
1.0
-32.0

Negative-exponent handling: invert x once, negate n, and reuse the same positive-exponent loop; in Python this negation is always safe since ints are arbitrary precision, but in a fixed-width 32-bit language, the most negative representable exponent must first be widened to a 64-bit type before negating it, since negating it directly overflows.

Worked example

Tracing $x=2, n=10$ (binary 1010) bit by bit:

The two set bits (positions 1 and 3) contribute $x^{2^1} \cdot x^{2^3} = 4 \cdot 256 = 1024 = 2^{10}$, matching the printed result exactly.

Complexity

$O(\log|n|)$ time, $O(1)$ space for the iterative version above (a recursive version instead
uses $O(\log|n|)$ call-stack space).

Edge cases

• n = 0: the while exponent loop never executes (exponent starts at 0), returning
  result = 1.0, matching my_pow(3.0, 0) -> 1.0.
• x = 0, n > 0: explicitly special-cased to return 0.0 before the main loop.
• x = 0, n = 0: explicitly special-cased to return 1.0 by convention.
• x = 0, n < 0: explicitly raises ZeroDivisionError, since 0 to a negative power is
  mathematically undefined; this must be special-cased rather than silently returning infinity
  or crashing with an unclear error.
• Negative base: sign is preserved correctly through repeated squaring and multiplication,
  e.g. my_pow(-2.0, 5) = -32.0.
• Most-negative fixed-width exponent (e.g. INT32_MIN): not an issue for Python's
  arbitrary-precision ints, but in a fixed-width 32-bit language the most negative representable
  exponent must be widened to a 64-bit type before negating it, since negating it directly
  overflows.

Trade-offs & pitfalls

• Floating-point precision: repeated squaring compounds rounding error faster than repeated multiplication in some regimes; for |x| very close to 1 raised to a huge power, or extreme |n| combined with |x| far from 1, relative error can grow. Computing via exp(n * log(x)) is an alternative when raw precision matters more than speed, but that requires x > 0 (log is undefined otherwise) and introduces its own rounding from the exp/log calls.
• Modular exponentiation: if the actual need is $x^n \bmod m$ (as in cryptographic-sized exponents), the accumulation step becomes (result * base) % m at every multiply, keeping every intermediate value bounded to a fixed size instead of letting a plain big-integer power grow unboundedly large.

Direct answer

Push every opening bracket onto a stack. On a closing bracket, it must match whatever opener currently sits on top of the stack; if it does not, or the stack is already empty, the string is invalid. After the scan, the string is valid only if the stack is empty, meaning every opener found a partner. This runs in $O(n)$ time and $O(n)$ space.

Structured elaboration

A stack models "the most recently opened, still-unclosed bracket" exactly, because it is last-in-first-out (LIFO): whichever opener was pushed most recently is always the one that must be closed next, and that is precisely what sits on top. Checking a closer against the top of the stack is an $O(1)$ lookup through a small mapping () pairs with (, ] with [, } with {).

Counting bracket types separately (how many ( versus how many )) is not enough: a string can have perfectly equal counts of every bracket type and still be invalid because the nesting order is wrong, for example ([)]. Only a structure that remembers order, like a stack, can catch that.

Worked example

def is_valid_brackets(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack


if __name__ == "__main__":
    tests = ["()[]{}", "(]", "([)]", "{[]}"]
    print([is_valid_brackets(t) for t in tests])

Running this prints [True, False, False, True]. Trace ([)]: push (, push [, then see ); the top of the stack is [, which does not pair with ), so the function returns False immediately, even though the overall bracket counts are balanced.

Complexity

Time: $O(n)$, one pass over the string doing $O(1)$ work per character.
Space: $O(n)$ worst case, since a string of all opening brackets pushes every character onto the stack before the scan ends.

Edge cases

• Empty string: the stack never receives a push, so it is empty at the end and the function correctly returns True.
• A lone unmatched opening bracket at the very end: the stack is non-empty when the scan finishes, so the final not stack check (not just the per-character comparisons) is what catches it.
• A closing bracket with nothing open: stack is empty when a closer arrives, so the code must check not stack before indexing stack[-1], or it raises instead of returning False cleanly.

Trade-offs & pitfalls

Using a single stack with a pairs mapping generalizes cleanly to any number of bracket types; writing a separate counter per bracket type cannot detect ordering violations no matter how many counters you add.

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

Start with two pointers at the far-left and far-right lines and compute the area between them as the width times the shorter of the two heights, since the shorter line is what actually limits how much water the pair can hold. Then repeatedly move whichever pointer marks the shorter line one step inward, tracking the best area seen. This is safe because keeping the shorter line fixed and moving the taller one inward can only shrink the width while the limiting height stays the same or gets worse, so that move can never beat the current area; moving the shorter line is the only move that has any chance of finding a taller line and thus a larger limiting height.

Approach

• Initialize left = 0 and right = len(height) - 1.
• At each step, compute area = min(height[left], height[right]) * (right - left) and update the best area seen.
• Move the pointer at the shorter height inward (left += 1 or right -= 1); if the two heights are equal, either pointer can move.
• Stop when left == right.

from typing import List


def max_area(height: List[int]) -> int:
    """Two-pointer O(n) time, O(1) space solution."""
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best


if __name__ == "__main__":
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
    print(max_area([1, 1]))                        # 1
    print(max_area([4, 3, 2, 1, 4]))               # 16

Running this prints 49, 1, 16. For [1, 8, 6, 2, 5, 4, 8, 3, 7], the best area of 49 comes from index 1 (height 8) and index 8 (height 7): width $8 - 1 = 7$ times limiting height $\min(8, 7) = 7$ gives $49$, and no other pair in that array beats it.

Key points

• The greedy step only works because the pointer you leave behind (the taller one) was never the bottleneck for the current pair, so discarding it costs nothing you could have used; discarding the shorter one instead would throw away the only pointer that could have found something taller.
• Equal heights at both pointers: either pointer can move; the tie means both sides are equally the "shorter" one for that comparison.
• In a fixed-width-integer language (Java, C++), height * width can overflow a 32-bit integer for very large inputs; use a 64-bit accumulator for the area. Python integers don't have this issue, but it's a real production concern in typed languages.

Complexity

Time: $O(n)$, a single pass with the two pointers converging. Space: $O(1)$, only the two pointers and a running best value.

Edge cases

• Fewer than two lines: no container is possible, so the answer is 0.
• All heights equal: every pair's limiting height is the same, so the widest pair (the two endpoints) wins.
• A height of 0 at some position contributes an area of 0 whenever it's one of the two chosen lines, which is harmless, just never optimal.
• This two-pointer approach only finds the best area between two chosen lines; it does not generalize directly to the harder "water trapped above every bar" version of this problem (where interior bars can also trap water above them), since that variant needs to track a running maximum height from the left and from the right at every position, not just a single global best between two outer lines. It's a natural harder extension of the same converging-pointer idea, but with per-position bookkeeping added on top.

Direct answer

Bucket entities into a uniform grid whose cell size is close to the query radius r, so a "find nearby objects" search only has to inspect a small, fixed neighborhood of cells (typically the 3x3 block around the query point) instead of scanning the whole population. On each frame, only remove a moved object from its old cell and insert it into its new one, rather than rebuilding the structure from scratch. Reach for a hierarchical structure like a quadtree/octree or a bounding volume hierarchy (BVH) only once objects are unevenly clustered enough that a single fixed cell size stops fitting the whole space well.

Structured elaboration

Why brute force is O(n^2) and bucketing fixes it: comparing every pair costs O(n^2); with buckets sized around r, the expected work per query is O(k) where k is the number of objects in the local neighborhood, independent of n.

Cell sizing: choose cell_size $\approx$ r, so a query only ever needs to check
$\text{cells checked} = \left(2\left\lceil \frac{r}{c} \right\rceil + 1\right)^2$
cells around the query point. Too small a cell size means checking many empty cells; too large means each cell holds many objects that still need an exact-distance filter.

Update strategy for moving objects: don't rebuild the whole grid every frame. On each object's move, compute its old and new cell; if they differ, remove/re-insert only that one object (O(1) amortized (averaged over a sequence of operations)), leaving every other object's bucket untouched.

from collections import defaultdict
import math

class UniformGrid:
    """
    Uniform spatial hash grid for 2D points. Cell size should be ~ the
    query radius r, so a range query only has to look at a small,
    constant number of neighboring cells regardless of n.
    """
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self.cells = defaultdict(set)   # (cx, cy) -> set of entity ids
        self.positions = {}              # entity id -> (x, y)

    def _cell_of(self, x, y):
        return (math.floor(x / self.cell_size), math.floor(y / self.cell_size))

    def insert(self, entity_id, x, y):
        cell = self._cell_of(x, y)
        self.cells[cell].add(entity_id)
        self.positions[entity_id] = (x, y)

    def update(self, entity_id, x, y):
        old_cell = self._cell_of(*self.positions[entity_id])
        new_cell = self._cell_of(x, y)
        if old_cell != new_cell:
            self.cells[old_cell].discard(entity_id)
            self.cells[new_cell].add(entity_id)
        self.positions[entity_id] = (x, y)

    def query_radius(self, x, y, r):
        """Ids within radius r of (x, y). Assumes r <= cell_size so only
        the 3x3 neighborhood of cells needs checking."""
        cx, cy = self._cell_of(x, y)
        span = max(1, math.ceil(r / self.cell_size))
        found = []
        for dx in range(-span, span + 1):
            for dy in range(-span, span + 1):
                for eid in self.cells.get((cx + dx, cy + dy), ()):
                    ex, ey = self.positions[eid]
                    if (ex - x) ** 2 + (ey - y) ** 2 <= r * r:
                        found.append(eid)
        return found


grid = UniformGrid(cell_size=10)
points = {
    "A": (0, 0),
    "B": (3, 4),     # distance 5 from A
    "C": (100, 100),
    "D": (8, 1),     # distance ~8.06 from A
}
for eid, (x, y) in points.items():
    grid.insert(eid, x, y)

print(sorted(grid.query_radius(0, 0, r=6)))   # expect A, B
print(sorted(grid.query_radius(0, 0, r=9)))   # expect A, B, D

grid.update("C", 1, 1)  # C moves next to A
print(sorted(grid.query_radius(0, 0, r=6)))   # expect A, B, C

Output:

['A', 'B']
['A', 'B', 'D']
['A', 'B', 'C']

flowchart TB
  Q[Query point plus radius r] --> G[Uniform grid: locate cell]
  G --> N[Scan 3x3 neighboring cells]
  N --> C1[Sparse cell bucket]
  N --> C2[Dense cell bucket]
  C2 --> BVH[Per-cell BVH for dense cluster]
  C1 --> R[Candidate objects]
  BVH --> R
  R --> F[Filter by exact distance]

Folding the sibling framings: a geospatial nearest-neighbor / bounding-box index over points of interest (POIs) is the same uniform-grid-or-quadtree choice, but with a much lower update rate: points rarely move, so rebuild-on-ingest is fine instead of per-frame updates. Web-map marker clustering at a given zoom level is the same structure choice again, except "cell size" is derived from the current zoom's pixel-to-distance ratio rather than a fixed world-space radius, and re-bucketing happens on zoom change instead of every animation frame. The general "brute-force O(n^2) overlap check needs a better structure" framing is the same problem stated without a specific domain at all.

Worked example

With cell_size=10 and four points, A at the origin, B at distance 5, D at distance roughly 8.06, and C far away at (100, 100), a radius-6 query from the origin correctly returns only A and B (as shown in the run above), and widening to radius 9 pulls in D as well. After C is moved to (1, 1), right next to the origin, the SAME radius-6 query now also returns C, confirming the incremental update() correctly re-buckets a moved object without touching anything else in the grid.

Complexity

For the UniformGrid code above: insert/update are $O(1)$ average, a fixed number of
dict/set operations regardless of $n$. query_radius is $O(k)$ average, where $k$ is the
number of objects in the $(2 \cdot \text{span} + 1)^2$ neighboring cells scanned
(span = ceil(r / cell_size)), assuming roughly uniform density, plus one $O(1)$
exact-distance check per candidate. Space is $O(n)$ for positions plus
$O(n + \text{cells used})$ for cells. The table above gives the corresponding bounds for
quadtree/octree and BVH alternatives.

Edge cases

• Empty grid: query_radius on a grid with nothing inserted returns [] immediately,
  since no cell is populated.
• r much larger than cell_size: span = max(1, ceil(r / cell_size)) still scans
  correctly, but the scanned neighborhood grows with r, so a query radius far exceeding the
  cell size degrades toward brute force over the affected region.
• update() on an id never inserted: self.positions[entity_id] raises a KeyError, since
  update() assumes the entity already exists.
• Query point on a cell boundary: math.floor cleanly assigns it to one cell, and the
  3x3-or-wider neighborhood scan still covers points just across that boundary in the adjacent
  cell.
• All objects clustered in one cell: a uniform grid degrades toward brute force within that
  single dense cell, which is exactly why a hierarchical structure (quadtree/BVH) is proposed
  once density gets that uneven.

Trade-offs & pitfalls

• A uniform grid degrades toward brute force WITHIN a cell if the cell size is chosen too large relative to local object density.
• If object sizes vary a lot, a single global cell size stops fitting everything; a hierarchical grid or loose quadtree handles that better than one fixed cell size.
• Rebuilding the whole structure from scratch every frame (instead of incrementally moving only the objects that changed cell) throws away the O(1)-amortized-move benefit, turning the approach into O(n) work per frame regardless of the query pattern, which defeats the purpose for every-frame queries.
• A BVH is attractive when most objects are static or only their transforms change (cheap refit); once objects change TOPOLOGY (spawn, despawn, jump far), a BVH needs a real rebuild, not just a refit.