Python accepted O(n) with rough proof


  • 0

    I just guessed it should be the median point but I don't have a formal proof yet.

    Convert the problem to a math problem:
    f(x) = |x - x_1| +|x - x_2| + |x - x_3| + ... + |x - x_n|
    We know |x - a| + |x - b| >= |a - b| from high school math
    f(x) > = |x_1 - xn| + |x_2 - x_n-1| + ... + |x_k - x_k+1|
    Assume x_m = median,
    Then x_i < x_m when i < m and x_i >= x_m when i >= m.
    f(x_m) = (x_m - x_1) + (x_m - x_2) + ... + (x_m - x_m+1) - (x_m+2 - xm+3) - ... - (x_n-1 - x_n)
    f(x_m) = |x_1 - xn| + |x_2 - x_n-1| + ... + |x_k - x_k+1|
    Then when x = x_m, f(x) reaches minimum value.

    class Solution(object):
        def minMoves2(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums.sort()
            mid = nums[len(nums) / 2]
            return sum(abs(num - mid) for num in nums)
    

  • 0

    I guess you can argue that the built-in sorting method is optimized to perform closer to average O(n), but I still think in an interview context a built-in sorting method would be considered resorting to a O(nlogn) complexity on average.


  • 0

    @Ellest My bad. It's O(nlogn). I just don't want to implement another quickselect here.


  • 0

    @jedihy Yeah that's cool. I just wasn't sure if you were going for the argument that builtin sorts are more practical than O(nlogn) in practice.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.