632. Smallest Range Covering Elements from K Lists #

Problem #

You have k lists of sorted integers in ascending 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: [[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].

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -10^5 <= value of elements <= 10^5.

Problem Summary #

You have k integer arrays sorted in ascending order. Find the smallest range such that each of the k lists has at least one number included in it.

We define that if b-a < d-c, or when b-a == d-c, a < c, then range [a,b] is smaller than [c,d].

Note:

• The given lists may contain duplicate elements, so ascending order here means >=.
• 1 <= k <= 3500
• -105 <= value of elements <= 105
• For users using Java, please note that the input type has been modified to List<List>. You can see this change after resetting the code template.

Solution Approach #

• Given K arrays, the requirement is to find a range among these K arrays that can include at least one element from each of the K arrays.
• This problem is a variant of Problem 76. Problem 76 is solved with a sliding window; it requires finding the smallest substring in the parent string S that can contain all the characters of string T. This problem is similar: the parent string can be viewed as a large array formed by merging the K arrays, while string T is formed by taking one element from each of the K arrays. The range to find is the same: the smallest range that can contain T. Another difference is that Problem 76 deals with strings, while this problem deals with numbers. When finally constructing T, it is necessary to ensure that each of the K arrays has one element, so naturally we need to maintain the array index where each element belongs. After the above conversion, this problem can be transformed into the solution for Problem 76.
• In the specific solution process, use a map to maintain the frequency of the K arrays appearing in the window. The time complexity is O(n*log n), and the space complexity is O(n).

Code #

package leetcode

import (
	"math"
	"sort"
)

func smallestRange(nums [][]int) []int {
	numList, left, right, count, freqMap, res, length := []element{}, 0, -1, 0, map[int]int{}, make([]int, 2), math.MaxInt64
	for i, ns := range nums {
		for _, v := range ns {
			numList = append(numList, element{val: v, index: i})
		}
	}
	sort.Sort(SortByVal{numList})
	for left < len(numList) {
		if right+1 < len(numList) && count < len(nums) {
			right++
			if freqMap[numList[right].index] == 0 {
				count++
			}
			freqMap[numList[right].index]++
		} else {
			if count == len(nums) {
				if numList[right].val-numList[left].val < length {
					length = numList[right].val - numList[left].val
					res[0] = numList[left].val
					res[1] = numList[right].val
				}
			}
			freqMap[numList[left].index]--
			if freqMap[numList[left].index] == 0 {
				count--
			}
			left++
		}
	}
	return res
}

type element struct {
	val   int
	index int
}

type elements []element

// Len define
func (p elements) Len() int { return len(p) }

// Swap define
func (p elements) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

// SortByVal define
type SortByVal struct{ elements }

// Less define
func (p SortByVal) Less(i, j int) bool {
	return p.elements[i].val < p.elements[j].val
}