LeetCode in Kotlin

632. Smallest Range Covering Elements from K Lists

Hard

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.

Solution

import java.util.Objects
import java.util.PriorityQueue

class Solution {
    internal class Triplet(var value: Int, var row: Int, var idx: Int) : Comparable<Triplet?> {
        override operator fun compareTo(other: Triplet?): Int {
            return value - other!!.value
        }
    }

    fun smallestRange(nums: List<List<Int>>): IntArray {
        val pq = PriorityQueue<Triplet>()
        var maxInPq = Int.MIN_VALUE
        for (i in nums.indices) {
            pq.add(Triplet(nums[i][0], i, 0))
            if (maxInPq < nums[i][0]) {
                maxInPq = nums[i][0]
            }
        }
        var rangeSize = maxInPq - Objects.requireNonNull(pq.peek()).value + 1
        var rangeLeft = Objects.requireNonNull(pq.peek()).value
        var rangeRight = maxInPq
        while (true) {
            val nextNumber = pq.remove()
            if (nextNumber.idx + 1 < nums[nextNumber.row].size) {
                val `val` = nums[nextNumber.row][nextNumber.idx + 1]
                if (`val` > maxInPq) {
                    maxInPq = `val`
                }
                pq.add(Triplet(`val`, nextNumber.row, nextNumber.idx + 1))
                if (maxInPq - Objects.requireNonNull(pq.peek()).value + 1 < rangeSize) {
                    rangeSize = maxInPq - pq.peek().value + 1
                    rangeLeft = maxInPq
                    rangeRight = pq.peek().value
                }
            } else {
                break
            }
        }
        val answer = IntArray(2)
        answer[0] = rangeLeft
        answer[1] = rangeRight
        return answer
    }
}

This site is open source. Improve this page.