#1477

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

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

Find two non-overlapping sub-arrays with a given target sum and return the minimal total length efficiently using array scanning and hash lookup.

array hash table binary search dynamic programming sliding window

Problem Statement

Given an integer array arr and an integer target, find two non-overlapping sub-arrays where each sub-array sums exactly to target. Your goal is to minimize the sum of their lengths.

Return the minimal sum of lengths of these two sub-arrays, or -1 if it is impossible to find such two sub-arrays. Consider scenarios where multiple sub-arrays exist but only certain pairs yield the minimal combined length.

Examples

Example 1

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

Output: 2

Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2

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

Output: 2

Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3

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

Output: -1

We have only one sub-array of sum = 6.

Constraints

1 <= arr.length <= 105
1 <= arr[i] <= 1000
1 <= target <= 108

Solution Approach

Prefix Scan with Hash Map

Maintain a running prefix sum while iterating over the array. Store each prefix sum in a hash map pointing to its index. Whenever the difference between current prefix sum and target exists in the map, record the sub-array length.

Build Minimal Left and Right Arrays

Create two arrays: prefix[i] stores the minimum sub-array length ending before index i, suffix[i] stores the minimum sub-array length starting at or after index i. This helps quickly check non-overlapping pairs.

Combine Results for Minimal Total Length

Iterate over all split points to combine prefix and suffix lengths. Track the minimal sum of two non-overlapping sub-arrays, ensuring indices do not overlap. Return -1 if no valid combination is found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is scanned once and hash map lookups are O(1). Space complexity is O(n) for the prefix and suffix arrays plus the hash map.

What Interviewers Usually Probe

Check for multiple sub-arrays with the same sum and ensure non-overlapping selection.
Expect discussion on using prefix sums with hash maps to quickly identify valid sub-arrays.
Watch for edge cases where no two valid sub-arrays exist, requiring a -1 return.

Common Pitfalls or Variants

Common pitfalls

Overlapping sub-arrays are mistakenly counted; always verify index boundaries.
Not updating the minimal length in prefix or suffix arrays, leading to incorrect total length.
Ignoring single sub-array cases where a second sub-array does not exist.

Follow-up variants

Find k non-overlapping sub-arrays with the same target sum and minimize total length.
Return the maximal total length of two non-overlapping sub-arrays with target sum.
Handle arrays with negative integers, requiring careful prefix sum handling.

FAQ

What is the main strategy to solve Find Two Non-overlapping Sub-arrays Each With Target Sum?

Use a prefix sum hash map to locate sub-arrays efficiently, then combine minimal left and right lengths to find non-overlapping pairs.

How do prefix and suffix arrays help in this problem?

Prefix and suffix arrays store minimal lengths of sub-arrays from the left and right, allowing quick combination checks without overlap.

Can the array contain negative numbers?

Yes, but prefix sum tracking must account for decreasing sums, which may require extra care in hash map updates.

What should be returned if only one valid sub-array exists?

Return -1 because the problem requires exactly two non-overlapping sub-arrays.

Is this problem solved using sliding window?

Sliding window works only for positive integers; for mixed or general cases, hash map prefix sums ensure correctness.

terminal

Solution

Solution 1: Hash Table + Prefix Sum + Dynamic Programming

We can use a hash table $d$ to record the most recent position where each prefix sum appears, with the initial value $d[0]=0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        d = {0: 0}
        s, n = 0, len(arr)
        f = [inf] * (n + 1)
        ans = inf
        for i, v in enumerate(arr, 1):
            s += v
            f[i] = f[i - 1]
            if s - target in d:
                j = d[s - target]
                f[i] = min(f[i], i - j)
                ans = min(ans, f[j] + i - j)
            d[s] = i
        return -1 if ans > n else ans

Continue Practicing

#1658 minimum operations to reduce x to zero #1027 longest arithmetic subsequence #2008 maximum earnings from taxi