Why is my one-pass solution slower than the two-pass?


  • 0
    C

    When I thought of the idea of decreasing the largest number
    I wrote down this

    def minMoves(self, nums):
        moves = 0
        min = min(nums)
        for x in nums:
            moves += (x-min)
        return moves
    

    This is a two-pass O(n) solution, it can beat about 50% on average.
    Then I optimized it to one-pass by removing the sort, but it only beats 40%...

    def minMoves(self, nums):
        moves = 0
        min = nums[0]
        for i, x in enumerate(nums):
            if x > min:
                moves += (x-min)
            elif x < min:
                moves += i * (min-x)
                min = x
            return moves
    

Log in to reply
 

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