Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Sort the three-valued array in one pass with three pointers, low, mid, high, that carve it into a growing "already-placed-0s" region, a "confirmed-1s" region, and a "not-yet-placed-2s" region, swapping at most once per position and using no extra storage (the Dutch National Flag algorithm). The same low/high swap idea generalizes directly to a two-way in-place partition by any predicate, but that direct generalization is not stable: swapping elements out of place can scramble the relative order of items that land in the same output region, so keeping order stable needs an extra step beyond just relabeling the predicate.

Structured elaboration

The three-way invariant

At every point during the scan: everything before low is 0, everything in [low, mid) is 1, everything after high is 2, and mid is the next unclassified element. When nums[mid] == 0, swapping it to low and advancing both pointers is safe because the element that lands at mid from the swap was already known to be 1 (it came from inside [low, mid)). When nums[mid] == 2, swapping it to high and only decrementing high (not advancing mid) is required because the element swapped in from the unexplored tail is unclassified and must still be examined.

Generalizing to an arbitrary predicate, and where stability breaks

Collapsing the three categories to two, "satisfies the predicate" versus "does not", turns this into the standard in-place two-way partition: scan with a single pointer, swap anything satisfying the predicate to the front. This preserves the $O(n)$ time, $O(1)$ space profile, but it is not stable: a swap moves an element across positions that may already hold other same-category elements, and nothing about the swap preserves their relative order. The demonstration below shows two items in the same category (both satisfying the predicate) ending up reordered relative to each other purely because of how the swaps landed, even though the partition itself (which items are in which category) is correct.

To keep relative order stable while partitioning in place, the pointer-swap approach is not enough on its own. Two honest options:

• Trade space for stability (simple): scan once, appending predicate-true and predicate-false items to two separate output lists in encounter order, then concatenate. This is $O(n)$ time and stable by construction, at the cost of $O(n)$ auxiliary space, no longer in-place.
• Keep $O(1)$ space, pay in time (advanced): a genuinely in-place and stable partition is possible using a recursive divide-and-rotate scheme, partition each half of the array independently, then merge the two halves' boundary regions by rotating the "false" suffix of the left half past the "true" prefix of the right half. This is the same technique behind library-grade in-place stable partitions (for example, C++'s std::stable_partition is specified to do at most $O(n \log n)$ swaps in the general case, or a single linear pass if it is allowed to allocate a temporary buffer). It is a materially different algorithm from the plain DNF swap, not just the same three-pointer idea relabeled.

Worked example

Approach

First, the DNF sort itself:

def dutch_national_flag(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

print(dutch_national_flag([2, 0, 2, 1, 1, 0]))

This prints [0, 0, 1, 1, 2, 2].

Second, the two-way generalization by predicate, showing the instability directly on tagged items so reordering is visible:

def unstable_partition(items, pred):
    lo = 0
    for i in range(len(items)):
        if pred(items[i]):
            items[lo], items[i] = items[i], items[lo]
            lo += 1
    return items

labeled = [('a', 1), ('b', 0), ('c', 1), ('d', 0), ('e', 1)]
print(unstable_partition(labeled[:], lambda t: t[1] == 1))

def stable_partition(items, pred):
    true_bucket = [x for x in items if pred(x)]
    false_bucket = [x for x in items if not pred(x)]
    return true_bucket + false_bucket

print(stable_partition(labeled[:], lambda t: t[1] == 1))

This prints:

[('a', 1), ('c', 1), ('e', 1), ('d', 0), ('b', 0)]
[('a', 1), ('c', 1), ('e', 1), ('b', 0), ('d', 0)]

The swap-based version reorders 'b' and 'd' relative to each other (both are category-0, and 'd' ends up before 'b', the reverse of their original order), while the extra-buffer version preserves 'b' before 'd' exactly as encountered.

Key points

• The DNF three-pointer scan and the two-way predicate partition are the same swap mechanism; only the number of categories changes.
• Correctness of which bucket each item lands in is unaffected by the instability; only the order within a bucket is at risk.
• Stability and true in-place ($O(1)$ space) are in tension for this problem: you can have both only by accepting $O(n \log n)$ time via the rotation-based approach, or you can have $O(n)$ time by giving up in-place-ness.

Complexity

DNF: time $O(n)$ (single pass, mid never revisits a position), space $O(1)$.
Unstable two-way partition: time $O(n)$, space $O(1)$.
Stable partition via extra buffer: time $O(n)$, space $O(n)$.

Edge cases

• Empty array, single element, or an already-sorted array: the DNF loop terminates immediately or after trivial no-op passes.
• All elements identical (all 1s, for instance): low never advances, mid sweeps straight to high with no swaps.
• A predicate that is trivially true or false for every element: the two-way partition degenerates to a no-op copy.

Trade-offs & pitfalls

The most common mistake when moving from three-way DNF to a two-way predicate partition is assuming the result is automatically stable "because it's the same kind of algorithm." It is not, and that distinction matters directly whenever a partition needs to preserve, for example, insertion order or timestamp order within each output group (a very common real requirement, such as partitioning a task queue into "ready" versus "blocked" while keeping each group's original ordering). Reaching for the swap-based version there without checking the stability requirement is a silent correctness bug, not just a style choice. When stability genuinely is not required, the swap-based version remains the better default: no allocation, single pass, and it generalizes cleanly to $k$-way partitioning by widening from two pointers to $k-1$ boundary pointers.

Direct answer

A plain prefix-sum array gives O(1) range-sum queries but forces an O(n)
rebuild whenever a single element changes, since every prefix after it shifts.
The structure that supports both range-sum queries and point updates in
$O(\log n)$ is a Binary Indexed Tree, commonly called a Fenwick tree
(named for its inventor, Peter Fenwick): an implicit tree layered over the
array where each node stores the sum of a specific, power-of-two-sized range,
so that both "add a value at one index" and "sum everything up to an index"
touch only $O(\log n)$ nodes, by walking a path determined by the binary
representation of the index.

Structured elaboration

Why plain prefix sums fail the update requirement. If prefix[i] stores
the sum of all elements before index i, a range query is one subtraction,
$O(1)$, but changing a single array element invalidates every prefix sum
from that index onward, an $O(n)$ fix. The question specifically asks for
both operations in $O(\log n)$, so a data structure is needed where a
single update only touches a bounded, logarithmic set of stored partial sums,
not a full contiguous range of them.

How a Fenwick tree gets both operations to $O(\log n)$. Index the
array 1-based internally. Each position i in the underlying tree array
stores the sum of a range of the original array whose length is the lowest
set bit of i (in binary): position 6 (110) stores a range of length 2
(the lowest set bit of 6 is 2), position 8 (1000) stores a range of length
8, and so on. This gives two walks, both bounded by the number of bits in
n, i.e. $O(\log n)$:

• Point update (add(i, delta)): starting at i, repeatedly jump to
  i += i & (-i) (moving to the next node whose range also covers i),
  adding delta at each stop, until past the end of the array. i & (-i)
  isolates the lowest set bit of i in two's-complement arithmetic, which is
  exactly the jump size that walks you through every ancestor node covering
  this index.
• Prefix-sum query (prefix_sum(i)): starting at i, repeatedly add the
  stored value and jump to i -= i & (-i) (stripping the lowest set bit),
  until reaching 0. Each step consumes one bit of i's binary representation,
  which is why the walk terminates in at most $\log_2 n$ steps.

Both operations only ever visit nodes on a path determined by clearing or
adding the lowest set bit, which is why each is $O(\log n)$ rather than
$O(n)$: a Fenwick tree never needs to touch a whole contiguous range of
stored sums the way a plain prefix array does.

Range sum from two prefix sums. range_sum(l, r) = prefix_sum(r) - prefix_sum(l - 1),
same subtraction trick as a plain prefix array, just built on top of
$O(\log n)$ prefix queries instead of $O(1)$ ones, trading a little query
speed for tractable updates.

Worked example

class FenwickTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (self.n + 1)
        for i, x in enumerate(nums):
            self._add(i, x)

    def _add(self, i, delta):
        i += 1  # 1-indexed internally
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def update(self, i, new_value):
        current = self.prefix_sum(i) - (self.prefix_sum(i - 1) if i > 0 else 0)
        self._add(i, new_value - current)

    def prefix_sum(self, i):
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_sum(self, left, right):
        if left > right:
            return 0
        left_part = self.prefix_sum(left - 1) if left > 0 else 0
        return self.prefix_sum(right) - left_part

nums = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2]
ft = FenwickTree(nums)
print(ft.range_sum(0, 9))  # sum of all elements
print(ft.range_sum(2, 5))  # -1 + 6 + 5 + 4
ft.update(2, 10)           # nums[2] changes from -1 to 10
print(ft.range_sum(2, 5))  # 10 + 6 + 5 + 4
print(ft.range_sum(0, 9))  # total shifts by the same +11 delta

Output (verified by running this exact code):

28
14
25
39

This was additionally cross-checked with a 200-operation randomized test
(seed 42) comparing every range_sum result against a brute-force
sum(arr[l:r+1]) recomputation after each simulated update, with no
mismatches.

Complexity

Time: $O(\log n)$ for both update and range_sum (each is one or two
prefix-sum walks). Space: $O(n)$ for the tree array, on top of the
original array.

Edge cases

• left > right: return 0 (an empty range).
• left == 0: skip the left-side prefix subtraction rather than querying
  prefix_sum(-1).
• Negative numbers: handled transparently, since the structure only ever adds
  and subtracts, with no assumption of non-negativity.
• Building from an existing array costs $O(n \log n)$ if done by calling
  _add once per element (as in the constructor above); an $O(n)$ direct
  build is possible but adds complexity that is rarely worth it unless n is
  very large and construction is on a hot path.

Trade-offs & pitfalls

• A segment tree solves the same problem with the same $O(\log n)$ bounds
  and is more general (it directly supports range-minimum, range-maximum,
  and other associative combining functions, not just sums), at the cost of
  roughly twice the constant-factor overhead and a slightly more involved
  implementation. The absorbed range-minimum-query framing does not carry
  over to a Fenwick tree as cleanly as range-sum does: a Fenwick tree's
  update walk relies on values being combinable by simple addition and
  subtraction (to compute a delta and apply it), but minimum has no inverse
  operation, so a Fenwick tree only supports range-minimum queries under
  restricted conditions (for example, values that only increase over time,
  never need pinpoint decreases); a general point-update range-minimum
  requirement should reach for a segment tree instead, not force-fit a
  Fenwick tree.
• The absorbed weighted-random-sampling framing fits well: a Fenwick
  tree over cumulative weights supports "pick index i with probability
  proportional to its weight" by drawing a random value in
  $[0, \text{total weight})$ and walking the tree to find the smallest
  prefix sum exceeding it (a "find by cumulative frequency" walk, itself
  $O(\log n)$), while still allowing individual weights to be updated in
  $O(\log n)$, which a plain cumulative array cannot do without an $O(n)$
  rebuild per weight change.
• The absorbed order-statistics augmented binary search tree (a binary
  search tree, or BST, where each node additionally stores the size of its
  subtree) is a related but different composition: it targets rank-based
  queries over a dynamic set of keys (insert, delete, find the k-th
  smallest key), whereas a Fenwick tree here targets sum queries over a
  fixed-size indexed array. Both are "compose a query capability onto a
  balanced or implicit tree structure so both queries and updates stay
  logarithmic," but they solve different query shapes (rank-of-key versus
  sum-over-range) and are not interchangeable implementations of each other.
• A common implementation bug is mixing up 0-indexed and 1-indexed
  bookkeeping between the public API and the internal tree array; keep the
  1-indexing strictly internal, as done above, so callers never need to
  reason about it.

Direct answer

The tight worst-case bound here is $\Theta(n)$ time and $O(1)$ auxiliary space, not the $\Theta(n \log n)$ that the doubling inner loop might suggest at first glance: for a fixed outer value i, the inner loop runs only about $\log_2(n/i)$ times, and summing that quantity over all i turns out to telescope to a linear total, not a linearithmic one, once carried through carefully. If the outer loop body itself did $O(n)$ work instead of $O(1)$, the total becomes $O(n^2)$, since that O(n) cost is now paid once per outer iteration, n times, dominating the inner loop's own (still linear) total cost.

Structured elaboration

Step 1: count inner-loop executions for a fixed i

Starting from j = i, each inner iteration replaces j with 2j + 1. In closed form, after m iterations, $j_m = 2^m(i+1) - 1$. The loop stops as soon as j >= n, so the number of executions $t(i)$ for a given i is the smallest m with $2^m(i+1) - 1 \ge n$, which gives
$t(i) = \left\lceil \log_2\!\left(\frac{n+1}{i+1}\right) \right\rceil$

Step 2: sum across all outer iterations

$T(n) = \sum_{i=0}^{n-1} t(i) = \Theta\!\left(n + \sum_{i=0}^{n-1} \log_2\!\left(\frac{n}{i+1}\right)\right)$
(the added $n$ term accounts for the ceiling and the outer loop's own O(1) per-iteration bookkeeping). The sum splits cleanly:
$\sum_{i=0}^{n-1} \log_2\!\left(\frac{n}{i+1}\right) = \sum_{k=1}^{n} \left(\log_2 n - \log_2 k\right) = n\log_2 n - \log_2(n!)$

Step 3: this is where the naive intuition goes wrong, and Stirling's approximation resolves it

It is tempting to stop at "a sum of n logarithmic terms is $\Theta(n \log n)$" without simplifying $\log_2(n!)$ further, but $\log_2(n!)$ is itself $\Theta(n \log n)$, and the two $n \log_2 n$ terms above very nearly cancel. Using Stirling's approximation in natural-log form,
$\ln(n!) = n\ln n - n + O(\ln n)$
and converting to base 2 ($\log_2 x = \ln x / \ln 2$):
$\log_2(n!) = n\log_2 n - \frac{n}{\ln 2} + O(\log n)$
Substituting back:
$n\log_2 n - \log_2(n!) = n\log_2 n - \left(n\log_2 n - \frac{n}{\ln 2} + O(\log n)\right) = \frac{n}{\ln 2} + O(\log n) = \Theta(n)$
so the total is
$T(n) = \Theta(n)$
Intuitively: the inner loop runs many times only for the small handful of i near the very start (i close to 0 needs close to $\log_2 n$ iterations), and that count drops off so quickly as i grows that the sum across all i stays linear in n rather than growing to n times the average log factor.

Step 4: verifying the derivation against a direct operation count

Since this is a derived claim about growth rate, it is worth checking numerically before trusting it, by literally counting how many times the inner loop body executes:

import math


def count_inner_iterations(n: int) -> int:
    """
    Counts total O(1)-work executions of the inner while loop across all
    outer iterations, for direct comparison against the analytic bound.
    This counts operations, not wall-clock time.
    """
    total = 0
    for i in range(n):
        j = i
        while j < n:
            total += 1
            j = j * 2 + 1
    return total


if __name__ == "__main__":
    for n in [1_000, 10_000, 100_000, 1_000_000]:
        counted = count_inner_iterations(n)
        predicted = n * math.log2(n) if n > 1 else 0
        ratio = counted / predicted if predicted else float("nan")
        print(f"n={n:>8}  counted={counted:>9}  n*log2(n)={predicted:>12.1f}  ratio={ratio:.3f}")

Running this prints:

n=    1000  counted=     1994  n*log2(n)=      9965.8  ratio=0.200
n=   10000  counted=    19995  n*log2(n)=    132877.1  ratio=0.150
n=  100000  counted=   199994  n*log2(n)=   1660964.0  ratio=0.120
n= 1000000  counted=  1999993  n*log2(n)=  19931568.6  ratio=0.100

The counted total divided by n converges to almost exactly 2 as n grows (1.994, 1.9995, 1.99994, 1.999993), while the counted total divided by $n\log_2 n$ keeps shrinking toward 0 rather than settling at a constant. A quantity that is truly $\Theta(n \log n)$ would have a roughly constant ratio against $n \log_2 n$; a quantity that is truly $\Theta(n)$ has a ratio against $n \log_2 n$ that shrinks toward 0 as n grows, which is exactly the pattern above, confirming the $\Theta(n)$ derivation (the limiting ratio against n itself, about 2, is consistent with $1/\ln 2 \approx 1.44$ plus the O(1) per-outer-iteration bookkeeping folded in).

Complexity

Time: $\Theta(n)$, tight (both upper and lower bound, not just an upper bound). Space: $O(1)$ auxiliary, since only i and j are tracked regardless of n.

Edge cases

• n=0: the outer loop body never runs, so the total work is trivially $\Theta(1)$ (or 0, depending on how the base case is counted), consistent with the formula's leading term.
• i=0 is the single most expensive outer iteration, taking close to $\log_2 n$ steps; i near n-1 costs only 1 step (j starts already close to n).
• If the doubling step were instead j = j * 2 (without the +1), the same derivation applies with a one-off adjustment to the closed form for $j_m$, and the asymptotic result is unchanged.

Trade-offs & pitfalls

The single biggest pitfall on this exact problem is stopping the derivation one step early: summing n terms that are each individually $O(\log n)$ and concluding $O(n \log n)$ overall, without carrying through what $\sum \log_2(n/i)$ actually simplifies to via Stirling's approximation. That intuition is wrong here specifically because the terms in the sum shrink rapidly (as $\log_2(n/i)$ for growing i), rather than staying near their largest value the way they would if the inner loop's iteration count did not depend on i at all. This is exactly the kind of derivation the reproducibility standard requires showing step by step, and confirming numerically, rather than asserting from a memorized shape ("doubling inside a loop looks like $\log n$, so nested with an outer loop must be $n \log n$") that does not actually hold once the per-i cost is summed out. If the outer loop body itself does $O(n)$ work in addition to the inner while loop, that new cost is paid once per outer iteration regardless of the inner loop's behavior, adding $n \times O(n) = O(n^2)$ to the total, which now dominates the inner loop's own $\Theta(n)$ contribution; the overall complexity becomes $O(n^2)$.

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

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.