LeetCode in Kotlin

862. Shortest Subarray with Sum at Least K

Hard

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1

Output: 1

Example 2:

Input: nums = [1,2], k = 4

Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3

Output: 3

Constraints:

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

Solution

import java.util.Deque
import java.util.LinkedList

class Solution {
    internal class Pair(var index: Int, var value: Long)

    fun shortestSubarray(nums: IntArray, k: Int): Int {
        val n = nums.size
        val dq: Deque<Pair> = LinkedList()
        var ans = Int.MAX_VALUE
        var sum: Long = 0
        for (i in 0 until n) {
            sum += nums[i].toLong()
            // Keep dq in incrementing order
            while (dq.isNotEmpty() && sum <= dq.peekLast().value) dq.removeLast()
            // Add current sum and index
            dq.add(Pair(i, sum))
            // Calculate your answer here
            if (sum >= k) ans = Math.min(ans, i + 1)

            // Check if Contraction is possible or not
            while (dq.isNotEmpty() && sum - dq.peekFirst().value >= k) {
                ans = ans.coerceAtMost(i - dq.peekFirst().index)
                dq.removeFirst()
            }
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}

This site is open source. Improve this page.