Scale Engineer

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Med
#1424Time: O(N^2), where N is the length of `nums`. The nested loops (one for `i` and one for `j`) result in a quadratic time complexity.Space: O(N), where N is the length of `nums`, for the `dp` array.
Patterns
GreedyPrefix Sum
Data structures
ArrayHash Table

Prompt

Given an array nums and an integer target, return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

 

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 0 <= target <= 106

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define dp[i] as the maximum number of non-overlapping subarrays with a sum equal to target that can be found in the suffix of the array starting from index i. The final answer will be dp[0], which is computed by iterating backward through the array and considering all possible subarrays.

Algorithm

  • Create a dp array of size n + 1, where n is the length of nums. Initialize all its values to 0.
  • Iterate i from n - 1 down to 0:
    • First, assume we don't start a subarray at i. The result would be the same as for the subarray starting at i+1. So, set dp[i] = dp[i + 1].
    • Initialize current_sum = 0.
    • Then, try to find a subarray starting at i. Iterate j from i to n - 1:
      • Add nums[j] to current_sum.
      • If current_sum equals target, we've found a valid subarray nums[i...j].
      • This contributes 1 to the count, plus the maximum number of subarrays we can find in the remaining part of the array, which starts at index j + 1. This is given by dp[j + 1].
      • Update dp[i] to be the maximum of its current value and 1 + dp[j + 1].
  • The final answer is dp[0], which represents the maximum number of subarrays for the entire array nums[0...n-1].

Walkthrough

We build a dp array of size n+1, where n is the length of nums. dp[i] will store the result for the subarray nums[i:]. We initialize dp[n] to 0, as there are no subarrays in an empty array.

We iterate backward from i = n-1 down to 0. For each index i, we have two choices:

  1. Don't start a subarray at index i: In this case, the number of subarrays is the same as the number we can find starting from i+1, which is dp[i+1]. We set dp[i] = dp[i+1] as a baseline.
  2. Start a subarray at index i: We iterate with a second pointer j from i to n-1, calculating the sum of nums[i...j]. If this sum equals target, we have found a valid subarray. This gives us 1 subarray plus the maximum number of subarrays we can find in the rest of the array, which starts from index j+1. This value is 1 + dp[j+1]. We then update dp[i] with the maximum value found among all such valid subarrays starting at i.

After the loops complete, dp[0] contains the maximum number of non-overlapping subarrays for the entire array.

class Solution {    public int maxNonOverlapping(int[] nums, int target) {        int n = nums.length;        int[] dp = new int[n + 1];                for (int i = n - 1; i >= 0; i--) {            // Option 1: Skip the element at index i            dp[i] = dp[i + 1];                        long currentSum = 0;            // Option 2: Find a subarray starting at i            for (int j = i; j < n; j++) {                currentSum += nums[j];                if (currentSum == target) {                    // Found a subarray nums[i...j].                    // The result is 1 + max subarrays from index j+1.                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);                }            }        }                return dp[0];    }}

Complexity

Time

O(N^2), where N is the length of `nums`. The nested loops (one for `i` and one for `j`) result in a quadratic time complexity.

Space

O(N), where N is the length of `nums`, for the `dp` array.

Trade-offs

Pros

  • It is a straightforward and systematic way to explore all possibilities, guaranteeing an optimal solution.

  • The logic is relatively easy to understand for those familiar with dynamic programming.

Cons

  • The O(N^2) time complexity is inefficient for large inputs as specified by the constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error.

Solutions

class Solution { public int maxNonOverlapping ( int [] nums , int target ) { int ans = 0 , n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { Set < Integer > vis = new HashSet <>(); int s = 0 ; vis . add ( 0 ); while ( i < n ) { s += nums [ i ]; if ( vis . contains ( s - target )) { ++ ans ; break ; } ++ i ; vis . add ( s ); } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem