Best single location on a line to minimize total distance

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.