[LeetCode] 253. Meeting Rooms II

 Problem : https://leetcode.com/problems/meeting-rooms-ii/

The minimum required meeting rooms equals to the maximum meeting happen in parallel.

- Solution 1. Use counter to count the meetings happen in parallel.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        for (int i = 0; i < intervals.length; i++) {
            pq.offer(new int[]{intervals[i][0], 1});
            pq.offer(new int[]{intervals[i][1], -1});
        }
        
        int count = 0;
        int result = 0;
        
        while (!pq.isEmpty()) {
            count += pq.poll()[1];
            result = Math.max(result, count);
        }
        
        return result;   
    }
}

- Solution 2. Use priority queue to save the meeting end time. The size of priority queue equals to the number of meetings happen in parallel.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int result = 0;
        
        for (int i = 0; i < intervals.length; i++) {
            while (!pq.isEmpty() && pq.peek() <= intervals[i][0]) {
                // the last meeting has ended.
                // remove it from the queue
                pq.poll();
            }
            
            pq.offer(intervals[i][1]);
            result = Math.max(result, pq.size());
        }
        
        return result;
    }
}

[LeetCode] 1094. Car Pooling

 Problem : https://leetcode.com/problems/car-pooling/

This problem is similar to the meeting room problems.

Use priority queue to process the timestamp when the 'occupied' counter be updated.

When 2 trips start on the same timestamp, it's important to decrease the 'occupied' counter first before increasing the 'occupied' counter.

Time complexity = O ( N * Log N ), N = length of the trips.

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        for ( int i=0; i < trips.length; i++) {
            // increase counter when the trip starts
            pq.offer(new int[]{trips[i][1], trips[i][0]});
            // decrease counter when the trip ends
            pq.offer(new int[]{trips[i][2], -1*trips[i][0]});
        }
        
        int occupied = 0;
        
        while (!pq.isEmpty() && occupied <= capacity) {
            occupied += pq.poll()[1];
        }
        
        return occupied <= capacity;
    }
}

[LeetCode] 973. K Closest Points to Origin

 Problem : https://leetcode.com/problems/k-closest-points-to-origin/

Use max priority queue to find the K closest points.

Time complexity = O( N * Log K ),  N = length of the input array. 

Space complexity = O ( K ),  the priority queue will contain at most K elements.

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // create a max priority queue for saving the K closest points
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> distanceOf(b) - distanceOf(a));
        
        for (int i = 0; i < points.length; i++) {
            if (pq.size() < k) {
                // put the point into the priority queue if the queue size is less than K
                pq.offer(points[i]);
            } else if (distanceOf(pq.peek()) > distanceOf(points[i])) {
                // otherwise, add the new point into priority queue if it is closer than the top point.
                // because it is max priority queue, the top point is the furthest point so far.
                // this condition check is needed to avoid blindly adding new point inito priority queue.
                pq.poll();
                pq.offer(points[i]);
            }
        }
    
        return pq.toArray(new int[0][]);
    }
    
    int distanceOf(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Quick Selection solutioin.

Time complexity = O(N)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        return quickSelect(points, 0, points.length-1, k);
    }
    
    int[][] quickSelect(int[][] points, int left, int right, int k) {       
        while (left < right) {
            int p = partition(points, left, right);
            if (p == k-1) {
                break;
            }
            
            if (p < k-1) {
                // continue to sort the rang [p+1, right]
                left = p + 1;
            } else {
                // continue to sort the range [left, p-1]
                right = p - 1;
            }
        }
        
        return Arrays.copyOf(points, k); 
    }
    
    int partition(int[][] points, int left, int right) {
        // use points[left] as the pivot value
        int pivotDistance = distanceOf(points[left]);
        
        int i = left, j = right + 1; // left and right scan indices
        
        while (true) {
            // scan left, stop when points[i] > pivotDistance or i reaches the array end
            while (distanceOf(points[++i]) < pivotDistance) if (i == right) break;
            // scan right, stop when points[j] < pivotDistance or j reaches the array start
            while (distanceOf(points[--j]) > pivotDistance) if (j == left) break;
            
            // stop scan
            if (i >= j) break;
            
            // exchange i and j
            int[] tmp = points[j];
            points[j] = points[i];
            points[i] = tmp;
        }
        
        // points[j] is the last element on right smaller than points[left]
        // swap 'left' and 'j'
        int[] tmp = points[left];
        points[left] = points[j];
        points[j] = tmp;
        
        return j;
    }
    
    int distanceOf(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Edited on 12/26/2021. Add the quick select solution.

[LeetCode] 1167. Minimum Cost to Connect Sticks

 Problem : https://leetcode.com/problems/minimum-cost-to-connect-sticks/

Greedily connect the 2 shortest sticks in each round. Use heap to find the 2 shortest sticks.

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        result = 0
        
        heapq.heapify(sticks)
        
        while len(sticks) > 1:
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            c = a + b
            result += c
            heapq.heappush(sticks, c)
        
        return result

[LeetCode] 1710. Maximum Units on a Truck

 Problem : https://leetcode.com/problems/maximum-units-on-a-truck/

Greedily take the largest boxes first. Use heap to avoid sort all boxes.

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        heap = [(-m, -n) for n, m in boxTypes]
        heapq.heapify(heap)
        
        result = 0
        
        while truckSize and heap:
            m, n = heapq.heappop(heap)
            m, n = -m, -n
            
            taken = min(truckSize, n)
            result += m * taken
            
            truckSize -= taken
            
        return result

[LeetCode] 1168. Optimize Water Distribution in a Village

 Problem :  https://leetcode.com/problems/optimize-water-distribution-in-a-village/

This problem can be reduced to a Minimum Spanning Tree problem.

We may consider the cost to build well in a village is the cost to reach to this village from any other villages. So we can use greedy algorithm to get the minimum cost to visit all villages.

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        graph = defaultdict(list)
        
        # consider the cost of laying pipe between village 'a' and 'b'
        # as the cast to reach village 'a' from 'b' and vice versa
        for a, b, cost in pipes:
            graph[a].append((b, cost))
            graph[b].append((a, cost))
        
        visited = set()
        
        heap = []
        total = 0
        
        # consider the cost of building well in one village
        # as the cost to reach to this building from any other building
        for i in range(n):
            heapq.heappush(heap, (wells[i], i+1))
        
        # greedily find the the minimum cost to visit all villages.
        while heap and len(visited) < n:
            cost, a = heapq.heappop(heap)
            
            if a not in visited:
                total += cost
                
                visited.add(a)
                
                for b, bcost in graph[a]:
                    heapq.heappush(heap, (bcost, b))
        
        return total

[LeetCode] 871. Minimum Number of Refueling Stops

 Problem: https://leetcode.com/problems/minimum-number-of-refueling-stops/

 Record the amount of gas can get from stations within current maximum distance.

When cannot reach to next station / the target position,  refuel with the maximum amount of gas from the visited gas station to extend the maximum distance can reach and increase refuel count. In the end, check the maximum distance exceeds the target position.

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        maxSoFar = startFuel
        heap = []
        
        i = 0
        refuel = 0
                
        while maxSoFar < target:
            while i < len(stations) and stations[i][0] <= maxSoFar:
                # save gas of station i in heap
                heapq.heappush(heap, -stations[i][1])
                i += 1
            
            if heap:
                # refuel with the maximum amount of gas from visited stations
                maxSoFar += -1 * heapq.heappop(heap)
                refuel += 1
            else:
                break
      
        return refuel if maxSoFar >= target else -1

[LeetCode] 378. Kth Smallest Element in a Sorted Matrix

Problem : https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

This problem equals to merge N sorted lists and find the kth element from the merged list.

Use heap to find small element from N sorted list.

Time complexity = O(K * Log N ), N = len(matrix)

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = []
        
        for i in range(len(matrix)):
            heapq.heappush(heap, (matrix[i][0], i, 0))
        
        result = 0
        for _ in range(k):
            result, y, x = heapq.heappop(heap)
            
            x += 1
            if x < len(matrix[y]):
                heapq.heappush(heap, (matrix[y][x], y, x))
        
        return result

[LeetCode] 373. Find K Pairs with Smallest Sums

 Problem: https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

Assume len(nums1) = M and len(nums2) = N.

nums1 and nums2 can form M sorted list and each list contains N elements.

This problem equals to merge M sorted list and output the first k elements.

The first element of each list is ( nums1[i],  nums2[0] ).  

Because nums1 is sorted list,  ( nums1[i],  nums2[0] ) is the smallest sum on each list.

To find the smallest sum among all list (global smallest sum), we put the smallest sum on each list into the heap.

Then popup the global smallest sum.   Then expend the heap with the next smallest sum of the list from where the current global smallest sum comes.

Time Complexity = O ( K * Log N ).  N = len(nums1)

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        """
                1 ,    2 ,    3
            1  (1,1)  (1,2)  (1,3)
            
            1  (1,1)  (1,2)  (1,3)
            
            2  (2,1)  (2,2)  (2,3)
            
        
        """
        
        if k == 0 or not nums1 or not nums2: return []
        
        heap = []
        result = []
        
        # add the first element of all lines into heap
        for y in range(len(nums1)):
            heapq.heappush(heap, (nums1[y] + nums2[0], y, 0))
        
        while len(result) < k and heap:
            # pop current minimum sum from heap
            _, y, x = heapq.heappop(heap)
            result.append([nums1[y], nums2[x]])
            
            # push next sum combination into heap
            x += 1
            if x < len(nums2):
                heapq.heappush(heap, (nums1[y] + nums2[x], y, x))
        
        return result

[LeetCode] 347. Top K Frequent Elements

 Problem : https://leetcode.com/problems/top-k-frequent-elements/

Use hash map to save count of each elements. 

Then use heap to get first k element .

Time Complexity = O ( N Log k )

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if k > len(nums): return nums
        
        count = Counter(nums)
        
        return heapq.nlargest(k, count.keys(), key=count.get)

[LeetCode] 215. Kth Largest Element in an Array

Problem : https://leetcode.com/problems/kth-largest-element-in-an-array/

A naive solution : 

Time complexity = O ( N Log N )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

Use heap:

Time complexity = O ( N Log K )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        
        while len(nums) > k:
            heapq.heappop(nums)
        
        return nums[0]

In real interview, I assume it expects to be resolved by Quick Sort.

Time complexity = O ( N Log N )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:  
        def swap(left, right):
            nums[left], nums[right] = nums[right], nums[left]
            
        def partition(left, right):
            pivot = left
            
            while left <= right:
                if nums[pivot] <= nums[left]:
                    left += 1
                elif nums[pivot] >= nums[right]:
                    right -= 1
                else:
                    swap(left, right)
                
            swap(left-1, pivot)
            return left-1
                
        def qsort(left, right):
            while left <= right:
                pivot = partition(left, right)
            
                if pivot == k - 1: 
                    return nums[pivot]
                elif pivot > k - 1:
                    right = pivot - 1
                else:
                    left = pivot + 1
        
            return nums[right]
        
        return qsort(0, len(nums)-1)

[LeetCode] 23. Merge k Sorted Lists

Problem : https://leetcode.com/problems/merge-k-sorted-lists/

Must divide and conquer approach to avoid exceeding time limit. 

Time Complexity = O( N log(len(lists) )

Space Complexity: O(1)

 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
    
        def merge(l1, l2):
            if l1 and l2:
                if l1.val < l2.val:
                    l1.next = merge(l1.next, l2)
                    return l1
                else:
                    l2.next = merge(l1, l2.next)
                    return l2
                
            return l1 if l1 else l2
        
        
        def helper(left, right):
            if left == right:
                return None
            
            if right - left == 1:
                return lists[left]
            
            if right - left == 2:
                return merge(lists[left], lists[left+1])
            
            
            mid = left + (right - left) // 2
            return merge(helper(left, mid), helper(mid, right))
    
            
        return helper(0, len(lists))

Use priority queue to merge K sorted list. N = max length of lists

Time Compleixty = O(N * Log K)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        
        while (!pq.isEmpty()) {
            p.next = pq.poll();
            p = p.next;
            if (p.next != null) pq.offer(p.next);
        }

        return dummy.next;
    }
}