301. Oil wells sit at various y-coordinates; a horizontal pipeline connects to each with vertical spurs. Where should the pipeline run to minimize total spur length?
MediumSearching & selection
Technical
Show model answer
Place it at the median y-coordinate. Moving the line upward by a small amount lengthens the spurs of every well below it and shortens those above it; when more wells are below than above, the total grows. The total is therefore minimized when the counts above and below balance, which is exactly the median (any point between the two middle values works for even counts).
Find the median in O(n) expected time with quickselect, or O(n) worst case with median of medians; no full sort is needed. The mean would minimize the sum of squared distances instead.