Quick Overview

Given an integer array that may contain negative numbers and a target k, return the length of the longest contiguous subarray whose sum equals k, or 0 when none exists. Tests reasoning about subarray sums with mixed signs and handling large inputs efficiently.

Length of the Longest Contiguous Subarray Summing to a Target

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given an integer array `nums` and an integer `k`, return the length of the longest contiguous subarray whose elements sum to exactly `k`. If no such subarray exists, return `0`. ### Function Signature ```python def longest_subarray_with_sum(nums: list[int], k: int) -> int: ``` ### Rules - A subarray is a non-empty contiguous block `nums[i..j]` with `i <= j`. - Elements may be negative, zero or positive. - Only the length is returned, so it does not matter which of several longest qualifying subarrays you have in mind. ### Constraints - `1 <= len(nums) <= 2 * 10^5` - `-10^4 <= nums[i] <= 10^4` - `-10^9 <= k <= 10^9` - Every subarray sum lies within `[-2 * 10^9, 2 * 10^9]`, which fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: nums = [2, -1, 3, 1, -2, 2], k = 3 Output: 5 ``` Both `[2, -1, 3, 1, -2]` and `[-1, 3, 1, -2, 2]` sum to 3. The whole array sums to 5, so no subarray of length 6 qualifies. **Example 2** ```text Input: nums = [1, 2, 3], k = 7 Output: 0 ``` The largest possible sum is 6, so no subarray sums to 7. **Example 3** ```text Input: nums = [0, 0, 0], k = 0 Output: 3 ``` The whole array sums to 0.

Overview: Given an integer array that may contain negative numbers and a target k, return the length of the longest contiguous subarray whose sum equals k, or 0 when none exists. Tests reasoning about subarray sums with mixed signs and handling large inputs efficiently.

Given an integer array `nums` and an integer `k`, return the length of the longest contiguous subarray whose elements sum to exactly `k`. If no such subarray exists, return `0`. Implement `longest_subarray_with_sum(nums, k)`. ### Rules - A subarray is a non-empty contiguous block `nums[i..j]` with `i <= j`. - Elements may be negative, zero or positive. - Only the length is returned, so it does not matter which of several longest qualifying subarrays you have in mind. ### Constraints - `1 <= len(nums) <= 2 * 10^5` - `-10^4 <= nums[i] <= 10^4` - `-10^9 <= k <= 10^9` - Every subarray sum lies within `[-2 * 10^9, 2 * 10^9]`, which fits in a 32-bit signed integer. The elements, `k`, every subarray sum and the returned length all fit in a 32-bit signed integer, so the Java and C++ signatures use `int`. A value obtained by subtracting `k` from such a sum can reach `3 * 10^9` in magnitude, which exceeds `2^31 - 1`; if your approach computes one, use 64-bit integers for it (`long` in Java, `long long` in C++). ### Example 1 ```text Input: nums = [2, -1, 3, 1, -2, 2], k = 3 Output: 5 ``` Both `[2, -1, 3, 1, -2]` and `[-1, 3, 1, -2, 2]` sum to 3. The whole array sums to 5, so no subarray of length 6 qualifies. ### Example 2 ```text Input: nums = [1, 2, 3], k = 7 Output: 0 ``` The largest possible sum is 6, so no subarray sums to 7.

Constraints

  • 1 <= len(nums) <= 2 * 10^5
  • -10^4 <= nums[i] <= 10^4
  • -10^9 <= k <= 10^9
  • Every subarray sum lies within [-2 * 10^9, 2 * 10^9], which fits in a 32-bit signed integer.

Examples

Input: ([2, -1, 3, 1, -2, 2], 3)

Expected Output: 5

Explanation: Source example 1: [2, -1, 3, 1, -2] and [-1, 3, 1, -2, 2] tie at length 5; the whole array sums to 5.

Input: ([1, 2, 3], 7)

Expected Output: 0

Explanation: Source example 2: the largest sum is 6, so no subarray sums to 7.

Hints

  1. Elements may be negative or zero, so a block's sum can fall as the block grows; do not assume that lengthening a block only increases its sum.
  2. Only the length is returned: when several different blocks share the maximum length the answer is that length, and when no block sums to k the answer is 0.
  3. A qualifying block may start at index 0, end at the last index, or cover the whole array; make sure your approach does not miss any of these positions.

Loading coding console...

Show the approach

Approach

Algorithm: scan nums once while maintaining the running prefix sum P (the sum of nums[0..i]) and a hash map from each prefix-sum value to the FIRST index at which it occurred. The map is seeded with value 0 at index -1, which represents the empty prefix. At index i, after adding nums[i] to P, look up P - k: if it was first seen at index s, then nums[s+1..i] sums to exactly k and has length i - s, so update the best length. Only after the lookup, record P at index i if P has never been seen; an existing entry is never overwritten.

Invariant: before processing index i, the map holds, for every value v among the prefix sums of lengths 0..i, the smallest prefix position (shifted by -1) whose sum is v.

Correctness: the subarray nums[s+1..i] sums to k exactly when prefix(i) - prefix(s) = k, i.e. prefix(s) = P - k. For a fixed right end i, the longest such subarray uses the smallest s, which is exactly what the first-occurrence map returns; taking the maximum over all right ends therefore gives the longest qualifying subarray overall, and 0 when no lookup ever succeeds. Looking up before inserting guarantees s < i, so every counted subarray is non-empty. Because only lengths are compared, which of several equally long subarrays is found does not matter.

Why simpler ideas fail: elements can be negative, so a window's sum is not monotonic in its length and a grow/shrink sliding window can discard the correct start (for example [5, -3, 1] with k = 3). Overwriting a prefix value with a later index shortens answers (for example [1, -1, 1, -1, 1] with k = 1), and forgetting the empty prefix misses every subarray that starts at index 0.

Edge cases: a single element (answer 1 or 0), no qualifying subarray (0), k = 0 with runs of zeros, qualifying subarrays at the start, end, middle or covering the whole array, and k at the +/-10^9 bounds. Every subarray sum fits in 32 bits, but P - k can reach 3 * 10^9 in magnitude, so Java and C++ keep P and the lookup key in 64-bit integers.

Time complexity:
O(n)
Space complexity:
O(n)