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

The optimal solution for Find Two Non-overlapping Sub-arrays Each With Target Sum runs in O(n) time and uses O(n) space. The complexity is O(n) because we only traverse the array a constant number of times to build the prefix and suffix arrays.

What is the brute force solution for Find Two Non-overlapping Sub-arrays Each With Target Sum?

The brute force approach for Find Two Non-overlapping Sub-arrays Each With Target Sum is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking all possible pairs of sub-arrays to see if they meet the target sum. This is straightforward but inefficient, as it examines every combination. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Find Two Non-overlapping Sub-arrays Each With Target Sum?

Find Two Non-overlapping Sub-arrays Each With Target Sum uses the following concepts: Array, Hash Table, Binary Search, Dynamic Programming, Sliding Window. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Find Two Non-overlapping Sub-arrays Each With Target Sum?

Clearly explain your thought process before coding. Consider edge cases and constraints upfront. Use comments to clarify complex logic in your code.

What are common mistakes when solving Find Two Non-overlapping Sub-arrays Each With Target Sum?

Not considering edge cases where no valid sub-arrays exist. Failing to properly manage indices when checking for non-overlapping sub-arrays.

#1477

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

Medium

ArrayHash TableBinary SearchDynamic ProgrammingSliding WindowHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses prefix and suffix arrays to efficiently track the minimum lengths of sub-arrays that sum to the target. This allows us to find two non-overlapping sub-arrays in linear time.

⚙️

Algorithm

4 steps

1Step 1: Create a prefix array where prefix[i] stores the minimum length of a sub-array ending before index i that sums to the target.
2Step 2: Create a suffix array where suffix[i] stores the minimum length of a sub-array starting at or after index i that sums to the target.
3Step 3: Iterate through the array and for each index, calculate the minimum combined length of prefix[i] and suffix[i].
4Step 4: Return the minimum combined length found, or -1 if no valid pairs exist.

solution.py41 lines

1# Full working Python code
2
3def minSumOfLengths(arr, target):
4    n = len(arr)
5    prefix = [float('inf')] * n
6    suffix = [float('inf')] * n
7    current_sum = 0
8    left = 0
9
10    for right in range(n):
11        current_sum += arr[right]
12        while current_sum > target:
13            current_sum -= arr[left]
14            left += 1
15        if current_sum == target:
16            prefix[right] = right - left + 1
17    
18    min_length = float('inf')
19    for i in range(n):
20        if i > 0:
21            prefix[i] = min(prefix[i], prefix[i-1])
22
23    current_sum = 0
24    right = n - 1
25    for left in range(n - 1, -1, -1):
26        current_sum += arr[left]
27        while current_sum > target:
28            current_sum -= arr[right]
29            right -= 1
30        if current_sum == target:
31            suffix[left] = right - left + 1
32
33    for i in range(n):
34        if i > 0:
35            suffix[i] = min(suffix[i], suffix[i + 1])
36
37    for i in range(n):
38        if prefix[i] != float('inf') and suffix[i] != float('inf'):
39            min_length = min(min_length, prefix[i] + suffix[i])
40
41    return min_length if min_length != float('inf') else -1

ℹ

Complexity note: The complexity is O(n) because we only traverse the array a constant number of times to build the prefix and suffix arrays.

1Using prefix and suffix arrays allows for efficient tracking of sub-array lengths.
2Non-overlapping conditions can be managed by careful indexing.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.