Python bucket sort TLE ?


  • 1
    Y

    How can this be improved? Seems to be O(n^2) and accepted in other languages.

        def smallestDistancePair(self, nums, k):
            diffs = [0 for _ in range(1000000)]
            
            for i, num in enumerate(nums):
                for num2 in nums[i + 1:]:
                    diffs[abs(num - num2)] += 1
                    
            for i, diff in enumerate(diffs):
                k -= diff
                if k <= 0:
                    return i
    

Log in to reply
 

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