Is Maximum Size Subarray Sum Equals k easy or hard?

The problem is classified as Medium difficulty. The brute force idea is straightforward, but identifying the prefix sum plus hash map optimization requires familiarity with common subarray sum patterns.

Maximum Size Subarray Sum Equals k Python/Java solution

Implement the prefix sum technique while storing sums in a dictionary (Python) or HashMap (Java). Track the earliest index for each prefix sum and update the maximum length whenever prefixSum - k is found in the map. The algorithm runs in O(n) time and O(n) space.

How to solve Maximum Size Subarray Sum Equals k in O(n)?

Maintain a running prefix sum while iterating through the array. Use a hash map to store the first index where each prefix sum occurs. For each element, check if prefixSum - k exists in the map. If it does, the distance between indices gives a subarray with sum k, allowing you to update the maximum length.

What is the best approach for Maximum Size Subarray Sum Equals k?

The most efficient approach uses prefix sums combined with a hash map. As you scan the array, store the earliest index for each prefix sum. If the current prefix sum minus k has appeared before, a valid subarray exists. This method runs in O(n) time with O(n) space.

Is Maximum Size Subarray Sum Equals k asked at Google/Amazon/Meta?

This problem appears frequently in technical interviews at companies like Amazon, Google, and Meta because it tests understanding of prefix sums, hash maps, and subarray patterns. Variants of this question also appear in system-level interview rounds.

What data structure is used in Maximum Size Subarray Sum Equals k?

The key data structure is a hash table (hash map) that stores prefix sums and their earliest indices. This enables constant-time lookups to determine whether a previous prefix sum can form a subarray with total sum k.

What is the time complexity of Maximum Size Subarray Sum Equals k?

The optimal prefix sum and hash map solution runs in O(n) time because the array is traversed once and each lookup in the hash table is O(1) on average. The brute force approach requires checking every subarray, which results in O(n²) time.

Description Hints 3 Solution Video 15:14

325. Maximum Size Subarray Sum Equals k

Medium50.8% acceptance8 companiesPremium elsewhere, free here

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Constraints:

1 <= nums.length <= 2 * 10⁵
-10⁴ <= nums[i] <= 10⁴
-10⁹ <= k <= 10⁹

Asked at 8 companies

Palantir Meta Tiktok Oracle Goldman Sachs

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Compute the prefix sum array where psum[i] is the sum of all the elements from 0 to i.

Hint 2

At each index i, the sum of the prefix is psum[i], so we are searching for the index x where psum[x] = psum[i] - k. The subarray [x + 1, i] will be of sum k.

Hint 3

Use a hashmap to get the index x efficiently or to determine that it does not exist.

15:14

Still stuck?Read the written solution, or watch a walkthrough.

Open solution