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

Original problem link: https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/description/

In this problem, we’re given an array and a target sum and asked to find the maximum number of non-overlapping subarrays that sum to the target.

First, we compile a prefix sums array to compute subarray sums faster. We can do the problem using an O(n²) to find all the valid subarrays ending at an index i, but that is a very slow solution. We can speed it up by tracking a lastTaken variable representing the end of the latest subarray (or null if we haven’t taken any), and make it O(n) by tracking all the previously seen prefix sums and their indices in a map to check if there are valid subarrays in O(1) time. We loop through and keep checking for valid subarrays.

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int[] prefixSums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i > 0) {
                prefixSums[i] = prefixSums[i - 1] + nums[i];
            } else {
                prefixSums[i] = nums[i];
            }
        }

        Integer lastTaken = null;
        int validSubarrays = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (prefixSums[i] == target && lastTaken == null) {
                validSubarrays++;
                lastTaken = i;
            } else if (lastTaken == null && map.containsKey(prefixSums[i] - target)) {
                validSubarrays++;
                lastTaken = i;
            } else if (lastTaken != null && map.containsKey(prefixSums[i] - target) && map.get(prefixSums[i] - target) >= lastTaken) {
                validSubarrays++;
                lastTaken = i;
            }
            map.put(prefixSums[i], i);
        }

        return validSubarrays;
    }
}