D
DevExCode

LeetCode 325: Maximum Size Subarray Sum Equals k Solution

Master LeetCode problem 325 (Maximum Size Subarray Sum Equals k), 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.

325. Maximum Size Subarray Sum Equals k

Medium
ArrayHash TablePrefix Sum

Problem Explanation

Explanation:

To solve this problem, we can use a hashmap to store the cumulative sum up to each index. We iterate through the array keeping track of the cumulative sum and store it in the hashmap along with its index. At each index, we check if the current sum minus the target k exists in the hashmap. If it does, we update the maximum length of the subarray. We return the maximum length of the subarray that sums to k.

Algorithm:

  1. Initialize a hashmap to store cumulative sums and their corresponding indices.
  2. Initialize variables maxLen to store the maximum length of the subarray and sum to store the cumulative sum.
  3. Iterate through the array:
    • Update sum with the current element.
    • If sum - k is present in the hashmap, update maxLen if necessary.
    • If sum is not present in the hashmap, store it with its index.
  4. Return maxLen.

Time Complexity: O(n) - We iterate through the array once. Space Complexity: O(n) - We use a hashmap to store cumulative sums.

:

Solution Code

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxLen = 0;
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) {
                maxLen = i + 1;
            } else if (map.containsKey(sum - k)) {
                maxLen = Math.max(maxLen, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        
        return maxLen;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 325 (Maximum Size Subarray Sum Equals k)?

This page provides optimized solutions for LeetCode problem 325 (Maximum Size Subarray Sum Equals k) 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 325 (Maximum Size Subarray Sum Equals k)?

The time complexity for LeetCode 325 (Maximum Size Subarray Sum Equals k) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 325 on DevExCode?

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

Back to LeetCode Solutions