055. Longest Subarray Summing to K

Why this mechanism works

The same prefix difference identifies valid starts, but the objective changes the remembered information. To maximize right-left for a fixed right boundary, keep the earliest occurrence of the needed prefix sum. Frequencies are unnecessary, and overwriting an early boundary can destroy the best length.

State and boundaries

earliest maps a prefix sum to its first boundary index. right counts consumed elements, beginning at one.

Protocol

1. Seed sum zero at boundary zero.
2. Extend the prefix.
3. If total-k exists, compare right-earliest[total-k] with best.
4. Store total only on its first occurrence.
5. Return best.

Visualization

[1,-1,5,-2,3], k=3
prefix at boundary 0: 0
prefix at boundary 4: 3
length=4-0=4

Python implementation

def longest_sum_k(nums, k):
    earliest = {0: 0}
    total = best = 0
    for right, value in enumerate(nums, 1):
        total += value
        if total - k in earliest:
            best = max(best, right - earliest[total - k])
        earliest.setdefault(total, right)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 longest_sum_k: earliest = {0: 0}
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0}

L3 longest_sum_k: total = best = 0
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0}; total=0; best=0

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0}; total=0; best=0; right=1; value=1

L5 longest_sum_k: total += value
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0}; total=1; best=0; right=1; value=1

L8 longest_sum_k: earliest.setdefault(total, right)
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1}; total=1; best=0; right=1; value=1

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1}; total=1; best=0; right=2; value=-1

L5 longest_sum_k: total += value
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1}; total=0; best=0; right=2; value=-1

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1}; total=0; best=0; right=3; value=5

... 5 intermediate state changes omitted ...

L8 longest_sum_k: earliest.setdefault(total, right)
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1, 5:3, 3:4}; total=3; best=4; right=4; value=-2

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1, 5:3, 3:4}; total=3; best=4; right=5; value=3

L5 longest_sum_k: total += value
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1, 5:3, 3:4}; total=6; best=4; right=5; value=3

L8 longest_sum_k: earliest.setdefault(total, right)
nums=[1, -1, 5, -2, 3]; k=3; earliest={0:0, 1:1, 5:3, 3:4, 6:5}; total=6; best=4; right=5; value=3

L2 longest_sum_k: earliest = {0: 0}
nums=[0, 0, 0]; k=0; earliest={0:0}

L3 longest_sum_k: total = best = 0
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=0

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=0; right=1; value=0

L7 longest_sum_k: best = max(best, right - earliest[total - k])
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=1; right=1; value=0

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=1; right=2; value=0

L7 longest_sum_k: best = max(best, right - earliest[total - k])
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=2; right=2; value=0

L4 longest_sum_k: for right, value in enumerate(nums, 1):
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=2; right=3; value=0

L7 longest_sum_k: best = max(best, right - earliest[total - k])
nums=[0, 0, 0]; k=0; earliest={0:0}; total=0; best=3; right=3; value=0

Why the solution is correct

All boundaries with the needed prefix yield valid intervals, and the earliest yields the longest for this endpoint. Retaining it cannot hurt any later endpoint. Considering every endpoint therefore finds the longest qualifying interval.

Time and space

O(n) expected time and O(n) auxiliary space.

Common mistakes

Replacing the earliest boundary with a later one shortens future candidates. Cell indices and boundary indices must not be mixed in the length formula.

Reasoning card

Transfer exercise

Find the shortest sum-k interval using remembered prefix positions. Which occurrence should be retained now?