LeetCode 1546: Maximum Number of Non-Overlapping Subarrays With Sum Equals Target Solution

Master LeetCode problem 1546 (Maximum Number of Non-Overlapping Subarrays With Sum Equals Target), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

Array Hash Table Greedy Prefix Sum

Problem Explanation

Explanation:

To solve this problem, we can utilize a hashmap to keep track of the cumulative sum of the subarrays seen so far. We iterate through the array and update the cumulative sum. If the difference between the current cumulative sum and the target sum exists in the hashmap, it means there is a subarray with the required sum. We keep track of the length of the subarray by updating a variable count, which is incremented when we find a valid subarray. We also update the hashmap with the current cumulative sum.

Algorithm:

Initialize a hashmap map with key 0 and value 0.
Initialize variables count and cumSum to 0.
Iterate through the input array nums:
- Update cumSum with the current element's value.
- If cumSum - target exists in map, increment count and update cumSum to 0.
- Update map with the current cumSum.
Return count.

Time Complexity:

The time complexity of this solution is O(n) where n is the number of elements in the input array nums.

Space Complexity:

The space complexity of this solution is O(n) where n is the number of elements in the input array nums.

Solution Code

import java.util.HashMap;

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int count = 0, cumSum = 0;
        
        for (int num : nums) {
            cumSum += num;
            if (map.containsKey(cumSum - target)) {
                count++;
                cumSum = 0;
            }
            map.put(cumSum, map.getOrDefault(cumSum, 0) + 1);
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1546 (Maximum Number of Non-Overlapping Subarrays With Sum Equals Target)?

This page provides optimized solutions for LeetCode problem 1546 (Maximum Number of Non-Overlapping Subarrays With Sum Equals Target) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1546 (Maximum Number of Non-Overlapping Subarrays With Sum Equals Target)?

The time complexity for LeetCode 1546 (Maximum Number of Non-Overlapping Subarrays With Sum Equals Target) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1546 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1546 in Java, C++, or Python.

Back to LeetCode Solutions