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

MediumArrayHash TableBinary SearchDynamic ProgrammingSliding Window
Leetcode Link

Problem Description

The problem requires finding two non-overlapping sub-arrays within a given array of integers, arr, where each sub-array sums up to a specific value, target. To qualify, neither of the sub-arrays should share any elements with the other, effectively meaning they cannot overlap. The goal is to find such pair of sub-arrays where the combined length of both sub-arrays is as small as possible. If it's impossible to find such pair of sub-arrays, the function should return -1.

Intuition

The solution to this problem involves dynamic programming and the use of a hashmap to track the prefix sums.

  1. The intuition behind the dynamic programming approach is that at any point in the array, we want to know the length of the smallest sub-array ending at that point which sums to target. This can help us efficiently update the answer when we find the next sub-array that sums to target.

  2. To efficiently find if a sub-array sums to target, we can use a hashmap to store the sum of all elements up to the current index (s), as the key, with the value being the index itself. If s - target is in the hashmap, it means there is a valid sub-array ending at the current index which sums to target.

  3. While iterating through the array, we keep updating our hashmap with the current sum and index, and we also keep track of the smallest sub-array found so far that sums to target using an array f.

  4. Whenever a new sub-array is found (checking if s - target exists in the hashmap), we calculate the minimum length of a sub-array that sums to target that ends at our current index. Simultaneously, we try to update the global answer, which is the sum of lengths of two such sub-arrays.

The key realization is that we do not need to store the actual sub-arrays. Instead, storing their lengths and endpoints suffices to solve the problem. By maintaining a running minimum length sub-array and utilizing the hashmap to efficiently query the existence of a previous sub-array sum, we can determine the optimal pair of sub-arrays that fulfill the conditions.

Learn more about Binary Search, Dynamic Programming and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The implementation utilizes a hashmap and a dynamic programming (DP) table. Here is a step-by-step breakdown:

  1. Hashmap for Prefix Sums:

    • A hashmap d is used to store the sum of all elements up to the current index as keys (s presents the current sum) and their corresponding indices as values. This helps quickly check if there is a sub-array ending at the current index that sums up to target.

  2. Initializing Variables:

    • s is the prefix sum initialized to 0.
    • n is the total number of elements in the array arr.
    • f is an array of size n+1 initialized to inf (infinity). f[i] will hold the length of the smallest sub-array ending before or at index i, which has a sum of target.
    • ans is initialized to inf and will be used to store the minimum sum of the lengths of the two non-overlapping sub-arrays found so far.

  3. Iterating Through the Array:

    • Using a for loop, we iterate through the array starting from index 1 (since f is 1-indexed to simplify calculations).
    • We update the prefix sum s by adding the current element v.

  4. Dynamic Programming Table Update:

    • At each index i, the current value of f[i] is set to f[i - 1], ensuring that we carry forward the length of the smallest sub-array found so far up to the previous index.

  5. Finding and Updating Sub-arrays:

    • At each step of the iteration, we check if s - target is in the hashmap d.
    • If it is, that means we have encountered a sub-array, ending at the current index, which sums up to target.
    • We retrieve this sub-arrayโ€™s starting index j from the hashmap, and we calculate its length i - j.
    • Then we update f[i] as the minimum of the current value and the length of this new sub-array, which reflects the smallest sub-array summing to target up to index i.

  6. Updating the Answer:

    • While a new valid sub-array is found, we calculate the sum of its length with the smallest length of a sub-array found before it, i.e., f[j] + i - j.
    • If this sum is smaller than our current answer, we update the answer ans.

  7. Returning the Answer:

    • After iterating through the entire array, it is possible that no such pair of sub-arrays was found. We check this by comparing ans with n.
    • If ans is still inf or greater than n, it means no two non-overlapping sub-arrays with the sum target were found, and we return -1.
    • Otherwise, we return ans, which is the minimum sum of the lengths of the required two sub-arrays.

By the end of the loop, we either find the minimum sum of lengths of two non-overlapping sub-arrays that sum up to target, or determine that itโ€™s not possible to find such sub-arrays and return -1.

The use of the DP approach with a hashmap allows the algorithm to run efficiently by preventing repeated scanning of the array to check for sub-arrays that sum to target.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the array arr = [1, 2, 1, 2, 1, 2, 1] with target = 3.

  1. Hashmap for Prefix Sums: We will use a hashmap d to keep track of the prefix sums. Initially, d is empty.

  2. Initializing Variables:

    • s starts at 0.
    • n is 7, the total number of elements in arr.
    • f is an array [inf, inf, inf, inf, inf, inf, inf, inf] (1-indexed for a total of n+1 entries).
    • ans is initialized to inf.

  3. Iterating Through the Array: We iterate i from 1 to 7, and for each element v in arr, we update s.

  4. Dynamic Programming Table Update: At each index, f[i] is updated to be the minimum length of a valid sub-array up to that point.

  5. Finding and Updating Sub-arrays:

    • For each v, we calculate s and check if s - target exists in d.
    • If it does, we find the length of the current sub-array and update f[i] with the minimum.

  6. Updating the Answer:

    • Each time we find a valid sub-array, we calculate if it can contribute to a smaller ans.

  7. Returning the Answer: At the end, we return ans or -1 if not found.

Now, let's walk through with our array:

  • Initial step: d = {0: 0} to account for starting from a sum of 0 at index 0.
  • i = 1, arr[1] = 1. s = 1. f = [inf, inf, inf, inf, inf, inf, inf, inf], ans = inf. d = {0: 0, 1: 1}.
  • i = 2, arr[2] = 2, s = 3. We see s - target = 0 in d. Sub-array [1, 2] has sum 3. Update f[2] = min(inf, 2 - 0) = 2. d = {0: 0, 1: 1, 3: 2}.
  • i = 3, arr[3] = 1. s = 4. No change since s - target = 1 is not a prefix sum we've seen that ended at an index before i. d = {0: 0, 1: 1, 3: 2, 4: 3}.
  • i = 4, arr[4] = 2. s = 6. We find s-target = 3 in d. The sub-array [1, 2] happens again. Update f[4] = min(inf, 4 - 2) = 2. ans = min(inf, f[2] + 2) = min(inf, 2 + 2) = 4. d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4}.
  • i = 5, arr[5] = 1.s = 7. We find s-target = 4 in d. Update f[5] = min(inf, 5 - 3) = 2. Ans does not update because f[3] was inf. d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4, 7: 5}.
  • i = 6, arr[6] = 2. s = 9. We find s-target = 6 in d. Update f[6] = min(inf, 6 - 4) = 2. ans = min(4, f[4] + 2) = min(4, 2 + 2) = 4. d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4, 7: 5, 9: 6}.
  • i = 7, arr[7] = 1. s = 10. We find s-target = 7 in d. Update f[7] = min(inf, 7 - 5) = 2. ans = min(4, f[5] + 2) = min(4, 2 + 2) = 4. d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4, 7: 5, 9: 6, 10: 7}.

After completing the iteration, we have ans = 4, which corresponds to two non-overlapping sub-arrays [1, 2] and [1, 2], both sum up to 3, with a combined minimum length of 4. Hence, the function would return 4.

Solution Implementation

1class Solution:
2    def minSumOfLengths(self, arr: List[int], target: int) -> int:
3        # Create a dictionary to remember sum of all elements till index i (0-indexed)
4        sum_to_index = {0: -1}  # Adjusted for 0-index, starting with sum 0 at index -1
5        current_sum = 0  # Current sum of elements
6        final_result = float('inf')  # Initialize the final_result with infinity
7      
8        # Minimum length subarray ending at i that sums to target
9        min_len_subarray = [float('inf')] * len(arr)
10      
11        for i, value in enumerate(arr):
12            current_sum += value  # Update the current_sum with the current value
13          
14            # Update the min_len_subarray for the current position
15            if i > 0:
16                min_len_subarray[i] = min_len_subarray[i - 1]
17          
18            # If the current_sum minus target sum is in sum_to_index...
19            if current_sum - target in sum_to_index:
20                # Get the start index of subarray ending at current index i
21                start_index = sum_to_index[current_sum - target]
22                # Calculate the length of this subarray
23                current_len = i - start_index
24                # Update the minimum length subarray for the current position
25                min_len_subarray[i] = min(min_len_subarray[i], current_len)
26                # If this is not the first element, consider previous subarrays and update final_result
27                if start_index >= 0:
28                    final_result = min(final_result, min_len_subarray[start_index] + current_len)
29          
30            # Update the sum_to_index with the current_sum at current index i
31            sum_to_index[current_sum] = i
32      
33        # If final_result was updated and is not infinity, return it, else return -1
34        return final_result if final_result != float('inf') else -1
35
1class Solution {
2    public int minSumOfLengths(int[] arr, int target) {
3        // Hash map to store the cumulative sum up to the current index with the index itself
4        Map<Integer, Integer> cumSumToIndex = new HashMap<>();
5        cumSumToIndex.put(0, 0); // Initialization with sum 0 at index 0
6
7        int n = arr.length; // Length of the array
8        int[] minLengths = new int[n + 1]; // Array to store the minimum subarray length ending at i that sums up to target
9        final int infinity = 1 << 30; // A very large number treated as infinity
10        minLengths[0] = infinity; // Initialize with infinity since there's no subarray ending at index 0
11
12        int currentSum = 0; // Sum of the current subarray
13        int answer = infinity; // Initialize the answer with a large number representing infinity
14
15        // Loop through the array to find minimum subarrays
16        for (int i = 1; i <= n; ++i) {
17            int value = arr[i - 1]; // Value at current index in the array
18            currentSum += value; // Update the current sum
19          
20            // Copy the minimum subarray length found so far to current position
21            minLengths[i] = minLengths[i - 1];
22          
23            // If the (currentSum - target) is found before, update the minimum length and answer
24            if (cumSumToIndex.containsKey(currentSum - target)) {
25                int j = cumSumToIndex.get(currentSum - target); // Previous index where the cumulative sum was currentSum - target
26                minLengths[i] = Math.min(minLengths[i], i - j); // Update the minimum length for current index
27                answer = Math.min(answer, minLengths[j] + i - j); // Calculate the combined length and update the answer
28            }
29          
30            // Store the current cumulative sum and corresponding index
31            cumSumToIndex.put(currentSum, i);
32        }
33      
34        // If the answer is still infinity, no such subarrays are found; return -1. Else, return the found answer
35        return answer > n ? -1 : answer;
36    }
37}
38
1class Solution {
2public:
3    // This function finds two non-overlapping subarrays which sum to the target and returns
4    // the minimum sum of their lengths or -1 if there are no such subarrays.
5    int minSumOfLengths(vector<int>& arr, int target) {
6        unordered_map<int, int> prefixSumToIndex;
7        prefixSumToIndex[0] = -1; // Initialization with a base case
8
9        int prefixSum = 0, arraySize = arr.size();
10
11        // Initialize the array to store the minimum length of a subarray ending at each index i that sums to target.
12        vector<int> minLenToEndAt(arraySize + 1, INT_MAX);
13        minLenToEndAt[0] = INT_MAX; // No subarray ends before the array starts.
14
15        int minTotalLen = INT_MAX; // This will store the result.
16
17        for (int i = 0; i < arraySize; ++i) {
18            prefixSum += arr[i]; // Add the current element to the prefix sum.
19
20            // Update the minimum length for a subarray ending at the current index.
21            if (i > 0) {
22                minLenToEndAt[i + 1] = minLenToEndAt[i];
23            }
24
25            // If the prefix sum needed to achieve the target exists...
26            if (prefixSumToIndex.count(prefixSum - target)) {
27                int startIndex = prefixSumToIndex[prefixSum - target];
28                // Update the minimum length for this index.
29                minLenToEndAt[i + 1] = min(minLenToEndAt[i + 1], i - startIndex);
30
31                // If the previous subarray (ending at startIndex) is valid...
32                if (minLenToEndAt[startIndex + 1] < INT_MAX) {
33                    // Update the minimum total length.
34                    minTotalLen = min(minTotalLen, minLenToEndAt[startIndex + 1] + i - startIndex);
35                }
36            }
37
38            // Update or add the current prefix sum and its ending index to the map.
39            prefixSumToIndex[prefixSum] = i;
40        }
41
42        // If minTotalLen is not updated, return -1 to indicate no such subarrays exist.
43        return minTotalLen == INT_MAX ? -1 : minTotalLen;
44    }
45};
46
1// Initialize a helper function to find the minimum of two numbers
2function min(a: number, b: number): number {
3    return a < b ? a : b;
4}
5
6// This function finds two non-overlapping subarrays which sum to the target
7// and returns the minimum sum of their lengths, or -1 if there are no such
8// subarrays.
9function minSumOfLengths(arr: number[], target: number): number {
10    const prefixSumToIndex: Map<number, number> = new Map();
11    prefixSumToIndex.set(0, -1); // Initialization with a base case
12
13    let prefixSum: number = 0;
14    const arraySize: number = arr.length;
15
16    // Initialize the array to store the minimum length of a subarray ending at each index i that sums to target.
17    const minLenToEndAt: number[] = new Array(arraySize + 1).fill(Number.MAX_SAFE_INTEGER);
18    minLenToEndAt[0] = Number.MAX_SAFE_INTEGER; // No subarray ends before the array starts.
19
20    let minTotalLen: number = Number.MAX_SAFE_INTEGER; // This will store the result.
21
22    for (let i = 0; i < arraySize; ++i) {
23        prefixSum += arr[i]; // Add the current element to the prefix sum.
24
25        // Update the minimum length for a subarray ending at the current index.
26        if (i > 0) {
27            minLenToEndAt[i + 1] = minLenToEndAt[i];
28        }
29
30        // If the prefix sum needed to achieve the target exists...
31        const neededSum = prefixSum - target;
32        if (prefixSumToIndex.has(neededSum)) {
33            const startIndex = prefixSumToIndex.get(neededSum);
34            // Update the minimum length for this index.
35            minLenToEndAt[i + 1] = min(minLenToEndAt[i + 1], i - startIndex!);
36
37            // If the previous subarray (ending at startIndex) is valid...
38            if (minLenToEndAt[startIndex! + 1] < Number.MAX_SAFE_INTEGER) {
39                // Update the minimum total length.
40                minTotalLen = min(minTotalLen, minLenToEndAt[startIndex! + 1] + i - startIndex!);
41            }
42        }
43
44        // Update or add the current prefix sum and its ending index to the map.
45        prefixSumToIndex.set(prefixSum, i);
46    }
47
48    // If minTotalLen is not updated, return -1 to indicate no such subarrays exist.
49    return minTotalLen === Number.MAX_SAFE_INTEGER ? -1 : minTotalLen;
50}
51
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the number of elements in the array arr. This is because the code iterates through the array once, with constant-time operations performed for each element (such as updating a dictionary, arithmetic operations, and comparison operations).

More specifically:

  1. We have a single for loop iterating over arr, so we visit each element of arr once.
  2. For each element in the for loop, we are performing a dictionary lookup (or insertion) for operation d[s] = i and d[s - target] which is typically O(1) on average for a hash table.
  3. Assignments and comparisons like f[i] = f[i - 1] and ans = min(ans, f[j] + i - j) are O(1) operations. Therefore, combining these constant-time operations within a single loop over n elements, the overall time complexity is linear, represented by O(N).

Space Complexity

The space complexity of the code is O(N) as well. This can be attributed to two data structures that scale with the input size:

  1. The dictionary d which, in the worst case, could contain an entry for each prefix sum.
  2. The list f which contains n + 1 elements (as it keeps a record of the minimum length of a subarray for every index up to n).

Since both d and f only grow linearly with the input array's size, the space complexity is linear, represented by O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ