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

The problem asks us to find two different subarrays inside the given array such that: 1. Each subarray has a sum exactly

leetcodemediumarrayhash-tablebinary-searchdynamic-programmingsliding-window

LeetCode Problem 1477

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Dynamic Programming, Sliding Window

Solution

Problem Understanding

The problem asks us to find two different subarrays inside the given array such that:

  1. Each subarray has a sum exactly equal to target
  2. The two subarrays do not overlap
  3. The total length of the two chosen subarrays is as small as possible

A subarray is a contiguous portion of the array. Since the subarrays must not overlap, if one subarray uses indices [l1, r1] and another uses [l2, r2], then either r1 < l2 or r2 < l1.

The input consists of:

  • arr, an array of positive integers
  • target, the desired sum for each subarray

The output is:

  • The minimum possible sum of lengths of two non-overlapping subarrays whose sums equal target
  • -1 if no such pair exists

The constraints are very important:

  • arr.length can be as large as 10^5
  • Each element is positive
  • target can also be large

Because the array size is large, any algorithm slower than roughly O(n log n) or O(n) is likely too slow. A naive solution that checks every possible pair of subarrays would be far too expensive.

An important property is that all numbers are positive. This allows us to use a sliding window efficiently, because increasing the window always increases the sum, and shrinking the window always decreases it.

Several edge cases are important:

  • The array may contain only one valid subarray, in which case the answer is -1
  • Multiple valid subarrays may overlap, but overlapping pairs are not allowed
  • The optimal answer may involve two very small subarrays far apart in the array
  • There may be many valid subarrays, requiring us to carefully track the minimum length seen so far

Approaches

Brute Force Approach

A straightforward solution is to generate every subarray whose sum equals target, then compare every pair of such subarrays to find the minimum combined length among non-overlapping pairs.

We can do this in several steps:

  1. Enumerate all subarrays
  2. Store every subarray whose sum equals target
  3. Compare every pair
  4. Check whether they overlap
  5. Track the minimum combined length

This approach is correct because it explicitly checks every valid possibility.

However, it is too slow.

There are O(n^2) possible subarrays. Comparing all pairs of valid subarrays can also take O(n^2) time in the worst case. This can lead to overall complexity approaching O(n^4) in the naive version, or O(n^2) even with optimizations.

With n = 100000, this is completely infeasible.

Optimal Approach

The key insight is that we do not need to compare every pair explicitly.

Instead, while scanning the array from left to right, we can:

  1. Use a sliding window to find subarrays with sum equal to target
  2. Keep track of the shortest valid subarray ending at or before each position
  3. Whenever we find a new valid subarray, combine it with the best earlier non-overlapping subarray

Because all numbers are positive, the sliding window works efficiently in linear time.

We maintain:

  • best[i], the minimum length of a valid subarray ending at or before index i
  • A running answer representing the best pair found so far

When we discover a subarray [left, right]:

  • Its length is right - left + 1
  • Any previous valid subarray must end before left
  • So we combine the current length with best[left - 1]

This avoids comparing every pair directly.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) to O(n⁴) O(n²) Enumerates and compares many subarrays
Optimal O(n) O(n) Sliding window with DP tracking minimum lengths

Algorithm Walkthrough

Step 1: Initialize Variables

We use:

  • left for the sliding window start
  • current_sum for the current window sum
  • best array where best[i] stores the shortest valid subarray ending at or before index i
  • answer initialized to infinity

The best array is critical because it lets us instantly retrieve the shortest earlier valid subarray.

Step 2: Expand the Sliding Window

Iterate through the array using right.

At each step:

  • Add arr[right] to current_sum

Since all values are positive, the window sum only increases when we expand.

Step 3: Shrink the Window When Needed

If current_sum > target, shrink the window from the left:

  • Subtract arr[left]
  • Increment left

We continue shrinking until current_sum <= target.

Because numbers are positive, once the sum exceeds the target, moving left forward is the only way to reduce it.

Step 4: Detect Valid Subarrays

Whenever current_sum == target, we found a valid subarray [left, right].

Compute:

length = right - left + 1

Step 5: Combine With Previous Non-overlapping Subarrays

To avoid overlap:

  • Any earlier subarray must end before left

If left > 0 and best[left - 1] is valid, then:

answer = min(answer, length + best[left - 1])

This combines the current subarray with the best earlier compatible one.

Step 6: Update the Best Array

We update:

best[right] = min(best[right - 1], length)

This means:

  • Either the best previous solution remains optimal
  • Or the current subarray is shorter

If no valid subarray ends at right, then:

best[right] = best[right - 1]

Step 7: Return the Result

If answer is still infinity, return -1.

Otherwise return answer.

Why it works

The algorithm works because at every index we maintain the shortest valid subarray ending at or before that position. When a new valid subarray is found, we immediately combine it with the best earlier non-overlapping subarray. Since every valid subarray is processed exactly once and every compatible earlier subarray is summarized inside best, the algorithm never misses the optimal pair.

Python Solution

from typing import List

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

        INF = float('inf')

        best = [INF] * n

        left = 0
        current_sum = 0
        answer = INF

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

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

            if current_sum == target:
                current_length = right - left + 1

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

                best[right] = current_length

            if right > 0:
                best[right] = min(best[right], best[right - 1])

        return -1 if answer == INF else answer

The implementation follows the algorithm directly.

The best array stores the minimum valid subarray length seen so far up to each position. Initially, every entry is infinity because no valid subarray has been found.

The sliding window is maintained using left and right. Since all elements are positive, the window can be adjusted efficiently without revisiting elements excessively.

Whenever a valid subarray is discovered, we first compute its length. Then we check whether there exists a non-overlapping earlier subarray using best[left - 1].

Finally, we propagate the minimum value forward inside the best array so every position contains the shortest valid subarray ending at or before that index.

Go Solution

package main

import "math"

func minSumOfLengths(arr []int, target int) int {
	n := len(arr)

	const INF = math.MaxInt32

	best := make([]int, n)

	for i := 0; i < n; i++ {
		best[i] = INF
	}

	left := 0
	currentSum := 0
	answer := INF

	for right := 0; right < n; right++ {
		currentSum += arr[right]

		for currentSum > target {
			currentSum -= arr[left]
			left++
		}

		if currentSum == target {
			currentLength := right - left + 1

			if left > 0 && best[left-1] != INF {
				if currentLength+best[left-1] < answer {
					answer = currentLength + best[left-1]
				}
			}

			best[right] = currentLength
		}

		if right > 0 && best[right-1] < best[right] {
			best[right] = best[right-1]
		}
	}

	if answer == INF {
		return -1
	}

	return answer
}

The Go implementation mirrors the Python logic closely.

Go does not have a built-in infinity value for integers, so math.MaxInt32 is used as a sentinel value.

Slices are initialized explicitly, and minimum comparisons are written manually because Go does not provide a built-in min function for integers in older versions.

Since the constraints fit comfortably inside 32-bit integers, integer overflow is not a concern here.

Worked Examples

Example 1

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

Valid subarrays:

  • [3] at index 0
  • [3] at index 4
right Window Sum Valid? best[right] answer
0 [3] 3 Yes 1 INF
1 [2] 2 No 1 INF
2 [2,2] 4 Shrink 1 INF
3 [2,4] 6 Shrink 1 INF
4 [3] 3 Yes 1 2

At index 4:

  • Current subarray length = 1
  • best[3] = 1
  • Total = 1 + 1 = 2

Final answer:

2

Example 2

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

Valid subarrays:

  • [7] at index 0
  • [3,4]
  • [7] at index 3
right Valid Subarray Length best[right] answer
0 [0,0] 1 1 INF
2 [1,2] 2 1 3
3 [3,3] 1 1 2

The best pair is:

  • First [7]
  • Last [7]

Total length:

1 + 1 = 2

Example 3

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

Only one valid subarray exists:

  • [6]

Since two non-overlapping subarrays are required, the result is:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element enters and leaves the sliding window at most once
Space O(n) The best array stores one value per index

The sliding window guarantees linear processing because both pointers only move forward. No nested rescanning occurs. The best array requires linear additional memory.

Test Cases

from typing import List

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

        INF = float('inf')

        best = [INF] * n

        left = 0
        current_sum = 0
        answer = INF

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

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

            if current_sum == target:
                current_length = right - left + 1

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

                best[right] = current_length

            if right > 0:
                best[right] = min(best[right], best[right - 1])

        return -1 if answer == INF else answer

sol = Solution()

assert sol.minSumOfLengths([3,2,2,4,3], 3) == 2
# Basic example with two single-element subarrays

assert sol.minSumOfLengths([7,3,4,7], 7) == 2
# Best solution uses two isolated single-element windows

assert sol.minSumOfLengths([4,3,2,6,2,3,4], 6) == -1
# Only one valid subarray exists

assert sol.minSumOfLengths([1,1,1,1,1], 2) == 4
# Multiple overlapping windows, choose non-overlapping ones

assert sol.minSumOfLengths([5,5,4,4,5], 3) == -1
# No valid subarray exists

assert sol.minSumOfLengths([3,1,1,1,5,1,2,1], 3) == 3
# Combination of different-sized windows

assert sol.minSumOfLengths([1,6,1], 7) == -1
# Entire array forms one valid subarray only

assert sol.minSumOfLengths([2,1,1,2,1,1,2], 3) == 4
# Multiple equal-length valid windows

assert sol.minSumOfLengths([1,2,2,3,2,2,1], 4) == 4
# Non-overlapping middle windows

assert sol.minSumOfLengths([1,1,1,2,2,2,1,1], 3) == 4
# Many overlapping possibilities

Test Summary

Test Why
[3,2,2,4,3], 3 Basic example from prompt
[7,3,4,7], 7 Multiple valid choices
[4,3,2,6,2,3,4], 6 Only one valid subarray
[1,1,1,1,1], 2 Heavy overlap between windows
[5,5,4,4,5], 3 No solution exists
[3,1,1,1,5,1,2,1], 3 Mixed subarray lengths
[1,6,1], 7 Single valid full-array window
[2,1,1,2,1,1,2], 3 Multiple equal candidates
[1,2,2,3,2,2,1], 4 Interior optimal windows
[1,1,1,2,2,2,1,1], 3 Many overlapping combinations

Edge Cases

One important edge case occurs when only one valid subarray exists. A naive implementation might accidentally return its length instead of recognizing that two non-overlapping subarrays are required. This implementation avoids that mistake because the answer is only updated when a previous valid subarray already exists in the best array.

Another important edge case involves overlapping subarrays. For example, in [1,1,1,1] with target 2, many valid windows overlap. The algorithm carefully checks best[left - 1], ensuring that the earlier subarray ends strictly before the current one begins.

A third edge case occurs when the optimal solution uses very small subarrays far apart in the array. A greedy approach that always chooses the first valid subarray could fail here. The best array solves this by continuously tracking the shortest valid subarray seen so far, guaranteeing that every future window is paired with the globally optimal earlier choice.

A final edge case involves arrays with no valid subarrays at all. In this situation, the answer variable remains infinity throughout execution, and the algorithm correctly returns -1.