I recently worked through a leetcode-style question I found quite interesting. Here's the problem:
Given a sorted array of integers
arr
, determine which element ofarr
is closest to all other elements inarr
. If there are several possible answers, output the smallest one.
The first thing I thought of reading the question was norms. I know that norms are used to determine the distance between vectors. The task does not compare vectors but integers, but the idea is the same - whatever number minimizes the norm is what I'm supposed to return.
Intuitively, I thought of the mean of the list - that's the value with the closest distance to all values in the list.
However, the mean of the list is not necessarily an element of the list - if arr = [1, 2, 4]
, then the mean of arr
is , a number that is not an element of arr
.
Peeking Into The Maths
Searching the internet, I found a great discussion Mathematics StackExchange. User Royi delivers what I believe is a beautiful explanation: You can notate the problem as
where arr
has elements, is the th element in arr
, and is the number we search for.
To find the extrema, I first form the derivative and then determine when the derivative equals 0.
The derivative of the norm is the sign-function , a function that returns if , if , and if .
The extrema is reached when .
In other words, I search an in arr
that divides all values in arr
into two subsets: one consisting of values that are larger than , and the other consisting of values smaller than . If I found an for which both subsets have the same number of elements, I found the I'm looking for.
Writing A Solution
Let's see this in action with some examples.
When arr = [1, 2, 3, 4, 5]
, then I can pick and form a subset of smaller values and a subset of larger values .
However, if arr
contains an even number of elements, e.g. arr = [1, 2, 3, 4]
, then the solution is ambiguous: Neither nor separate the set into subsets of equal size!
As a result, the sums of distances to other values in arr
are equal, and .
With both values being possible answers to the question, the problem statement comes to the rescue:
[...]If there are several possible answers, output the smallest one.
Since arr
is sorted, the solution in Python code is elegantly simple - just find the middle of the list:
def solution(arr):
k = len(arr)
if k % 2 == 1: # odd
mid = k // 2
else: # even
mid = k // 2 - 1 # return smaller element
return arr[mid]
Conclusion
The problem beautifully demonstrates how mathematical thinking can lead to surprisingly simple solutions in programming. What initially appeared to be a complex optimization problem of sums and distances was reduced to finding the middle of a sorted array.