Find Two Non-overlapping Sub-arrays Each With Target Sum Python/Java solution

Python and Java implementations typically use a prefix sum variable, a HashMap (or dictionary) for sum-to-index mapping, and an array tracking the best subarray length seen so far. Each iteration checks if prefixSum - target exists and updates the minimal combined length. The approach runs in O(n) time with O(n) space.

What is the best approach for Find Two Non-overlapping Sub-arrays Each With Target Sum?

The optimal approach uses prefix sums with a hash map and a dynamic programming array to track the shortest valid subarray ending before each index. While scanning the array, you detect target-sum subarrays in O(1) using prefixSum - target lookups. This enables combining two non-overlapping subarrays while keeping the minimum total length. The overall complexity is O(n) time and O(n) space.

Is Find Two Non-overlapping Sub-arrays Each With Target Sum asked at Google/Amazon/Meta?

Problems involving prefix sums, sliding windows, and non-overlapping subarrays appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to combine prefix sum detection with dynamic programming or interval constraints. Interviewers typically expect an O(n) solution.

What data structure is used in Find Two Non-overlapping Sub-arrays Each With Target Sum?

The main data structures are a hash map for prefix sum lookups and an auxiliary array for dynamic programming that stores the shortest valid subarray length up to each index. Some solutions also use two pointers for a sliding window when the array contains only positive integers.

What is the time complexity of Find Two Non-overlapping Sub-arrays Each With Target Sum?

The optimal algorithms run in O(n) time because the array is scanned once while maintaining prefix sums or a sliding window. Hash map lookups and updates occur in constant time. Space complexity is O(n) due to the prefix map and the auxiliary array storing the minimum subarray length seen so far.

Description Hints 3 Solution Video 14:44

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

Q: Is Find Two Non-overlapping Sub-arrays Each With Target Sum easy or hard?

The problem is rated Medium because it combines multiple techniques: prefix sums, hash maps, and dynamic programming style state tracking. Identifying a single target-sum subarray is straightforward, but enforcing non-overlap and minimizing total length adds complexity. Efficient solutions require O(n) time reasoning.

Q: How to solve Find Two Non-overlapping Sub-arrays Each With Target Sum in O(n)?

Maintain a running prefix sum and store previously seen sums in a hash map. When prefixSum - target appears in the map, a valid subarray ending at the current index is found. Track the length of that subarray and combine it with the shortest valid subarray ending earlier using a DP array. This guarantees non-overlapping segments and keeps the total length minimal in linear time.

Medium49.5% acceptance1 company

You are 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]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: 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
Explanation: We have only one sub-array of sum = 6.

Constraints:

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

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Let's create two arrays prefix and suffix where prefix[i] is the minimum length of sub-array ends before i and has sum = k, suffix[i] is the minimum length of sub-array starting at or after i and has sum = k.

Hint 2

The answer we are searching for is min(prefix[i] + suffix[i]) for all values of i from 0 to n-1 where n == arr.length.

Hint 3

If you are still stuck with how to build prefix and suffix, you can store for each index i the length of the sub-array starts at i and has sum = k or infinity otherwise, and you can use it to build both prefix and suffix.

14:44

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution