Maximum Size Subarray Sum Equals k - Practice Coding Problems

Maximum Size Subarray Sum Equals k - Problem

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.

A subarray is a contiguous sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1, 0, 1], k = 1

› Output: 2

💡 Note: The subarray [0, 1] starting at index 1 has sum 1 and length 2. Single element subarrays [1] also have sum 1 but length 1, so maximum is 2.

Example 2 — No Valid Subarray

$ Input: nums = [1, 2, 3], k = 10

› Output: 0

💡 Note: No subarray sums to 10, so return 0.

Example 3 — Negative Numbers

$ Input: nums = [-2, -1, 2, 1], k = 1

› Output: 2

💡 Note: The subarray [2, 1] at indices 2-3 has sum 1 and length 2. Also [-1, 2] has sum 1 and length 2.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁷ ≤ k ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers and target sum k

Process

Find all subarrays that sum to k

Output

Return maximum length found

Key Takeaway

🎯 Key Insight: Prefix sums with hash map allow finding target sum subarrays in O(n) time

Asked in

F Facebook 15 G Google 12 A Amazon 8

The optimal solution uses prefix sums with a hash map to find the maximum length subarray with sum k in O(n) time. The key insight is that if prefix_sum[j] - prefix_sum[i-1] = k, then subarray from i to j has sum k. Best approach is prefix sum with hash map: Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and find the longest one with sum k
Prefix Sum with Hash Map	O(n)	O(n)	Use prefix sums and hash map to find subarrays with target sum in O(n) time

Brute Force - Check All Subarrays — Algorithm Steps

For each starting index i
For each ending index j from i onwards
Calculate sum from i to j
If sum equals k, update max length

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Check all subarrays starting from index 0

Calculate

Sum each subarray and check if equals k

Track

Keep track of maximum length found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int maxLen = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            int currentSum = 0;
            for (int l = i; l <= j; l++) {
                currentSum += nums[l];
            }
            if (currentSum == k) {
                int len = j - i + 1;
                if (len > maxLen) {
                    maxLen = len;
                }
            }
        }
    }
    
    return maxLen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops - outer two for start/end indices, inner one for sum calculation

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler