Pattern: Heap

[23/Hard] Merge k Sorted Lists

Problem

  • You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

  • Merge all the linked-lists into one sorted linked-list 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 linked-lists 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: Min-heap

  • 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.

  1. We can insert the first element of each array in a Min Heap.
  2. After this, we can take out the smallest (top) element from the heap and add it to the merged list.
  3. After removing the smallest element from the heap, we can insert the next element of the same list into the heap.
  4. We can repeat steps 2 and 3 to populate the merged list in sorted order.
  • Let’s take the Example-1 mentioned above to go through each step of our algorithm:

  • Given lists: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]

  1. After inserting the first number from each list in the heap, the heap will have the following elements:

  1. We’ll take the top number from the heap, insert it into the merged list and add the next number in the heap.

  1. Again, we’ll take the top element of the heap, insert it into the merged list and add the next number to the heap.

  1. 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.

  1. 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 min-heap 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 integer k, return the k 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: Max-heap 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: Min-heap 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 the k-th smallest element in the matrix.

  • Note that it is the k-th smallest element in the sorted order, not the k-th 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 non-decreasing 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)[k-1]
Complexity
  • Time: \(O(n\log{n})\)
  • Space: \(O(1)\)
  • 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 the end for the Binary Search. Here is how our algorithm will work:
    1. Start the Binary Search with start = matrix[0][0] and end = matrix[n-1][n-1].
    2. Find middle of the start and the end. This middle number is NOT necessarily an element in the matrix.
    3. 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)\).
    4. While counting, we can keep track of the “smallest number greater than middle” (let’s call it n1) and at the same time the “biggest number less than or equal to the middle” (let’s call it n2). These two numbers will be used to adjust the “number range” for the Binary Search in the next iteration.
    5. 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.
    6. 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 update end = n1 to search in the lower part of the matrix in the next iteration.
  • 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 of x in array.
Complexity
  • Time: The Binary Search could take \(O(\log{max-min})\) 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{max-min})\)
  • 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{(max-min)})\) for the solution using findCount() or \(O(\log{n}\log{(max-min)})\) for the solution using bisect.bisect() where n is number of rows.
    • \(O(n)\) for findCount() or \(O(\log{n})\) for bisect.bisect()
    • \(O(\log{(max-min)})\) for the while loop
  • Space: \(O(1)\)

Solution: Min-Heap 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)\) times heappop is \(O((k)\log{n})\). Overall, \(O((n+k)\log{n})\)
  • Space: \(O(1)\)

Solution: Min-Heap 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: Min-Heap 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 max-heap
                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 \((n-k)\) times heappushpop 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 non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

  • We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < 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 non-decreasing 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 where points[i] = [x_, y_i] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
  • The distance between two points on the X-Y 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: Min-heap of size \(N\)

  • We insert \(N\) distance measurements corresponding to each input point to a min-heap of size \(N\).
  • Calling heapq.heappop(distance) will pop the smallest item in the heap. So calling heappop() \(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 min-heap 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: Min-heap of size \(K\)

  • We store \(K\) distance measurements corresponding to each input point to a min-heap 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 built-in max heap, we use a min-heap 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) <= K-1:
                heapq.heappush(distance, (-p[0]**2-p[1]**2, p))
            else:
                if -p[0]**2-p[1]**2 > distance[0][0]:
                    heapq.heappop(distance)
                    heapq.heappush(distance, (-p[0]**2-p[1]**2, p)) # or heapq.heapreplace(distance, (-p[0]**2-p[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 2-2 = 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 1-0 = 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.
  • 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:
      1. Get rid of the 3 biggest elements.
      2. Get rid of 2 biggest elements, and the smallest.
      3. Get rid of the biggest element, and 2 smallest.
      4. Get rid of the 3 smallest elements.
    • And in these four choices respectively, the min and the max will be the following:
      1. 1st element, and 4th from the last.
      2. 2nd element, and 3rd from the last.
      3. 3rd element, and 2nd from the last.
      4. 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[n-4] - A[0] == (14-1 = 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[n-3] - A[1] == (15-5 = 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[n-2] - A[2] == (16-6 = 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[n-1] - A[3] == (17-13 = 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})\)