Overview

This problem asks us to find the length of the longest contiguous subarray whose sum is at most \(K\). It can be solved efficiently using the two-pointer technique (also known as the sliding window technique).

Analysis

Naive Approach and Its Issues

The first approach that comes to mind is to try all possible intervals \([l, r]\).

for l in 1..N:
    for r in l..N:
        Calculate the sum of interval [l,r] and check if it's at most K

This method has \(O(N^2)\) ways to choose intervals, and calculating the sum of each interval takes \(O(N)\), resulting in an overall complexity of \(O(N^3)\). For \(N = 2 \times 10^5\), this is far too slow.

Using prefix sums can reduce the sum calculation to \(O(1)\), but even then, \(O(N^2)\) will result in TLE.

Key Insight

Here’s an important observation:

Since all elements in the array are positive, extending the interval to the right always increases the sum, and moving the left endpoint to the right always decreases the sum

Using this monotonicity, when the left endpoint \(l\) is fixed, there is a unique maximum \(r\) that satisfies the condition. Furthermore, when \(l\) increases by 1, the corresponding maximum \(r\) either stays the same or increases (it never decreases).

For example, with \(A = [3, 1, 2, 4, 1]\) and \(K = 6\): - When \(l=1\): \([3,1,2]\) is possible (sum \(6\)), \(r=3\) - When \(l=2\): \([1,2,4]\) has sum \(7 > 6\), so \([1,2]\) with \(r=3\), or moving forward to \(r=4\) gives sum \(7\) which is not allowed - Actually, for \(l=2\), \(r=3\) (sum \(3\)) or \(r=4\) (sum \(7\)), so up to \(r=3\) is possible

Due to this property, we can use the “two-pointer technique” where both \(l\) and \(r\) only move in the right direction.

Algorithm

We use the Two-Pointer Technique.

1. Start both left endpoint \(l\) and right endpoint \(r\) at \(0\) (the beginning)
2. Move \(r\) one position to the right and add \(A[r]\) to the interval sum
3. While the sum exceeds \(K\), move \(l\) to the right and subtract \(A[l]\)
4. Update the answer with the current interval length \(r - l + 1\)
5. Repeat steps 2-4 until \(r\) reaches the end

Concrete example (\(A = [3, 1, 2, 4, 1]\), \(K = 6\)):

Step	\(l\)	\(r\)	Interval	Sum	Length
1	0	0	[3]	3	1
2	0	1	[3,1]	4	2
3	0	2	[3,1,2]	6	3
4	1	3	[1,2,4]	7→shrink left	-
4’	2	3	[2,4]	6	2
5	3	4	[4,1]	7→5	2

Answer: 3

Complexity

• Time Complexity: \(O(N)\)
  • Since \(l\) and \(r\) each increase at most \(N\) times, even including the while loop, the overall complexity is \(O(N)\)
• Space Complexity: \(O(N)\)
  • Space required to store the array \(A\)

Implementation Notes

• Since the upper bound of \(K\) is as large as \(10^{15}\), the variable storing the sum must be a 64-bit integer (Python handles this automatically)

• By including left <= right in the condition while current_sum > K and left <= right, we can handle the case where all elements are greater than \(K\)

• If there is no interval satisfying the condition (each \(A_i > K\)), max_count remains \(0\) and is output as is

  Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    max_count = 0
    current_sum = 0
    left = 0
    
    for right in range(N):
        current_sum += A[right]
        
        while current_sum > K and left <= right:
            current_sum -= A[left]
            left += 1
        
        if current_sum <= K:
            max_count = max(max_count, right - left + 1)
    
    print(max_count)

solve()

---

This editorial was generated by claude4.5opus.