LeetCode Entry

209. Minimum Size Subarray Sum

6.07.2023 medium 2023 kotlin

Min length subarray with sum >= target

209. Minimum Size Subarray Sum medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/267

Problem TLDR

Min length subarray with sum >= target

Intuition

Use two pointers: one adding to sum and another subtracting. As all numbers are positive, then sum will always be increasing with adding a number and deceasing when subtracting.

Approach

Let’s use Kotlin Sequence API

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


fun minSubArrayLen(target: Int, nums: IntArray): Int {
    var lo = 0
    var sum = 0
    return nums.asSequence().mapIndexed { hi, n ->
        sum += n
        while (sum - nums[lo] >= target) sum -= nums[lo++]
        (hi - lo + 1).takeIf { sum >= target }
    }
    .filterNotNull()
    .min() ?: 0
}