philosyang.com

1509. Minimum Difference Between Largest and Smallest Value in Three Moves | 1653

Easy! /ignorant

 1class Solution:
 2    def minDifference(self, nums: List[int]) -> int:
 3        n = len(nums)
 4        if n <= 4:
 5            return 0
 6
 7        nums.sort()
 8        # print(nums)
 9
10        diff = [-1] * (n - 1)
11        diff_sum = 0
12
13        for i in range(n - 1):
14            diff_cur = nums[i + 1] - nums[i]
15            diff[i] = diff_cur
16            diff_sum += diff_cur
17
18        # print(diff)
19        # print(diff_sum)
20
21        # only 4 possible situations.
22        # [-,-,-,...]
23        # [-,-,...,-]
24        # [-,...,-,-]
25        # [...,-,-,-]
26
27        return diff_sum - max(
28            sum(diff[:3]),
29            sum(diff[-3:]),
30            diff[0] + diff[1] + diff[-1],
31            diff[0] + diff[-1] + diff[-2],
32        )

I made my answer a bit more complex than needed, I actually don’t need the diff array at all:

 1class Solution:
 2    def minDifference(self, nums: List[int]) -> int:
 3        n = len(nums)
 4        if n <= 4:
 5            return 0
 6        nums.sort()
 7        return min(
 8            nums[-1] - nums[3],
 9            nums[-2] - nums[2],
10            nums[-3] - nums[1],
11            nums[-4] - nums[0],
12        )

… and we can actually do this without the need of an nlogn sort:

 1class Solution:
 2    def minDifference(self, nums: List[int]) -> int:
 3        n = len(nums)
 4        if n <= 4:
 5            return 0
 6        mins = heapq.nsmallest(4, nums)   # ascending
 7        maxs = heapq.nlargest(4, nums)    # descending
 8        return min(
 9            maxs[0] - mins[3],
10            maxs[1] - mins[2],
11            maxs[2] - mins[1],
12            maxs[3] - mins[0],
13        )

This is nlogk where k == 4, thus effectively linear.

takeaways:

  1. heapq (nsmallest and nlargest) revision

#Array #Greedy #Sorting #Heap #Python