2875.minimum-size-subarray-in-infinite-array.md

2875. Minimum Size Subarray in Infinite Array

Suppose the target consists of some groups of nums with length k and some remaing elements in nums:

[X X X X X X] + k * [X..X] + [X X X X X X]
target   |------------------------|

The value k will be the target / sum and target % sum (remainingSum) will be the remaining elements, where sum is the sum of all elements.

[X X X X X X][X X X X X X]
         |--------|

Then for the remaining elements, we can use Sliding Window approach to find the length of subarray which sum is target % sum form the circular array:

fun minSizeSubarray(nums: IntArray, target: Int): Int {
    val n = nums.size
    var sum = 0
    for (num in nums) {
        sum += num
    }
    val k = target / sum
    val remainingSum = target % sum

    // there is no remaining elements
    if (remainingSum == 0) return k * n

    // Sliding Window
    var left = 0
    var right = 0
    var length = Int.MAX_VALUE
    var sum = 0
    // We have to iterate 2 * n times, because we check the circular array.
    while (right < n * 2) {
        sum += nums[right % n]

        while (sum > remainingSum) {
            sum -= nums[left % n]
            left++
        }
        if (sum == remainingSum) {
            length = minOf(length, right - left + 1)
        }
        right++
    }
    return if (length == Int.MAX_VALUE) -1 else times * nums.size + length
}

• Time Complexity: O(n), we have to iterate 2 * n times.
• Space Complexity: O(1).