0

Best single location on a line to minimize total distance

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Best single location on a line to minimize total distance

Companies: Meta

Difficulty: Medium

Problem statement

You are choosing one location on a number line to serve a set of sites. You are given a non-empty integer array nums. Each value is the coordinate of a site (values may repeat and may be negative).

Pick a point x that is one of the values in nums so that the total distance

total = sum(|x - nums[i]| for every index i)

is as small as possible. Return [x, total]. If several values of x give the same minimum total, return the smallest such x.

Implement:

def min_total_distance(nums: list[int]) -> list[int]: ...

Constraints

  • 1 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • The total can exceed 32-bit range.

Example 1

nums = [7, 1, 4]
output: [4, 6]

Choosing 4 costs 3 + 3 + 0 = 6. Choosing 1 costs 9 and choosing 7 costs 9.

Example 2

nums = [-6, 0, 12, 2]
output: [0, 20]

Choosing 0 or 2 both cost 20; return the smaller one, 0.

Aim for better than O(n^2). Be ready to discuss an expected O(n) approach.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

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.

Code

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")

Complexity

  • 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.

Test cases

  • [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.

Follow-ups

  • 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.

Interviewer expectations

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.

Sign in to comment, vote or remix.