Smallest Range Covering Elements from K Lists

class Solution {
public:
    vector<int> findSmallestRange(vector<vector<int>>& numLists) {
        vector<pair<int, int>> elements;
    
        // Store all numbers with their originating list indices
        for (int index = 0; index < numLists.size(); index++) {
            for (int element : numLists[index]) {
                elements.push_back({element, index});
            }
        }
    
        // Sort all elements
        sort(elements.begin(), elements.end());
    
        // Variables to find the minimal range
        unordered_map<int, int> countMap;
        int minRangeStart = 0, minRangeEnd = INT_MAX;
        int start = 0, covered = 0;
    
        for (int end = 0; end < elements.size(); end++) {
            countMap[elements[end].second]++;
            if (countMap[elements[end].second] == 1) covered++;
    
            // Shrink the window if all lists are covered
            while (covered == numLists.size()) {
                int currentRange = elements[end].first - elements[start].first;
                if (currentRange < minRangeEnd - minRangeStart) {
                    minRangeStart = elements[start].first;
                    minRangeEnd = elements[end].first;
                }
    
                countMap[elements[start].second]--;
                if (countMap[elements[start].second] == 0) covered--;
                start++;
            }
        }
    
        return {minRangeStart, minRangeEnd};
    }
};

This C++ program is designed to solve the problem of finding the smallest range that includes at least one number from each of a given set of lists. The approach utilizes efficient data structures and algorithms, emphasizing clarity with each step involved in the solution.

• First, the program defines a vector of pairs to store elements along with the index of the list they come from. This helps in identifying the source list of each element during later stages of processing.

• The program then iterates over each list and inserts each element and its corresponding list index into the vector of pairs. This flattening of lists into a single vector forms the preprocessing stage for future operations.

• Once all elements are stored, they are sorted. Sorting is crucial as it aids in the subsequent sliding window approach, allowing the program to effectively scan through the elements to find the minimum range.

• Post sorting, the program uses a sliding window technique assisted by an unordered map (countMap) for counting occurrences of list indices within the current window. The use of unordered_map ensures efficient lookups, insertions, and deletions.

• As the end pointer of the sliding window expands, the program continuously checks if the current window covers elements from all lists using the covered counter. If it's true, attempts to contract the window from the left are made to minimize the range while still covering all lists.

• If a valid candidate for a minimal range is found (covering all lists), it updates the minimal range if it's smaller than any previously found ranges.

• When the condition fails (i.e., not all lists are covered anymore), the left pointer of the window (start) is incremented, and the process repeats.

The entire operation ensures that the final smallest range containing at least one element from each list is returned efficiently. This solution effectively balances between preprocessing (sorting and mapping) and optimized searching using the sliding window technique, suitable for problems involving ranges over multiple lists.

class Solution {
    
    public int[] findSmallestRange(List<List<Integer>> nums) {
        List<int[]> combined = new ArrayList<>();
    
        for (int i = 0; i < nums.size(); i++) {
            for (int num : nums.get(i)) {
                combined.add(new int[] { num, i });
            }
        }
    
        combined.sort(Comparator.comparingInt(a -> a[0]));
    
        Map<Integer, Integer> map = new HashMap<>();
        int begin = 0, matches = 0;
        int minLengthStart = 0, minLengthEnd = Integer.MAX_VALUE;
    
        for (int end = 0; end < combined.size(); end++) {
            map.put(
                combined.get(end)[1],
                map.getOrDefault(combined.get(end)[1], 0) + 1
            );
            if (map.get(combined.get(end)[1]) == 1) matches++;
    
            while (matches == nums.size()) {
                int currentRange = combined.get(end)[0] - combined.get(begin)[0];
                if (currentRange < minLengthEnd - minLengthStart) {
                    minLengthStart = combined.get(begin)[0];
                    minLengthEnd = combined.get(end)[0];
                }
    
                map.put(
                    combined.get(begin)[1],
                    map.get(combined.get(begin)[1]) - 1
                );
                if (map.get(combined.get(begin)[1]) == 0) matches--;
                begin++;
            }
        }
    
        return new int[] { minLengthStart, minLengthEnd };
    }
}

The solution presented addresses the problem of finding the smallest range that includes at least one number from each of the K lists. The approach is implemented in Java and utilizes several key data structures and algorithms discussed below:

• List 'combined' is used to collect all the integers across the K lists along with their respective list indices. This aids in retaining the knowledge of an integer's origin list.

• Sorting: After populating 'combined', it is sorted based on the integers. Sorting helps to linearly traverse and find the smallest sequential range covering all lists.

• HashMap 'map' keeps track of the number of occurrences of indices during a range consideration. This is central to identifying when a certain range has elements from all K lists.

• Sliding Window Technique: Implementing a dynamic window (using pointers 'begin' and 'end'), the algorithm adjusts its size to potentially reduce the range while still covering all lists.

  • Increasing 'end' expands the window to include more elements/list indices.
  • Adjust 'begin' to contract the window from the left, testing smaller valid ranges.

• Range Updates: When a valid range containing all list indices is found which is smaller than any previous range, update the start and end of this minimal range.

Return:

• After iterating through all elements, the smallest starting and ending points of the range determined to be minimal are returned as an integer array.

By analyzing the frequency of list indices within the constructed sliding window, this algorithm efficiently finds the minimal range. The use of additional storage like the hash map and combined list array is a trade-off for improving time complexity by potentially reducing the number of comparisons needed to find the smallest range.

class Solution:
    def findSmallestRange(self, lists: List[List[int]]) -> List[int]:
        combined_lists = []
    
        # Combining all numbers with their originating list index
        for index in range(len(lists)):
            for value in lists[index]:
                combined_lists.append((value, index))
    
        # Sorting combined number and index list
        combined_lists.sort()
    
        # Initialize two pointers for finding minimum range
        occurrences = defaultdict(int)
        start, within_range = 0, 0
        min_start, min_end = 0, float("inf")
    
        for end in range(len(combined_lists)):
            occurrences[combined_lists[end][1]] += 1
            if occurrences[combined_lists[end][1]] == 1:
                within_range += 1
    
            # Adjust window to include elements from all lists
            while within_range == len(lists):
                current_range = combined_lists[end][0] - combined_lists[start][0]
                if current_range < min_end - min_start:
                    min_start = combined_lists[start][0]
                    min_end = combined_lists[end][0]
    
                occurrences[combined_lists[start][1]] -= 1
                if occurrences[combined_lists[start][1]] == 0:
                    within_range -= 1
                start += 1
    
        return [min_start, min_end]

This summary explains the process of finding the smallest range that includes at least one number from each of the K lists using Python.

• This solution involves creating a class Solution with a function findSmallestRange, which takes lists as the input parameter and returns a list of two integers indicating the smallest range.

• Start by combining all elements from each list along with their respective list indices into the combined_lists. This prepares for a comprehensive evaluation of the values across all lists.

• Sort combined_lists to streamline the subsequent step of minimizing the range.

• Use two pointers, start and end, which help in traversing combined_lists while evaluating potential minimum ranges. Initialize a dictionary occurrences to count occurrences of each list index within the current range and an integer within_range to track when a range has included elements from all lists.

• Traverse combined_lists using the end pointer. For each element, update occurrences and adjust within_range. If occurrences of a new list index reaches one, increment the within_range.

• When within_range matches the total number of K lists, evaluate if the current range (from start to end) is smaller than the previously found ranges. If so, update min_start and min_end with the current start and end point values.

• Before moving the start pointer to narrow the range, decrease the frequency of the current start index element in occurrences. If the frequency drops to zero, decrement within_range, and then move the start pointer forward to potentially discover a new minimum range with a swapped out element.

• Continue this process until you have completely traversed combined_lists with the end pointer, ensuring that all combinations have been tested.

• Finally, return [min_start, min_end], which holds the smallest range found.

By following these steps, the function efficiently finds the smallest numerical range containing at least one number from each list, dealing with complexities using a dynamic sliding window technique.