Subarray with a Given Sum
Updated
Problem statement
You are given an array arr of non-negative integers and a positive integer target. Find a subarray (one or more neighboring elements) whose values add up to exactly target.
Positions are counted from 1, so the first element is at position 1. Return [start, end], the first and last positions of the subarray.
If several subarrays work, return the one with the smallest start. If several of those share that start, return the one with the smallest end. If no subarray works, return [-1].
Function
findSubarrayWithSum(arr: int[], target: long) → int[]Examples
Example 1
arr = [1,2,3,7,5]target = 12return = [2,4]Positions 2 to 4 hold 2 + 3 + 7 = 12. Positions 4 to 5 also work, because 7 + 5 = 12, but position 2 is the smaller start, so the answer is [2, 4].
Example 2
arr = [4,0,0,3,0,2]target = 3return = [2,4]No subarray starting at position 1 works, because it already holds 4. From position 2, the sums are 0, 0, 3, so positions 2 to 4 add up to 3. Positions 2 to 5 also add up to 3, but position 4 is the earlier end. The answer is [2, 4], not the shorter [4, 4], because position 2 starts earlier.
Example 3
arr = [1,2,3]target = 7return = [-1]The whole array adds up to only 6, so no subarray reaches 7. The answer is [-1].
Constraints
1 <= arr.length <= 10^50 <= arr[i] <= 10^91 <= target <= 10^14
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Count Hotspot Playback WindowsGoogle · ONSITE INTERVIEWGoogle interview questions
- Shortest Window with Required CountsOracle · ONSITE INTERVIEWOracle interview questions
- Longest Binary Window with at Most K OnesLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Trim a Telemetry Buffer to a Target SumAmazon · ONSITE INTERVIEW
- Trapping Rain WaterInMobi · ONSITE INTERVIEWInMobi interview questions
- Subarray Product Less Than KApple · PHONE SCREENApple interview questions
- Subarray Product Less Than KAngel One · PHONE SCREEN
- Subarray Product Less Than KThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Trapping Rain WaterGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Count Subarrays With Product Equal to KSalesforce · OASalesforce interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)