Jobs

Interviews

Discussions

Maximum Size Subarray Sum Equals k

Medium

Palantir

0 views

Topics:

ArraysSliding Windows

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there isn't 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⁹

Maximum Size Subarray Sum Equals k

Medium

Palantir

0 views

Topics:

ArraysSliding Windows

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there isn't 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⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array `nums`? Could they be negative, zero, or only positive?
What is the expected behavior if the input array `nums` is null or empty?
What is the maximum size of the input array `nums`?
If multiple subarrays sum to `k` and have the same maximum length, is any of them acceptable as a solution?
What is the range of possible values for `k`? Could `k` be negative, zero, or only positive?

Brute Force Solution

Approach

The brute force strategy involves checking every possible group of consecutive numbers within the given list. We'll examine all possible groups, from the smallest to the largest, to find the one with the biggest span that adds up to the target number.

Here's how the algorithm would work step-by-step:

Start with the first number in the list and consider it as a group by itself.
Calculate the sum of this single-number group. If it equals the target number, remember this group's span (which is just 1).
Next, consider the first two numbers as a group.
Calculate the sum of this two-number group. If it equals the target number, remember this group's span (which is 2).
Keep expanding the group by one number at a time, always starting from the first number in the list.
For each group, check if the sum matches the target number. If it does, note the span.
After checking all groups starting from the first number, repeat the process starting from the second number in the list.
Continue this process, shifting the starting point one number at a time, until you've checked every possible group of consecutive numbers.
Finally, compare the spans of all the groups that added up to the target number, and choose the largest span. That span represents the maximum size subarray.

Code Implementation

def find_max_subarray_length(numbers, target):
    max_length = 0
    list_length = len(numbers)

    # Iterate through all possible start indices
    for start_index in range(list_length):
        # Iterate through all possible end indices for each start index
        for end_index in range(start_index, list_length):
            current_sum = 0

            # Calculate the sum of the current subarray
            for index in range(start_index, end_index + 1):
                current_sum += numbers[index]

            # Check if the current subarray sum equals the target
            if current_sum == target:
                # Update max length if current subarray is longer
                subarray_length = end_index - start_index + 1
                if subarray_length > max_length:
                    max_length = subarray_length

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the array with a nested loop structure to examine all possible subarrays. The outer loop iterates from the first to the last element (n elements). For each starting element in the outer loop, the inner loop calculates the sum of all possible subarrays starting from that element. The number of inner loop iterations decreases with each outer loop iteration, leading to approximately n*(n+1)/2 operations. This simplifies to O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through all possible subarrays, calculating sums and tracking the maximum size. While sums are calculated, they are done on the fly and not stored persistently. Only a few variables (e.g., to store the current sum, the maximum length found so far) are used. Therefore, the auxiliary space used remains constant regardless of the input array size N, resulting in O(1) space complexity.

Optimal Solution

Approach

The goal is to find the longest continuous group of numbers that add up to a specific target. Instead of checking every possible group, we'll use a clever way to remember sums we've already seen, allowing us to quickly calculate the sum of new groups.

Here's how the algorithm would work step-by-step:

Start by keeping track of a running total as you go through the numbers from left to right.
Also, keep a record of each running total you've seen so far, along with where you first saw that total.
As you move along, figure out what running total you'd need to have seen earlier to reach the target when you add the current numbers to it.
If you've seen that required total before, that means the numbers in between that earlier point and your current spot add up to the target! Find the length of this group.
Keep track of the longest group you find that adds up to the target.
If you reach a running total you haven't seen before, make sure to add it to your record, along with where you saw it.
By remembering past totals, you avoid recalculating sums for every possible group, allowing you to find the longest group efficiently.

Code Implementation

def max_subarray_len(nums, target):
    running_sum = 0
    max_length = 0
    sum_index_map = {}

    # Initialize the map to handle cases where the subarray starts from index 0
    sum_index_map[0] = -1

    for i, num in enumerate(nums):
        running_sum += num

        # Check if (running_sum - target) exists in the map
        required_sum = running_sum - target

        if required_sum in sum_index_map:
            # Found a subarray with the target sum.
            length = i - sum_index_map[required_sum]
            max_length = max(max_length, length)

        # Store the current sum and its index if it's not already in the map
        if running_sum not in sum_index_map:
            # Keep track of the first occurence of each sum
            sum_index_map[running_sum] = i

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to calculate the running sum. Inside the loop, it performs constant-time operations: checking if a value exists in the hash map (prefix sums) and updating the maximum length. The hash map operations (put and get) take O(1) time on average. Therefore, the time complexity is dominated by the single iteration through the array, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm uses a hash map to store the running total and its corresponding index. In the worst-case scenario, where no subarray sums to k and all running sums are unique, the hash map will store N key-value pairs, where N is the number of elements in the input array. Thus, the auxiliary space used by the hash map grows linearly with the input size. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no subarrays to evaluate.
Array with one element that equals k	Return 1, as the single element satisfies the condition.
Array with one element that doesn't equal k	Return 0, as no valid subarray exists.
Array with all zeros and k = 0	Return the length of the array as the entire array sums to k.
Array with all zeros and k != 0	Return 0, as no subarray can sum to k.
Array containing negative numbers and zeros, k = 0	The hashmap efficiently handles negative prefixes and zeros to identify valid subarrays.
Array with extremely large numbers that could cause integer overflow when summing	Use a data type like long if integer overflow is possible based on constraints.
No subarray sums to k	The algorithm should correctly iterate and return 0 when no such subarray is found.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array `nums`? Could they be negative, zero, or only positive?
What is the expected behavior if the input array `nums` is null or empty?
What is the maximum size of the input array `nums`?
If multiple subarrays sum to `k` and have the same maximum length, is any of them acceptable as a solution?
What is the range of possible values for `k`? Could `k` be negative, zero, or only positive?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the list and consider it as a group by itself.
Calculate the sum of this single-number group. If it equals the target number, remember this group's span (which is just 1).
Next, consider the first two numbers as a group.
Calculate the sum of this two-number group. If it equals the target number, remember this group's span (which is 2).
Keep expanding the group by one number at a time, always starting from the first number in the list.
For each group, check if the sum matches the target number. If it does, note the span.
After checking all groups starting from the first number, repeat the process starting from the second number in the list.
Continue this process, shifting the starting point one number at a time, until you've checked every possible group of consecutive numbers.
Finally, compare the spans of all the groups that added up to the target number, and choose the largest span. That span represents the maximum size subarray.

Code Implementation

def find_max_subarray_length(numbers, target):
    max_length = 0
    list_length = len(numbers)

    # Iterate through all possible start indices
    for start_index in range(list_length):
        # Iterate through all possible end indices for each start index
        for end_index in range(start_index, list_length):
            current_sum = 0

            # Calculate the sum of the current subarray
            for index in range(start_index, end_index + 1):
                current_sum += numbers[index]

            # Check if the current subarray sum equals the target
            if current_sum == target:
                # Update max length if current subarray is longer
                subarray_length = end_index - start_index + 1
                if subarray_length > max_length:
                    max_length = subarray_length

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by keeping track of a running total as you go through the numbers from left to right.
Also, keep a record of each running total you've seen so far, along with where you first saw that total.
As you move along, figure out what running total you'd need to have seen earlier to reach the target when you add the current numbers to it.
If you've seen that required total before, that means the numbers in between that earlier point and your current spot add up to the target! Find the length of this group.
Keep track of the longest group you find that adds up to the target.
If you reach a running total you haven't seen before, make sure to add it to your record, along with where you saw it.
By remembering past totals, you avoid recalculating sums for every possible group, allowing you to find the longest group efficiently.

Code Implementation

def max_subarray_len(nums, target):
    running_sum = 0
    max_length = 0
    sum_index_map = {}

    # Initialize the map to handle cases where the subarray starts from index 0
    sum_index_map[0] = -1

    for i, num in enumerate(nums):
        running_sum += num

        # Check if (running_sum - target) exists in the map
        required_sum = running_sum - target

        if required_sum in sum_index_map:
            # Found a subarray with the target sum.
            length = i - sum_index_map[required_sum]
            max_length = max(max_length, length)

        # Store the current sum and its index if it's not already in the map
        if running_sum not in sum_index_map:
            # Keep track of the first occurence of each sum
            sum_index_map[running_sum] = i

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no subarrays to evaluate.
Array with one element that equals k	Return 1, as the single element satisfies the condition.
Array with one element that doesn't equal k	Return 0, as no valid subarray exists.
Array with all zeros and k = 0	Return the length of the array as the entire array sums to k.
Array with all zeros and k != 0	Return 0, as no subarray can sum to k.
Array containing negative numbers and zeros, k = 0	The hashmap efficiently handles negative prefixes and zeros to identify valid subarrays.
Array with extremely large numbers that could cause integer overflow when summing	Use a data type like long if integer overflow is possible based on constraints.
No subarray sums to k	The algorithm should correctly iterate and return 0 when no such subarray is found.