Shortest equal length for two boards covering every hole

Reframe. Sort the hole positions. Two boards each cover a contiguous interval on the line, so after sorting, the first board covers some prefix a[0..i] and the second covers the remaining suffix a[i+1..n-1]. (If the boards overlapped or interleaved, you could always slide them so one covers a prefix and the other the suffix without making either longer.) A board placed at X with length L covers [X, X+L], so a group of holes with span max - min needs L >= max - min. Both boards share one length, so a split at i needs

L(i) = max(a[i] - a[0], a[n-1] - a[i+1])

and the answer is the smallest L(i) over all splits, raised to at least 1 because the length must be a positive integer.

Brute force. Try every length L from 1 up to a[n-1] - a[0] and greedily check coverage (place board 1 at the first hole, skip everything within L, place board 2 at the next uncovered hole, check it reaches the last). That is O(n · range), which fails when positions go up to 10^9.

Binary search (what many candidates reach first). Feasibility is monotone in L: if length L works, any longer length works. So binary search L over [1, a[n-1] - a[0]] with the O(n) greedy check, or an O(log n) check with bisect. That is O(n log n + n log R) and is accepted.

Optimal after sorting: one linear scan. The closed form above needs no search: walk i from 0 to n-2, compute L(i) and keep the minimum. One pass, O(n) after the O(n log n) sort.

Common trap. "Split at the largest gap between adjacent holes" is not correct. It ignores how the two group spans balance. Holes [0, 4, 5, 9, 10, 14] have three gaps of 4. Splitting at the first one gives spans 0 and 10. Splitting at the middle one gives spans 5 and 5, which is the answer. Another wrong answer, "largest gap plus one", confuses the gap between boards with the board length.

Invariants.

• Sorted order is what makes "one board = a prefix, the other = a suffix" hold.
• An empty group is fine: with n == 1 the second board covers nothing and sits anywhere.
• The answer is never 0, because L must be positive.

from bisect import bisect_right


def min_board_length(holes: list[int]) -> int:
    """Smallest positive L so two boards of length L (each covering
    [X, X+L]) cover every hole. Sort, then try every prefix/suffix split."""
    if not holes:
        return 1
    a = sorted(holes)
    n = len(a)
    if n <= 2:
        return 1  # each board covers one hole (or both sit on one point)
    best = a[-1] - a[0]  # one board covers everything, the other is idle
    for i in range(n - 1):
        left = a[i] - a[0]
        right = a[-1] - a[i + 1]
        best = min(best, max(left, right))
    return max(1, best)


def can_cover(a: list[int], length: int, boards: int = 2) -> bool:
    """Greedy check on sorted holes: start each board at the first
    uncovered hole and jump past everything it covers."""
    i, n = 0, len(a)
    for _ in range(boards):
        if i >= n:
            return True
        i = bisect_right(a, a[i] + length, i)
    return i >= n


def min_board_length_binary_search(holes: list[int], boards: int = 2) -> int:
    """Generalises to k boards: binary search the length."""
    if not holes:
        return 1
    a = sorted(holes)
    lo, hi = 1, max(1, a[-1] - a[0])
    while lo < hi:
        mid = (lo + hi) // 2
        if can_cover(a, mid, boards):
            hi = mid
        else:
            lo = mid + 1
    return lo


if __name__ == "__main__":
    import random

    cases = [
        ([3, 9, 4], 1),
        ([1, 30, 12, 18], 12),
        ([0, 4, 5, 9, 10, 14], 5),
        ([7], 1),
        ([5, 5, 5], 1),
        ([2, 100], 1),
        ([0, 1, 2, 3, 100], 3),
        ([-10, -4, 6, 7], 6),
        ([1, 1_000_000_000], 1),
    ]
    for holes, expected in cases:
        assert min_board_length(holes) == expected, (holes, min_board_length(holes))
        assert min_board_length_binary_search(holes) == expected, holes

    def brute(holes: list[int]) -> int:
        a = sorted(holes)
        length = 1
        while not can_cover(a, length):
            length += 1
        return length

    for _ in range(2000):
        holes = [random.randint(-30, 30) for _ in range(random.randint(1, 9))]
        assert min_board_length(holes) == brute(holes) == min_board_length_binary_search(holes), holes
    print("all tests passed")

• min_board_length: O(n log n) time for the sort, then O(n) for the scan. O(n) extra space for the sorted copy (O(1) if sorting in place is allowed).
• min_board_length_binary_search: O(n log n) sort, then O(log R) iterations with an O(k log n) check each, where R is the coordinate range and k the number of boards. O(n) space.
• If the input is already sorted, the scan alone is O(n) time and O(1) space.

• [3, 9, 4] → 1 (one board on 3 and 4, the other on 9)
• [1, 30, 12, 18] → 12 (sorted [1, 12, 18, 30]; the splits give 18, 12 and 17, so cut between 12 and 18)
• [0, 4, 5, 9, 10, 14] → 5 (the largest-gap trap; split in the middle)
• [7] → 1 (single hole; length must be positive)
• [5, 5, 5] → 1 (all holes at one point)
• [2, 100] → 1 (one board per hole)
• [0, 1, 2, 3, 100] → 3
• [-10, -4, 6, 7] → 6 (negative positions work the same)
• [1, 1000000000] → 1 (huge range, still one board per hole)
• Empty input → 1 by convention (ask the interviewer)
• Randomized: compare against a length-by-length brute force on small inputs

1. k boards instead of two. The prefix/suffix scan no longer works directly. Binary search the length with the greedy check: start a board at the first uncovered hole, jump with bisect_right past a[i] + L, and count boards. O(n log n + log R · k log n). For an exact DP alternative, dp[j][i] = best max span covering the first i holes with j boards, which is O(k n^2) and slower.
2. Boards may have different lengths; minimise total length. Now you want to drop the largest gap: total = (a[n-1] - a[0]) - max_gap. For k boards, drop the k-1 largest gaps. This is the case where the "largest gap" idea is correct, so it is a good check that the candidate understands why it fails for equal lengths.
3. Board covers [X, X+L-1] (L counts cells, not distance). Every span gets +1: the answer becomes best + 1 and no special case for 0 is needed. Ask which convention the interviewer means before coding.
4. Streaming holes / online queries. Keep holes in a sorted container. The optimal split is where the prefix span stops being smaller than the suffix span, so binary search for the crossover (prefix span grows with i, suffix span shrinks) and check its two neighbours: O(log n) per query after O(log n) insertion.
5. Two dimensions (square boards on a grid). Two equal squares covering points: binary search the side and check by trying the four corners of the bounding box for the first square, then testing whether the leftover points fit in a square of that side. Shows whether the candidate can carry the monotonicity argument to a new setting.

Mid-level (L4)

• Sorts first and explains why one board then covers a prefix and the other a suffix.
• Gets a correct O(n log n) solution, by the split scan or by binary search with a greedy check.
• Handles one hole, duplicate positions and the positive-length rule without prompting.

Senior (L5)

• Writes the closed form max(a[i] - a[0], a[n-1] - a[i+1]) and drops the binary search, or explains when each is preferable.
• Rejects the "split at the largest gap" heuristic with a counterexample.
• Clarifies the inclusive-endpoint convention and tests both off-by-one variants.
• Extends to k boards with binary search on the answer.

Staff (L6+)

• States the monotonicity argument that justifies the binary search and the unimodal crossover that makes online queries O(log n).
• Contrasts equal lengths (minimise the max) with free lengths (minimise the sum, drop the largest gaps) and explains why the greedy works in one and not the other.
• Talks through the 2D variant or a randomized brute-force test harness as the way to gain confidence quickly.