Galactic Expedition Routes — Problem Statement & Solution Guide
Problem Description
Given an integer array distances and an integer fuel, identify every non‑empty contiguous subarray whose elements sum exactly to fuel. Return a list containing each distinct subarray as an array of its elements. Subarrays that have identical sequences of numbers are considered the same and should appear only once in the result. The order of subarrays in the output is irrelevant; if no subarray meets the criterion, return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Expedition Routes"
WHY DOES IT MATTER?
Identifying subarrays with a specific sum is a classic sliding‑window / prefix‑sum pattern that appears in financial transaction analysis, signal processing, and load‑balancing scenarios where exact quotas must be met. Mastery of this pattern demonstrates a candidate’s ability to convert quadratic enumeration into linear‑time hash‑based lookups.
OPTIMIZATION CHALLENGE
The breakthrough is recognising that the sum of any subarray can be expressed as the difference of two prefix sums. By storing each prefix sum as you scan, you turn a nested loop into a single pass and a constant‑time hashmap lookup, collapsing O(n^2) work into O(n).
REAL-WORLD CONNECTION
Think of a logistics pipeline where trucks carry cargo weights (array elements) and you need to find every contiguous sequence of trucks that exactly fills a container of capacity 'fuel'. Instead of checking every possible convoy, you track the cumulative weight as trucks join the line and instantly know when a perfect fill occurs by consulting a ledger (hash map) of previous cumulative weights.
During an interview, compute the running sum on the fly, query the hashmap for (currentSum‑target), and immediately push any newly discovered subarray into a result set while also inserting the current sum into the map. Keep a secondary Set of serialized subarrays to enforce uniqueness.
COMPLEXITY AT A GLANCE
O(n+output)O(n+output)Core Theory — Why This Approach?
The problem asks for every distinct contiguous subarray whose elements sum to a given target. A naïve solution enumerates all O(n^2) subarrays and computes each sum, which quickly becomes infeasible for large n because the sum operation itself can be O(n) leading to O(n^3) time in the worst case. The optimal paradigm leverages prefix sums: the sum of a subarray [i..j] equals prefix[j+1]-prefix[i]. By storing each prefix sum in a hash map that maps a sum value to all indices where it occurs, we can, for each current prefix, instantly discover all earlier positions that would produce the target sum. This reduces the search to linear time while still allowing us to reconstruct the actual subarrays. To guarantee uniqueness of the output, we canonicalise each discovered subarray (e.g., by joining its elements into a string) and store it in a secondary hash set, discarding duplicates that arise from identical value sequences at different positions.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain negative numbers and you needed to return the count of distinct subarrays instead of the subarrays themselves?
The same prefix‑sum + hashmap technique works because negative numbers do not break the equality check. Instead of storing the actual subarray, maintain a hash set of the stringified subarray or a rolling hash of its values to ensure distinctness, and increment a counter each time a new unique representation is found.
Q2What is the time and space complexity trade‑off when you store all start indices for each prefix sum versus storing only the most recent index?
Storing all start indices preserves the ability to enumerate every qualifying subarray, giving O(n+output) time but O(n) additional space for the map of lists. Keeping only the latest index reduces space to O(1) extra but loses the ability to list all subarrays, limiting the solution to counting occurrences.
Q3In a distributed system where the array is sharded across multiple nodes, how could you compute the target‑sum subarrays without moving the entire data set to a single node?
Each node computes local prefix sums and emits (prefixValue, localIndex) pairs. A coordinator merges these streams, adjusting indices by the cumulative length of preceding shards, and applies the same hashmap logic globally. Overlapping subarrays that cross shard boundaries are detected by sharing the last prefix value of the previous shard with the next node.
Examples
Input
distances = [2,3,1,2,4,3], fuel = 7
Output
[[1,2,4],[4,3]]
Explanation: Starting at index 2 the slice [1,2,4] sums to 7. Starting at index 4 the slice [4,3] also sums to 7. No other contiguous segment yields 7, and the two found slices are different, so they are returned.
Input
distances = [5,-2,3,1,2], fuel = 4
Output
[[-2,3,1,2],[3,1]]
Explanation: From index 1 to 4 the segment [-2,3,1,2] sums to 4. From index 2 to 3 the segment [3,1] also sums to 4. Both are unique sequences, so they are included.
Input
distances = [1,1,1,1,1], fuel = 3
Output
[[1,1,1]]
Explanation: Every length‑3 window sums to 3, but all produce the identical sequence [1,1,1]. Because duplicates are removed, the result contains a single subarray.
Constraints
- 1 <= distances.length <= 100000
- -1000000000 <= distances[i] <= 1000000000
- -1000000000 <= fuel <= 1000000000
- Solution should run in O(n) time and O(n) additional space
Optimal Approach & Strategy
Maintain a running prefix sum and a hashmap from sum values to all indices where they occur; for each index, look up (prefix‑target) to instantly retrieve all matching start positions, then store unique subarrays.
Brute Force Approach
Generate every possible contiguous subarray with two nested loops and compute its sum, checking against the target each time.
Verified Code Solutions
/**
* @param {number[]} distances
* @param {number} fuel
* @return {number[][]}
*/
function findExpeditionRoutes(distances, fuel) {
const n = distances.length;
if (n === 0) return [];
const uniqueSubarrays = new Set();
for (let i = 0; i < n; i++) {
let currentSum = 0;
for (let j = i; j < n; j++) {
currentSum += distances[j];
if (currentSum === fuel) {
const subarray = distances.slice(i, j + 1);
uniqueSubarrays.add(JSON.stringify(subarray));
}
}
}
const result = [];
for (const str of uniqueSubarrays) {
result.push(JSON.parse(str));
}
return result;
}
// Example usage
const distances = [2, 3, 1, 2, 4, 3];
const fuel = 7;
const result = findExpeditionRoutes(distances, fuel);
console.log(result);#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
vector<vector<int>> findExpeditionRoutes(vector<int>& distances, int fuel) {
int n = distances.size();
if (n == 0) return {};
set<vector<int>> uniqueSubarrays;
for (int i = 0; i < n; ++i) {
int currentSum = 0;
for (int j = i; j < n; ++j) {
currentSum += distances[j];
if (currentSum == fuel) {
vector<int> subarray(distances.begin() + i, distances.begin() + j + 1);
uniqueSubarrays.insert(subarray);
} else if (currentSum > fuel && all_of(distances.begin() + i, distances.begin() + j + 1, [](int x) { return x > 0; })) {
// Optimization: if all elements are positive and sum exceeds fuel, break
// But since we can have negative numbers, we can't always break
// For safety, we continue unless we know all remaining are positive
}
}
}
vector<vector<int>> result;
for (const auto& subarray : uniqueSubarrays) {
result.push_back(subarray);
}
return result;
}
int main() {
vector<int> distances = {2, 3, 1, 2, 4, 3};
int fuel = 7;
vector<vector<int>> result = findExpeditionRoutes(distances, fuel);
for (const auto& subarray : result) {
cout << "[";
for (size_t i = 0; i < subarray.size(); ++i) {
cout << subarray[i];
if (i < subarray.size() - 1) cout << ", ";
}
cout << "] ";
}
cout << endl;
return 0;
}import java.util.*;
public class Main {
public static List<List<Integer>> findExpeditionRoutes(int[] distances, int fuel) {
int n = distances.length;
if (n == 0) return new ArrayList<>();
Set<List<Integer>> uniqueSubarrays = new HashSet<>();
for (int i = 0; i < n; i++) {
int currentSum = 0;
for (int j = i; j < n; j++) {
currentSum += distances[j];
if (currentSum == fuel) {
List<Integer> subarray = new ArrayList<>();
for (int k = i; k <= j; k++) {
subarray.add(distances[k]);
}
uniqueSubarrays.add(subarray);
}
}
}
return new ArrayList<>(uniqueSubarrays);
}
public static void main(String[] args) {
int[] distances = {2, 3, 1, 2, 4, 3};
int fuel = 7;
List<List<Integer>> result = findExpeditionRoutes(distances, fuel);
for (List<Integer> subarray : result) {
System.out.print("[");
for (int i = 0; i < subarray.size(); i++) {
System.out.print(subarray.get(i));
if (i < subarray.size() - 1) System.out.print(", ");
}
System.out.print("] ");
}
System.out.println();
}
}from typing import List
def find_expedition_routes(distances: List[int], fuel: int) -> List[List[int]]:
n = len(distances)
if n == 0:
return []
unique_subarrays = set()
for i in range(n):
current_sum = 0
for j in range(i, n):
current_sum += distances[j]
if current_sum == fuel:
subarray = tuple(distances[i:j+1])
unique_subarrays.add(subarray)
return [list(subarray) for subarray in unique_subarrays]
if __name__ == "__main__":
distances = [2, 3, 1, 2, 4, 3]
fuel = 7
result = find_expedition_routes(distances, fuel)
print(result)/**
* @param {number[]} distances
* @param {number} fuel
* @return {number[][]}
*/
function findExpeditionRoutes(distances, fuel) {
const n = distances.length;
if (n === 0) return [];
const uniqueSubarrays = new Set();
for (let i = 0; i < n; i++) {
let currentSum = 0;
for (let j = i; j < n; j++) {
currentSum += distances[j];
if (currentSum === fuel) {
const subarray = distances.slice(i, j + 1);
uniqueSubarrays.add(JSON.stringify(subarray));
}
}
}
const result = [];
for (const str of uniqueSubarrays) {
result.push(JSON.parse(str));
}
return result;
}
// Example usage
const distances = [2, 3, 1, 2, 4, 3];
const fuel = 7;
const result = findExpeditionRoutes(distances, fuel);
console.log(result);Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.