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 for i, x in enumerate(nums): if x > min: moves += (x-min) elif x < min: moves += i * (min-x) min = x return moves