DDSA Solutions

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

MediumView on LeetCode
ArrayHash TableBinary SearchSliding WindowDynamic ProgrammingPrefix Sum

Problem Overview

You need two disjoint subarrays that each sum to target, and their lengths should be as small as possible together.

Intuition

You need two disjoint subarrays that each sum to target, and their lengths should be as small as possible together. Because every value is positive, each right endpoint has at most one left endpoint that makes the window sum equal target, so a sliding window finds every candidate in linear time.

Algorithm

  1. 1Keep a sliding window [l, r] and its sum.
  2. 2Expand r, and shrink l while the sum exceeds target.
  3. 3best[i] stores the shortest target subarray ending at or before i.
  4. 4When the window sums to target, if best[l-1] exists, update the answer with best[l-1] plus the current window length.
  5. 5Refresh a running shortest length and write it into best[r].
  6. 6Return the answer, or -1 if no valid pair was found.

Example Walkthrough

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

  1. 1.The single-element windows [3] at the start and [3] at the end each hit the target.
  2. 2.Pairing those two non-overlapping windows gives length sum 2.
  3. 3.No shorter pair exists.

Output: 2

Common Pitfalls

  • •The two windows must not share indices; pairing a window with best just before its left edge enforces that.
  • •Positive array values are required for the unique sliding window; negatives would break it.
  • •best must carry forward the minimum even on indices that do not end a target window.
  • •Return -1 when fewer than two valid windows can be placed without overlap.
1477.cs
C#
// Approach: Positive elements => unique sliding window for each right end.
// best[i] = shortest target subarray ending at or before i. When window
// [l, r] hits target, pair it with best[l-1] if that exists, then refresh
// the running shortest length into best[r].
// Complexity: O(n) time, O(n) extra space. Optimal up to constants.
public class Solution
{
    public int MinSumOfLengths(int[] arr, int target)
    {
        int n = arr.Length;
        int ans = int.MaxValue;
        int sum = 0;
        int bestSoFar = int.MaxValue;
        int[] best = new int[n];

        for (int l = 0, r = 0; r < n; r++)
        {
            sum += arr[r];
            while (sum > target)
                sum -= arr[l++];

            if (sum == target)
            {
                int len = r - l + 1;
                if (l > 0 && best[l - 1] != int.MaxValue)
                    ans = Math.Min(ans, best[l - 1] + len);
                bestSoFar = Math.Min(bestSoFar, len);
            }

            best[r] = bestSoFar;
        }

        return ans == int.MaxValue ? -1 : ans;
    }
}
Was this solution helpful?

Related Problems