LeetCode/kt/shortest-subarray-with-sum-at-least-k.kt

class Solution {
    fun shortestSubarray(
        nums: IntArray,
        k: Int,
    ): Int {
        val sums =
            nums
                .scan(0L) { runningSum, x ->
                    runningSum + x.toLong()
                }
                .toList()

        val candidates = ArrayDeque<Int>()

        return (0..nums.size)
            .map { i ->
                var shortestLength = Int.MAX_VALUE
                while (
                    candidates.isNotEmpty() &&
                    sums[i] - sums[candidates.first()] >= k
                ) {
                    shortestLength =
                        listOf(
                            shortestLength, i - candidates.removeFirst(),
                        ).min()
                }

                while (
                    candidates.isNotEmpty() &&
                    sums[i] <= sums[candidates.last()]
                ) {
                    candidates.removeLast()
                }

                candidates.add(i)

                shortestLength
            }
            .filter { it < Int.MAX_VALUE }
            .minOrNull() ?: -1
    }
}