Skip to main content

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

medium

Find the max number of disjoint subarrays whose sums each equal target. Prefix-sum hash plus greedy reset — a 1D DP wearing the disguise of a sliding window.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6

Examples

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]), ([5,1,4,2,-9]), and ([3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Use prefix sums plus a hash set: a subarray ending at i sums to target if prefix[i] - target was a previously-seen prefix.

Hint 2

Greedy: as soon as you find a valid subarray, commit it and reset the hash set so it cannot overlap.

Hint 3

Re-seed the set with {0} after each commit because a new subarray can start immediately.

Solution approach

Reveal approach

Maintain a running prefix sum and a hash set of all prefix sums seen so far. Initialize the set with {0} (the empty prefix). Iterate the array: for each i compute prefix += nums[i]. If prefix - target is in the set, you have found a subarray ending at i whose sum is target. Increment the answer, then RESET the set to {0} and start the next prefix fresh at 0 — this enforces non-overlap because no future subarray can include any index up to i. Otherwise add the current prefix to the set and continue. Return the count. O(n) time, O(n) space. The reset move is what turns a counting problem into a greedy interval-scheduling proof.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • dynamic-programming
  • prefix-sum
  • hash-table
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Maximum Number of Non-Overlapping Subarrays With Sum Equals Target and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →