MiddleCodeCommonNot answered yet
Find a contiguous subarray summing to X (with negatives)
Given an array of integers (possibly negative) and a target X, find any non-empty contiguous subarray whose elements sum to X and return its [start, end] indices, or {-1, -1} if none exists.
Requirements:
- O(n) time.
- Because of negatives, a sliding window does not work.
std::pair<int,int> subarrayWithSum(const std::vector<int>& a, long long X) {
// your code here
}Write the implementation.
Walk the array accumulating a prefix sum P, with a hash map from prefix value to earliest index seeded 0 → -1. At each j, if P - X is in the map, the subarray after that index up to j sums to X. Negatives rule out a window, so the map gives O(n).
- ✗Using a sliding window despite negative numbers, which breaks the monotonic-sum assumption
- ✗Forgetting to seed
0 → -1so a subarray starting at index 0 is missed - ✗Letting the prefix sum overflow
inton large inputs
- →How would the approach simplify if all numbers were guaranteed non-negative?
- →Why is the
0 → -1seed entry essential?
Contents
Task
Find a contiguous subarray summing to X (numbers may be negative) in O(n).
Solution
std::pair<int,int> subarrayWithSum(const std::vector<int>& a, long long X) {
std::unordered_map<long long, int> firstIdx;
firstIdx[0] = -1; // empty prefix
long long prefix = 0;
for (int j = 0; j < static_cast<int>(a.size()); ++j) {
prefix += a[j];
auto it = firstIdx.find(prefix - X);
if (it != firstIdx.end()) return {it->second + 1, j};
firstIdx.emplace(prefix, j); // earliest index only
}
return {-1, -1};
}Key points
- Looking up
prefix - Xamong earlier prefixes gives O(n). - The
0 → -1seed catches a subarray starting at index 0. - A window does not work with negative numbers.
Contents
