Longest Stretch Summing to K
MediumArrays & Hashing
Problem
A fitness tracker logs the net elevation change of each minute of a hike (up is positive, down is negative). You want the longest continuous period whose total climb is exactly k metres.
Given nums and k, return the length of the longest contiguous subarray whose sum equals k, or 0 if there is none.
Example 1
- Input:
- nums = [2, -1, 3, -2, 4, 1], k = 4
- Output:
- 4
[-1, 3, -2, 4] (indices 1–4) sums to 4. [3, -2, 4, 1] sums to 6, and no longer stretch hits 4.
Example 2
- Input:
- nums = [1, 2, 3], k = 10
- Output:
- 0
Constraints
- 1 ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
- -10^9 ≤ k ≤ 10^9
Hint
Show the first hint
Negative values break the sliding window. Think in prefix sums instead.
Walkthrough
How to approach it
01Clarify before coding
- Can values be negative? Yes, so a two-pointer window does not work.
- What if no subarray sums to k? Return 0.
- Length, not the subarray? Yes, just the length.
02Brute force
For every start, extend the end with a running sum and record the longest match.
Cost: O(n²) time: 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.