Skills101
← All coding problems

Subarray With Given Sum

mediumPlacement Coding+20 XPTime limit 2s

All numbers in the array are positive. Find a contiguous subarray whose sum is exactly S. If several exist, report the one that ends first (smallest right end). Because every number is positive, there is at most one such subarray for each right end.

Input:

  • line 1: n S
  • line 2: n positive integers

Output: the 1-based start and end positions l r, or -1 if no subarray has sum S.

Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ values ≤ 10⁴, 1 ≤ S ≤ 10⁹.

Think about it: use a sliding window. Grow the window to the right; while its sum is larger than S, shrink it from the left. Positive numbers make this safe: shrinking always lowers the sum.

Sample input 1

5 12
1 2 3 7 5

Sample output 1

2 4

Sample input 2

3 100
1 2 3

Sample output 2

-1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.