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

2875. Minimum Size Subarray in Infinite Array

Sliding Window

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 (remainingTarget) 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]
         |--------|

For example, [1, 2, 3, 4] and target = 23:

[1, 2, 3, 4]
target = 23

// Form the infinite array
[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ...]
 |--------------------------|

// Then we find the shortest subrray that sum is 3
[1, 2, 3, 4]
 |--|

ans = 2 + (23 / 10) * (23 % 10) = 2 + 2 * 3 = 8

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 remainingTarget = target % sum

    // there is no remaining elements
    if (remainingTarget == 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 > remainingTarget) {
            sum -= nums[left % n]
            left++
        }
        if (sum == remainingTarget) {
            length = minOf(length, right - left + 1)
        }
        right++
    }
    // Remember to add `k` segments.
    return if (length == Int.MAX_VALUE) -1 else times * n + length
}

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