Distilled • LeetCode • Heap
 Pattern: Heap
 [23/Hard] Merge k Sorted Lists
 [347/Medium] Top K Frequent Elements
 [378/Medium] Kth Smallest Element in a Sorted Matrix
 [632/Hard] Smallest Range Covering Elements from K Lists
 [973/Medium] K Closest Points to Origin
 [1509/Medium] Minimum Difference Between Largest and Smallest Value in Three Moves
Pattern: Heap
[23/Hard] Merge k Sorted Lists
Problem

You are given an array of k linkedlists lists, each linkedlist is sorted in ascending order.

Merge all the linkedlists into one sorted linkedlist and return it.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linkedlists are:
[
1>4>5,
1>3>4,
2>6
]
merging them into one sorted list:
1>1>2>3>4>4>5>6
 Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
 Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.
 See problem on LeetCode.
Solution: Minheap

A brute force solution could be to add all elements of the given ‘K’ lists to one list and sort it. If there are a total of ‘N’ elements in all the input lists, then the brute force solution will have a time complexity of \(O(N*\log{N})\) as we will need to sort the merged list. Can we do better than this? How can we utilize the fact that the input lists are individually sorted?

If we have to find the smallest element of all the input lists, we have to compare only the smallest (i.e. the first) element of all the lists. Once we have the smallest element, we can put it in the merged list. Following a similar pattern, we can then find the next smallest element of all the lists to add it to the merged list.

The best data structure that comes to mind to find the smallest number among a set of ‘K’ numbers is a Heap. Let’s see how can we use a heap to find a better algorithm.
 We can insert the first element of each array in a Min Heap.
 After this, we can take out the smallest (top) element from the heap and add it to the merged list.
 After removing the smallest element from the heap, we can insert the next element of the same list into the heap.
 We can repeat steps 2 and 3 to populate the merged list in sorted order.

Let’s take the Example1 mentioned above to go through each step of our algorithm:

Given lists:
L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
 After inserting the first number from each list in the heap, the heap will have the following elements:
 We’ll take the top number from the heap, insert it into the merged list and add the next number in the heap.
 Again, we’ll take the top element of the heap, insert it into the merged list and add the next number to the heap.
 Repeating the above step, take the top element of the heap, insert it into the merged list and add the next number to the heap. As there are two 3s in the heap, we can pick anyone but we need to take the next element from the corresponding list to insert in the heap.
 We’ll repeat the above step to populate our merged array.
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) > Optional[ListNode]:
ListNode.__lt__ = lambda self, other: self.val < other.val
h = []
head = tail = ListNode(0)
for i in lists:
if i:
heapq.heappush(h, (i.val, i))
while h:
node = heapq.heappop(h)[1]
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(h, (node.next.val, node.next))
return head.next
Complexity
 Time: Since we’ll be going through all the elements of all arrays and will be removing/adding one element to the heap in each step, the time complexity of the above algorithm will be \(O(N*logK)\), where \(N\) is the total number of elements in all the \(K\) input arrays.
 Space: The space complexity will be \(O(K)\) because, at any time, our minheap will be storing one number from all the \(K\) input arrays.
[347/Medium] Top K Frequent Elements
Problem

Given an integer array
nums
and an integerk
, return thek
most frequent elements. You may return the answer in any order. 
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
 Example 2:
Input: nums = [1], k = 1
Output: [1]
 Constraints:
1 <= nums.length <= 105
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
 See problem on LeetCode.
Solution: Reverse sort counter output by frequency values
class Solution:
def topKFrequent(self, nums: List[int], k: int) > List[int]:
c = Counter(nums)
return sorted(c, key=lambda x: c[x], reverse=True)[:k]
 Same approach; much verbose:
class Solution:
def topKFrequent(self, nums: List[int], k: int) > List[int]:
frq = defaultdict(list)
for key, cnt in Counter(nums).items():
frq[cnt].append(key)
res = []
for times in reversed(range(len(nums) + 1)):
res.extend(frq[times])
if len(res) >= k: return res[:k]
return res[:k]
Complexity
 Time: \(O(n)\)
 Space: \(O(n)\)
Solution: Maxheap of size \(k\)
 Build a frequency dictionary  invert the sign of the frequency (negative frequency serves as the priority key for the heap later).
 Push all
(negative frequency, item)
pairs into the heap.  Pop \(k\) items from heap and append to a result list.
 Return list.
class Solution:
def topKFrequent(self, nums: List[int], k: int) > List[int]:
if not nums:
return []
if len(nums) == 1:
return [nums[0]]
# first find freq  freq dict
d = {}
for num in nums:
if num in d:
d[num] = 1 # reverse the sign on the freq for the heap's sake
else:
d[num] = 1
h = []
from heapq import heappush, heappop
for key in d:
heappush(h, (d[key], key)) # push (freq, item): O(log(k))
res = []
count = 0
while count < k:
freq, item = heappop(h) # O(log(k))
res.append(item)
count += 1
return res
Complexity
 Time: \(O(n\log{n})\)
 Space: \(O(n)\)
Solution: Minheap of size \(n\)
 Build a frequency dictionary (freq is positive).
 Build a heap.
 Make sure heap contains \(k\) items at maximum by popping out the items with least frequency as you push to heap.
 The time complexity of adding an element in a heap is \(O(\log{k})\) and we do it \(n\) times that means \(O(n\log{k})\) time complexity for this step.
 Heap now contains \(k\) items (the desired output basically).
 Pop and append to the output list  \(O(k\log{k})\).
 Return list.
class Solution:
def topKFrequent(self, nums: List[int], k: int) > List[int]:
if len(nums) == 1:
return [nums[0]]
# freq dict
d = {}
for num in nums:
if num in d:
d[num] += 1
else:
d[num] = 1
# go over the n input items and
# insert k items into heap: O(n log(k))
h = []
from heapq import heappush, heappop
for key in d: # O(n)
heappush(h, (d[key], key)) # push (freq, item): O(log(k))
if len(h) > k:
heappop(h)
res = []
while h: # O(k)
freq, item = heappop(h) # O(log(k))
res.append(item)
return res
Complexity
 Time: \(O(n\log{k})\)
 Space: \(O(n)\)
[378/Medium] Kth Smallest Element in a Sorted Matrix

Given an
n x n
matrix
where each of the rows and columns is sorted in ascending order, return thekth
smallest element in the matrix. 
Note that it is the
kth
smallest element in the sorted order, not thekth
distinct element. 
You must find a solution with a memory complexity better than
O(n^2)
. 
Example 1:
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
Example 2:
Input: matrix = [[5]], k = 1
Output: 5
 Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 300
109 <= matrix[i][j] <= 109
All the rows and columns of matrix are guaranteed to be sorted in nondecreasing order.
1 <= k <= n2
 See problem on LeetCode.
Solution: Sort
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) > int:
res = []
for r in matrix:
res += r
return sorted(res)[k1]
Complexity
 Time: \(O(n\log{n})\)
 Space: \(O(1)\)
Solution: Binary search

Since each row and column of the matrix is sorted, is it possible to use Binary Search to find the Kth smallest number?

The biggest problem to use Binary Search, in this case, is that we don’t have a straightforward sorted array, instead, we have a matrix. As we remember, in Binary Search, we calculate the middle index of the search space (‘1’ to ‘N’) and see if our required number is pointed out by the middle index; if not we either search in the lower half or the upper half. In a sorted matrix, we can’t really find a middle. Even if we do consider some index as middle, it is not straightforward to find the search space containing numbers bigger or smaller than the number pointed out by the middle index.
 An alternative could be to apply the Binary Search on the “number range” instead of the “index range”. As we know that the smallest number of our matrix is at the top left corner and the biggest number is at the bottom right corner. These two numbers can represent the “range” i.e., the
start
and theend
for the Binary Search. Here is how our algorithm will work: Start the Binary Search with
start = matrix[0][0]
andend = matrix[n1][n1]
.  Find middle of the
start
and theend
. Thismiddle
number is NOT necessarily an element in the matrix.  Count all the numbers smaller than or equal to middle in the matrix. As the matrix is sorted, we can do this in \(O(N)\).
 While counting, we can keep track of the “smallest number greater than
middle
” (let’s call itn1
) and at the same time the “biggest number less than or equal to the middle” (let’s call itn2
). These two numbers will be used to adjust the “number range” for the Binary Search in the next iteration.  If the count is equal to ‘K’,
n2
will be our required number as it is the “biggest number less than or equal to the middle”, and is definitely present in the matrix.  If the count is less than ‘K’, we can update
start = n2
to search in the higher part of the matrix and if the count is greater than ‘K’, we can updateend = n1
to search in the lower part of the matrix in the next iteration.
 Start the Binary Search with
 Here is a visual representation of the algorithm:
class Solution(object):
def kthSmallest(self, matrix: List[List[int]], k: int) > int:
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
def count_less_equal(matrix, smaller, mid, larger):
count, n = 0, len(matrix)
row, col = n  1, 0
while row >= 0 and col < n:
if matrix[row][col] > mid:
# as matrix[row][col] is bigger than the mid, let's keep track of the
# smallest number greater than the mid
larger = min(larger, matrix[row][col])
row = 1
else:
# as matrix[row][col] is less than or equal to the mid, let's keep track of the
# biggest number less than or equal to the mid
smaller = max(smaller, matrix[row][col])
count += row + 1
col += 1
return count, smaller, larger
l, r = matrix[0][0], matrix[1][1]
while l < r:
mid = (l + r) // 2 # or l + (r  l) // 2
# calculate how many numbers are on the left of middle number
count, smaller, larger = count_less_equal(matrix, mid, l, r)
# or order = sum(bisect.bisect(row, m) for row in matrix) < k:
if count >= k:
r = smaller # search lower
else:
l = larger # search higher
return l
 Note that
bisect.bisect(array, x)
returns an insertion point which comes after (to the right of) any existing entries ofx
in array.
Complexity
 Time: The Binary Search could take \(O(\log{maxmin})\) iterations where \(max\) is the largest and \(min\) is the smallest element in the matrix and in each iteration we take \(O(n)\) for counting, therefore, the overall time complexity of the algorithm will be \(O(n*\log{maxmin})\)
 Space: \(O(1)\)
Solution: Binary search (cleaner)
 Same approach; cleaner:
class Solution(object):
def kthSmallest(self, matrix: List[List[int]], k: int) > int:
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
def findCount(matrix, val):
count = 0
for row in matrix:
for col in row:
if col <= val: count += 1
return count
l, r = matrix[0][0], matrix[1][1]
while l < r:
mid = (l + r) // 2 # or l + (r  l) // 2
# calculate how many numbers are on the left of middle number
count = findCount(matrix, mid)
# or count = sum(bisect.bisect(row, m) for row in matrix) < k:
if count >= k:
r = mid # search lower
else:
l = mid + 1 # search higher
return l
Complexity
 Time: \(O(n\log{(maxmin)})\) for the solution using
findCount()
or \(O(\log{n}\log{(maxmin)})\) for the solution usingbisect.bisect()
wheren
is number of rows. \(O(n)\) for
findCount()
or \(O(\log{n})\) forbisect.bisect()
 \(O(\log{(maxmin)})\) for the
while
loop
 \(O(n)\) for
 Space: \(O(1)\)
Solution: MinHeap of size \(n\)
from heapq import heappush, heappop
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) > int:
a, res = [], 1
for r in matrix:
for e in r:
heappush(a, e)
for _ in range(k):
res = heappop(a)
return res
Complexity
 Time: \(n\) times
heappush
is \(O(n\log{n})\) and \((k)\) timesheappop
is \(O((k)\log{n})\). Overall, \(O((n+k)\log{n})\)  Space: \(O(1)\)
Solution: MinHeap of size \(n\) with heapify
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
import heapq
vals = [val for row in matrix for val in row]
heapq.heapify(vals)
for _ in range(k):
ans = heapq.heappop(vals)
return ans
Complexity
 Time: heapify is \(O(n)\) and \(k\) times pop is \(O(k \log{n})\) so overall time complexity is: \(O(n + k\log{n})\)
 Space: \(O(1)\)
Solution: MinHeap of size \(k\)
 Same approach; better time complexity:
import heapq
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) > int:
if not matrix or not matrix[0]:
return 1
heap = []
for row in range(len(matrix)):
for col in range(len(matrix[0])):
# Negate element to emulate a maxheap
nextVal = matrix[row][col]
# If the length of your heap is less than k, push elements
if len(heap) < k:
heapq.heappush(heap, nextVal)
# If your heap has k elements and if the current element is
# greater than the max element so far, pop out the current max
# and add the new one in
elif nextVal > heap[0]:
heapq.heappushpop(heap, nextVal)
return heap[0]
Complexity
 Time: \(k\) times
heappush
is \(O(k\log{n})\) and \((nk)\) timesheappushpop
is \(O((n  k)\log{n})\). Overall, \(O(n\log{n})\)  Space: \(O(1)\)
[632/Hard] Smallest Range Covering Elements from K Lists
Problem

You have
k
lists of sorted integers in nondecreasing order. Find the smallest range that includes at least one number from each of thek
lists. 
We define the range
[a, b]
is smaller than range[c, d]
ifb  a < d  c
ora < c if b  a
==d  c
. 
Example 1:
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
 Example 2:
Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
 Constraints:
nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
105 <= nums[i][j] <= 105
nums[i] is sorted in nondecreasing order.
 See problem on LeetCode.
Solution
import heapq
class Solution:
def smallestRange(self, nums: List[List[int]]) > List[int]:
result = []
hq = []
high = sys.maxsize
for i in range(len(nums)):
heapq.heappush(hq, (nums[i][0], i, 0))
high = max(high, nums[i][0])
result = [hq[0][0], high]
while True:
num , listIndex, numIndex = heapq.heappop(hq)
if numIndex == len(nums[listIndex])  1:
break;
nextNum = nums[listIndex][numIndex + 1]
heapq.heappush(hq, (nextNum, listIndex, numIndex + 1))
high = max(high, nextNum)
if high  hq[0][0] < result[1]  result[0]:
result = [hq[0][0], high]
return result
Complexity
 Time: \(O(n\log{k})\)
 Space: \(O(k)\)
[973/Medium] K Closest Points to Origin
Problem
 Given an array of
points
wherepoints[i] = [x_, y_i]
represents a point on the XY plane and an integerk
, return thek
closest points to the origin(0, 0)
.  The distance between two points on the XY plane is the Euclidean distance (i.e.,
sqrt((x1  x2)^2 + (y1  y2)^2
).  You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
 Example 1:
Input: points = [[1,3],[2,2]], k = 1
Output: [[2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[2,2]].
 Example 2:
Input: points = [[3,3],[5,1],[2,4]], k = 2
Output: [[3,3],[2,4]]
Explanation: The answer [[2,4],[3,3]] would also be accepted.
 Constraints:
1 <= k <= points.length <= 104
104 < x_i, y_i < 104
 See problem on LeetCode.
Solution: Sort
 Sort the list according to the distance to origin. However, note that this does more than the question has asked – we sorted all the input points, while the question only ask for top \(K\). To improve time complexity, we need to think about how to get we ask without extra effort. This is where the heap data structure comes in.
class Solution:
def kClosest(self, points: List[List[int]], K: int) > List[List[int]]:
points.sort(key = lambda P: P[0]**2+P[1]**2)
return points[:K]
Complexity
 Time: \(O(N \log{N})\)
Solution: Minheap of size \(N\)
 We insert \(N\) distance measurements corresponding to each input point to a minheap of size \(N\).
 Calling
heapq.heappop(distance)
will pop the smallest item in the heap. So callingheappop()
\(K\) times will be yield the result.
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) > List[List[int]]:
distance = []
for i in points:
heapq.heappush(distance, (i[0]**2 + i[1]**2, i))
K_points = []
for i in range(K):
K_points.append(heapq.heappop(distance)[1])
return K_points
 The problem with the above approach is that we stored all the \(N\) elements so the time complexity is \(O(N\log{N})\). Since we only need the top \(k\) smallest elements, we don’t care about the order of other elements.
 So if we keep a minheap of size \(k\), use the
heap[0]
element as threshold, iterate through the array, only the \(K\) elements will be added to the heap.
Complexity
 Time: Inserting an item to a heap of size \(n\) would take \(O(\log{n})\) time. And we do this for each of the \(n\) items/points. So runtime is \(O(n * \log{n})\) where \(n\) is the number of input points.
 Space: \(O(n)\) for our heap.
Solution: Minheap of size \(K\)
 We store \(K\) distance measurements corresponding to each input point to a minheap of size \(K\).
 If inserting an item makes the heap size larger than \(K\), then we immediately pop an item after inserting (
heappushpop()
).
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) > List[List[int]]:
heap = []
for (x, y) in points:
dist = (x*x + y*y)
if len(heap) == K:
heapq.heappushpop(heap, (dist, x, y))
else:
heapq.heappush(heap, (dist, x, y))
return [(x,y) for (dist, x, y) in heap]
Complexity
 Time: Inserting an item to a heap of size \(K\) would take \(O(\log{K})\) time. And we do this for each of the \(n\) items/points. So runtime is \(O(n * \log{K})\) where \(n\) is the number of input points.
 Space: \(O(K)\) for our heap.
Solution: Max heap of size \(K\)
 Since Python doesn’t have a builtin max heap, we use a minheap to achieve maximum heap’s by storing inverted (negated) versions of the input points.
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) > List[List[int]]:
distance = []
for p in points:
if len(distance) <= K1:
heapq.heappush(distance, (p[0]**2p[1]**2, p))
else:
if p[0]**2p[1]**2 > distance[0][0]:
heapq.heappop(distance)
heapq.heappush(distance, (p[0]**2p[1]**2, p)) # or heapq.heapreplace(distance, (p[0]**2p[1]**2, p))
res = []
for i in range(K):
res.append(heapq.heappop(distance)[1])
return res
Complexity
 Time:
heapq
is a binary heap, with \(O(\log{n})\) push and \(O(\log{n})\) pop. \(n\) is the size of the minimum heap. In this case, \(n = K\). So the runtime is \(O(N * \log{K})\) where \(N\) is the length of points.  Space: \(O(K)\) for our heap.
Solution: Max heap of size \(N\) (Simpler)
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) > List[List[int]]:
heap = []
for x, y in points:
d = (x*x + y*y)
heapq.heappush(heap, (d, x, y))
if len(heap) > K:
heapq.heappop(heap)
return [[x, y] for _, x, y in heap]
Complexity
 Time:
heapq
is a binary heap, with \(O(\log{n})\) push and \(O(\log{n})\) pop. \(n\) is the size of the minimum heap. In this case, \(n = K\). So the runtime is \(O(N * \log{K})\) where \(N\) is the length of points.  Space: \(O(K)\) for our heap.
[1509/Medium] Minimum Difference Between Largest and Smallest Value in Three Moves
Problem

You are given an integer array nums. In one move, you can choose one element of nums and change it by any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

Example 1:
Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 22 = 0.
 Example 2:
Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1].
The difference between the maximum and minimum is 10 = 1.
 Constraints:
1 <= nums.length <= 105
109 <= nums[i] <= 109
 See problem on LeetCode.
Solution: Sort, then look for the minimum difference among the first three and last three elements
 Intuition:
 If we can do 0 move, return
max(A)  min(A)
.  If we can do 1 move, return
min(the second max(A)  min(A), the max(A)  second min(A))
since we’re looking to minimize the difference between the maximum and minimum element by either reducing the maximum element to the match the minimum element or increasing the minimum element to match the maximum element. and so on.
 If we can do 0 move, return
 Explanation:
 If there are 4 or less elements in it, we’re going to be left with 1 element at most, making the difference b/w min and max 0.
 If there are more elements, then we have one of these four choices:
 Get rid of the 3 biggest elements.
 Get rid of 2 biggest elements, and the smallest.
 Get rid of the biggest element, and 2 smallest.
 Get rid of the 3 smallest elements.
 And in these four choices respectively, the min and the max will be the following:
 1st element, and 4th from the last.
 2nd element, and 3rd from the last.
 3rd element, and 2nd from the last.
 4th element, and (1st from) the last.
 In other words, we simply need to take the pairwise difference b/w the 4 smallest elements in the array, and the 4 largest elements in the array (in reverse order). Sorting the entire array for this is inefficient. A more efficient way is provided by the
heapq
module.  And of course, we can use this for any number of moves, not just 3. At a large number of moves though, it would be faster to sort the entire array.

Example:
A = [1,5,6,13,14,15,16,17] (note that the array is sorted) n = 8 Case 1: kill 3 biggest elements All three biggest elements can be replaced with 14 [1,5,6,13,14,15,16,17] > [1,5,6,13,14,14,14,14] == can be written as A[n4]  A[0] == (141 = 13) Case 2: kill 2 biggest elements + 1 smallest elements [1,5,6,13,14,15,16,17] > [5,5,6,13,14,15,15,15] == can be written as A[n3]  A[1] == (155 = 10) Case 3: kill 1 biggest elements + 2 smallest elements [1,5,6,13,14,15,16,17] > [6,6,6,13,14,15,16,16] == can be written as A[n2]  A[2] == (166 = 10) Case 4: kill 3 smallest elements [1,5,6,13,14,15,16,17] > [13,13,13,13,14,15,16,17] == can be written as A[n1]  A[3] == (1713 = 4) Answer is the minimum of all these cases!
class Solution:
def minDifference(self, nums: List[int]) > int:
nums.sort()
return 0 if len(nums) <= 4 else min(b  a for a, b in zip(nums[:4], nums[4:]))
Complexity
 Time: \(O(n\log{n})\)
 Space: \(O(log{n})\)
Solution: Partial Sorting using a Heap, then look for the minimum difference among the first three and last three elements
class Solution:
def minDifference(self, nums: List[int]) > int:
# return 0 if len(nums) <= 4 else min(a  b for a, b in zip(heapq.nlargest(4, nums), reversed(heapq.nsmallest(4, nums))))
return 0 if len(nums) <= 4 else min(a  b for a, b in zip(heapq.nlargest(4, nums), heapq.nsmallest(4, nums)[::1]))
Complexity
 Time: \(O(n\log{k})\)
 Space: \(O(log{k})\)