Best single location on a line to minimize total distance

We pick one point x from the input and pay |x - p| for every point p.
The cost f(x) = Σ |x - p| is the quantity to minimize.

Brute force. Try every element as x and sum the distances: O(n²).
Say it out loud, then move on.

Key idea: the median. Sort the points and walk x from left to right.
Moving x right by a small step d adds d for every point on its left
and removes d for every point on its right. So f keeps falling while
fewer points sit on the left than on the right, and starts rising once
more sit on the left. It bottoms out at the median. For an even count, any
x between the two middle values is optimal, and both middle values are
input elements. That is why "x must come from the input" costs nothing.

Tie rule: when several elements give the same minimum, return the smallest.
With the points sorted as a, that is the lower median a[(n - 1) // 2].

Computing the total. Once x is fixed, one pass gives the total. With
sorted input there is a cleaner form that avoids x entirely: pair the
outermost points, Σ (a[n-1-i] - a[i]) for i < n // 2. Every pair
(a[i], a[n-1-i]) contributes its width no matter where x sits between
them, and the median sits inside every pair.

Optimal. Sorting gives O(n log n), which is usually fine. For O(n)
expected, find the lower median with quickselect (random pivot, three-way
partition so duplicates do not degrade it), then sum distances in one pass.

Invariants:

• The answer x is always an input element (the lower median).
• f is convex and piecewise linear; its slope at x is
  (#points < x) - (#points > x), so the minimum is where the slope crosses zero.

import random
from typing import List


def min_total_distance(nums: List[int]) -> List[int]:
    """Return [x, total] where x in nums minimizes sum |x - p|.

    Ties go to the smallest x (the lower median). O(n log n).
    """
    if not nums:
        raise ValueError("nums must not be empty")
    a = sorted(nums)
    n = len(a)
    x = a[(n - 1) // 2]
    total = sum(a[n - 1 - i] - a[i] for i in range(n // 2))
    return [x, total]


def kth_smallest(nums: List[int], k: int) -> int:
    """Quickselect: k-th smallest (0-based), expected O(n)."""
    items = list(nums)
    while True:
        pivot = random.choice(items)
        lows = [v for v in items if v < pivot]
        equal = sum(1 for v in items if v == pivot)
        if k < len(lows):
            items = lows
        elif k < len(lows) + equal:
            return pivot
        else:
            k -= len(lows) + equal
            items = [v for v in items if v > pivot]


def min_total_distance_linear(nums: List[int]) -> List[int]:
    """Same answer in expected O(n) time without sorting."""
    if not nums:
        raise ValueError("nums must not be empty")
    x = kth_smallest(nums, (len(nums) - 1) // 2)
    return [x, sum(abs(x - p) for p in nums)]


def brute_force(nums: List[int]) -> List[int]:
    best = None
    for x in nums:
        cost = sum(abs(x - p) for p in nums)
        if best is None or (cost, x) < (best[1], best[0]):
            best = [x, cost]
    return best


if __name__ == "__main__":
    assert min_total_distance([5]) == [5, 0]
    assert min_total_distance([7, 1, 4]) == [4, 6]
    assert min_total_distance([10, 2]) == [2, 8]
    assert min_total_distance([3, 3, 3, 9]) == [3, 6]
    assert min_total_distance([-6, 0, 12, 2]) == [0, 20]
    for _ in range(500):
        arr = [random.randint(-50, 50) for _ in range(random.randint(1, 12))]
        expected = brute_force(arr)
        assert min_total_distance(arr) == expected, arr
        assert min_total_distance_linear(arr) == expected, arr
    print("all tests pass")

• Sorting version: O(n log n) time, O(n) space for the sorted copy (O(1)
  extra if sorting in place is allowed).
• Quickselect version: O(n) expected time, O(n²) worst case with unlucky
  pivots (median-of-medians makes it O(n) worst case, rarely worth coding);
  O(n) space as written, O(1) extra with in-place partitioning.
• Brute force: O(n²) time, O(1) space.

• [5] → [5, 0] (single point).
• [7, 1, 4] → [4, 6] (odd count: median 4, cost 3 + 3).
• [10, 2] → [2, 8] (even count: 2 and 10 both cost 8; tie goes to the smaller).
• [3, 3, 3, 9] → [3, 6] (duplicates).
• [-6, 0, 12, 2] → [0, 20] (negatives; 0 and 2 both cost 20).
• [1, 1000000000] → [1, 999999999] (large values; Python ints do not overflow, but call out 64-bit sums in Java/C++).
• Randomized check against the O(n²) brute force on small arrays.

• Weighted sites (each point has a shipment volume w): the answer is
  the weighted median. Sort by coordinate and take the first point where
  the running weight reaches half the total. O(n log n).
• Any real x, not only input points: the answer set is the whole
  interval between the two middle values; the minimum cost is unchanged.
  Ask which point the interviewer wants returned.
• 2D grid with Manhattan distance (LeetCode 296): the cost splits into
  rows and columns, so take the median row and median column separately.
  If x must be one of the given points, the two medians may not form an
  input point; then evaluate candidates fast with prefix sums over sorted
  rows and columns, O(n log n).
• Return the cost for every candidate or answer many queries: sort,
  build prefix sums, then cost(x) = x*L - sumL + sumR - x*R per query in
  O(log n) with binary search.
• Streaming points: keep two heaps (max-heap low half, min-heap high
  half) plus each heap's sum; the median and the total cost are available
  in O(1) after each O(log n) insert.
• k warehouses: each point ships to its nearest warehouse. Groups are
  contiguous in sorted order, so DP over split points with a median cost
  per segment (from prefix sums): O(k·n²), or faster with divide-and-conquer
  optimization.

Mid-level (L4)

• States the brute force, then argues why the median minimizes the sum.
• Handles the even-count tie and returns an input element.
• Sorting solution, correct and tested on small and duplicate cases.

Senior (L5)

• Gives the slope argument (left count vs right count) crisply, not just "median is known".
• Mentions quickselect for expected O(n) and handles duplicates in partitioning.
• Solves weighted and prefix-sum query follow-ups without prompting on the structure.

Staff (L6+)

• Generalizes cleanly: weighted median, 2D separability, and when separability breaks (input-point constraint in 2D).
• Discusses the streaming two-heap design and the k-warehouse DP with its cost.
• Raises practical concerns: overflow in sums, worst-case quickselect, choosing sort vs select for the real input size.