1477 LeetCode problem solution

LeetCode problem link: 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

LeetCode 1477 problem description

Medium level problem.

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with a sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2

Explanation: Only two sub-arrays have sum 3: [3] and [3]. Their total length is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2

Explanation: We can choose [7] at the beginning and [7] at the end.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i] <= 1000
1 <= target <= 10⁸

LeetCode 1477 problem: solution explanation

We can solve this problem by using Sliding Window + Prefix Minimum patterns.

Because every value in arr is positive, we use a sliding window to find sub-arrays whose sum is exactly target.

At the same time, we store the minimum length of a valid sub-array found before each position. This allows us to combine the current valid sub-array with the shortest non-overlapping one found earlier.

Step 1: Find target-sum sub-arrays

Use two pointers:

left
right

and maintain the sum of the current window:

sum = arr[left] + ... + arr[right]

For every right, add arr[right] to sum.

If:

sum > target

move left forward and subtract elements until:

sum <= target

Because all elements are positive, increasing right increases the sum and increasing left decreases it.

When:

sum == target

the current sub-array [left, right] is valid and its length is:

right - left + 1

Step 2: Store the shortest valid sub-array in each prefix

We use:

best[i]

to store the minimum length of a target-sum sub-array that ends at or before index i.

If the current window [left, right] has sum equal to target, its length is:

len = right - left + 1

We update:

minLen = min(minLen, len)
best[right] = minLen

If the current window is not valid, best[right] keeps the shortest valid length found earlier.

Step 3: Combine two non-overlapping sub-arrays

Suppose the current valid sub-array is:

[left, right]

A non-overlapping previous sub-array must end before left.

Therefore, its shortest possible length is stored in:

best[left - 1]

If it exists, combine the two lengths:

best[left - 1] + (right - left + 1)

and update:

result = min(result, best[left - 1] + len)

Because the previous sub-array ends at or before left - 1, the two sub-arrays cannot overlap.

Example

For:

arr = [3, 2, 2, 4, 3]
target = 3

At index 0, the window:

[3]

has sum 3, so:

best[0] = 1

At index 4, we find another valid window:

[3]

with:

left = 4
right = 4
len = 1

The shortest valid sub-array before left is:

best[3] = 1

Therefore:

result = 1 + 1
result = 2

LeetCode 1477 problem: complexity

Each element is added to the sliding window once and removed at most once.

The best array is updated once for every index.

Time complexity: O(n)
Space complexity: O(n)

Pattern: Sliding Window
Technique: Two Pointers / Prefix Minimum

LeetCode 1477 C++ solution

class Solution {
public:
  int minSumOfLengths(vector<int>& arr, int target)
  {
    int n = arr.size();
    int INF = n + 1;

    vector<int> best(n, INF);

    int left = 0;
    int sum = 0;
    int minLen = INF;
    int result = INF;

    for(int right = 0; right < n; right++)
    {
      sum += arr[right];

      while(sum > target)
      {
        sum -= arr[left];
        left++;
      }

      if(sum == target)
      {
        int len = right - left + 1;

        if(left > 0 && best[left - 1] != INF)
          result = min(result, len + best[left - 1]);

        minLen = min(minLen, len);
      }

      best[right] = minLen;
    }

    return result == INF ? -1 : result;
  }
};

LeetCode 1477 Java solution

class Solution {
  public int minSumOfLengths(int[] arr, int target) {
    int n = arr.length;
    int INF = n + 1;

    int[] best = new int[n];
    Arrays.fill(best, INF);

    int left = 0;
    int sum = 0;
    int minLen = INF;
    int result = INF;

    for(int right = 0; right < n; right++) {
      sum += arr[right];

      while(sum > target) {
        sum -= arr[left];
        left++;
      }

      if(sum == target) {
        int len = right - left + 1;

        if(left > 0 && best[left - 1] != INF)
          result = Math.min(result, len + best[left - 1]);

        minLen = Math.min(minLen, len);
      }

      best[right] = minLen;
    }

    return result == INF ? -1 : result;
  }
}

LeetCode 1477 JavaScript solution

var minSumOfLengths = function(arr, target) {
  const n = arr.length;
  const INF = n + 1;

  const best = new Array(n).fill(INF);

  let left = 0;
  let sum = 0;
  let minLen = INF;
  let result = INF;

  for(let right = 0; right < n; right++) {
    sum += arr[right];

    while(sum > target) {
      sum -= arr[left];
      left++;
    }

    if(sum === target) {
      const len = right - left + 1;

      if(left > 0 && best[left - 1] !== INF)
        result = Math.min(result, len + best[left - 1]);

      minLen = Math.min(minLen, len);
    }

    best[right] = minLen;
  }

  return result === INF ? -1 : result;
};

LeetCode 1477 TypeScript solution

function minSumOfLengths(arr: number[], target: number): number {
  const n: number = arr.length;
  const INF: number = n + 1;

  const best: number[] = new Array(n).fill(INF);

  let left: number = 0;
  let sum: number = 0;
  let minLen: number = INF;
  let result: number = INF;

  for(let right = 0; right < n; right++) {
    sum += arr[right];

    while(sum > target) {
      sum -= arr[left];
      left++;
    }

    if(sum === target) {
      const len: number = right - left + 1;

      if(left > 0 && best[left - 1] !== INF)
        result = Math.min(result, len + best[left - 1]);

      minLen = Math.min(minLen, len);
    }

    best[right] = minLen;
  }

  return result === INF ? -1 : result;
}

LeetCode 1477 Python solution

class Solution:
  def minSumOfLengths(self, arr: List[int], target: int) -> int:
    n = len(arr)
    INF = n + 1

    best = [INF] * n

    left = 0
    window_sum = 0
    min_len = INF
    result = INF

    for right in range(n):
      window_sum += arr[right]

      while window_sum > target:
        window_sum -= arr[left]
        left += 1

      if window_sum == target:
        length = right - left + 1

        if left > 0 and best[left - 1] != INF:
          result = min(result, length + best[left - 1])

        min_len = min(min_len, length)

      best[right] = min_len

    return -1 if result == INF else result