BL
U

46. Longest Subarray with Sum K (With Negative Numbers)

Med.

Problem Description

Given an array of NN integers (which may include negative values) and an integer KK, find the length of the longest contiguous subarray whose sum equals KK. If none exists, output 0.

Input Format

  • •Line 1: Two space-separated integers NN and KK (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the maximum length of a subarray with sum KK.

Example 1:
Input:
6 0
1 -1 5 -2 3 -6
Output:
6
Explanation: Sum of all 6 elements is 1-1+5-2+3-6 = 0, length 6.
Example 2:
Input:
3 5
1 2 3
Output:
2
Explanation: Subarray [2, 3] has sum 5 and length 2.
Example 3:
Input:
3 100
1 2 3
Output:
0
Explanation: No subarray sums to 100.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online