Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode solution in Python

1
class Solution:
2
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
3
        l, windowSum, res = 0, 0, float("inf")
4
        min_till = [float("inf")] * len(
5
            arr
6
        )  # records smallest lenth of subarry with target sum up till index i.
7
        for r, num in enumerate(arr):  # r:right pointer and index of num in arr
8
            windowSum += num
9
            while windowSum > target:
10
                # when the sum of current window is larger then target, shrink the left end of the window one by one until windowSum <= target
11
                windowSum -= arr[l]
12
                l += 1
13
                # the case when we found a new target sub-array, i.e. current window
14
            if windowSum == target:
15
                # length of current window
16
                curLen = r - l + 1
17
                # min_till[l - 1]: the subarray with min len up till the previous position of left end of the current window:
18
                # avoid overlap with cur window
19
                # new_sum_of_two_subarray = length of current window + the previous min length of target subarray without overlapping
20
                # , if < res, update res.
21
                res = min(res, curLen + min_till[l - 1])
22
                # Everytime we found a target window, update the min_till of current right end of the window,
23
                # for future use when sum up to new length of sum_of_two_subarray and update the res.
24
                min_till[r] = min(curLen, min_till[r - 1])
25
            else:
26
                # If windowSum < target: window with current arr[r] as right end does not have any target subarry,
27
                # the min_till[r] doesn't get any new minimum update, i.e it equals to previous min_till at index r - 1.
28
                min_till[r] = min_till[r - 1]
29
        return res if res < float("inf") else -1