Daily LeetCode #3

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/description/?envType=daily-question&envId=2024-10-13

The basic idea is to merge all the lists in num and apply window sliding on it, and it mathes perfectly.

Steps:

• merge all the lists into one list with elements in the form of (num, listIndex), since we need to identify which num is from which list
• do the sort
• start sliding window from left to right
• as we find each element, store it listIndex into hashmap.
• If we have nums from all three lists, the condition is met and we should caculate the range
• as long as the condition is met, we can shrink the window from left, and update hashmap at the same time
• we will get the result after iterating the whole merged list

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // merge all lists into one list with element in form of (num, listIndex)
        List<int[]> merged = new ArrayList<>();
        for(int i = 0; i < nums.size(); i++) {
            for(int j = 0; j < nums.get(i).size(); j++) {
                merged.add(new int[]{nums.get(i).get(j), i});
            }
        }

        // sort in ascending order
        Collections.sort(merged, (a, b) -> a[0] - b[0]);

        int k = nums.size();
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int uniqueCount = 0;
        int[] result = new int[]{0, Integer.MAX_VALUE};
        
        for (int right = 0; right < merged.size(); right++) {
            int listIndex = merged.get(right)[1];
            count.put(listIndex, count.getOrDefault(listIndex, 0) + 1);
            if (count.get(listIndex) == 1) {
                uniqueCount++;
            }
            
            while (uniqueCount == k) {
                // Update result if current range is smaller
                int currentMin = merged.get(left)[0];
                int currentMax = merged.get(right)[0];
                if (currentMax - currentMin < result[1] - result[0] || 
                    (currentMax - currentMin == result[1] - result[0] && currentMin < result[0])) {
                    result[0] = currentMin;
                    result[1] = currentMax;
                }
                
                // Shrink the window
                int leftListIndex = merged.get(left)[1];
                count.put(leftListIndex, count.get(leftListIndex) - 1);
                if (count.get(leftListIndex) == 0) {
                    uniqueCount--;
                }
                left++;
            }
        }
        
        return result;

    }
}

Time Complexity: O(nlogn)

[sort needs O(nlogn); slide window needs O(n)]

Space Complexity: O(n) [use the merged list only]

Safer to use (a, b) -> Integer.compare(a[0] - b[0]) than (a, b) -> a[0] - b[0].