Galactic Resource Allocation 2 — Problem Statement & Solution Guide

ArraysMediumSliding Window

TimeO(n)

SpaceO(1)

Problem Description

Given an array of strictly positive integers resourceValues and a positive integer targetCapacity, find the greatest possible length of a contiguous sub‑array whose elements sum to a value not larger than targetCapacity. If no sub‑array satisfies the condition, return 0. The algorithm must run in linear time relative to the array size.

DSA Pattern Breakdown

"Galactic Resource Allocation 2"

medium

WHY DOES IT MATTER?

The sliding‑window pattern solves a broad class of problems that require optimal sub‑array or sub‑string lengths under a cumulative constraint, making it a staple for performance‑critical code in real‑time systems.

OPTIMIZATION CHALLENGE

Recognizing that all numbers are positive lets you treat the sum as a monotonic function of the window size, allowing you to discard entire prefixes in O(1) instead of recomputing sums, which collapses the quadratic brute force to linear time.

REAL-WORLD CONNECTION

Think of a network router with a bandwidth cap: packets arrive continuously (right pointer) and the router must drop oldest packets (left pointer) when the total size exceeds the cap, always keeping the longest burst that fits within the limit.

During an interview, start by stating the monotonic property, sketch the two‑pointer movement, and then write the loop that expands right, contracts left when needed, and updates the answer – this demonstrates both insight and clean implementation.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the longest contiguous sub‑array whose sum does not exceed a given capacity. A naïve solution would enumerate every possible start index, expand the end index until the sum exceeds the limit, and keep track of the maximum length – this is O(n²) because each start re‑scans many elements. The key observation is that all numbers are strictly positive, which guarantees that extending a window can only increase its sum and shrinking it can only decrease it. This monotonicity enables the two‑pointer or sliding‑window technique, where we maintain a dynamic window [left,right) and adjust pointers in linear time. By moving the right pointer forward to include new elements and, whenever the sum exceeds targetCapacity, moving the left pointer forward to discard the oldest elements, we explore every feasible window exactly once, achieving O(n) time and O(1) extra space.

Interview Questions on This Problem

Q1How would you modify the solution if the array could contain zero or negative numbers?

With non‑positive numbers the sum is no longer monotonic, so the simple sliding window fails; you would need a prefix‑sum array combined with a balanced binary search tree or deque to find the longest sub‑array with sum ≤ target, which typically runs in O(n log n).

Q2Can you compute the answer using only one pass without storing the current sum explicitly?

Yes – you can keep the sum in a variable and update it incrementally as you move the pointers; the sum is effectively stored in that variable, so no extra array is needed, preserving O(1) space.

Q3What is the worst‑case scenario for the sliding‑window algorithm and why does it still remain linear?

The worst case occurs when every element forces both pointers to move (e.g., each element > targetCapacity, causing immediate left‑right shift). Each element is added and removed at most once, so total pointer movements are ≤ 2n, guaranteeing O(n) time.

Examples

Example 1

Input

{"resourceValues":[2,1,3,4,2],"targetCapacity":7}

Output

Explanation: Start with a sliding window at the array's beginning. Adding 2+1+3 gives sum 6 (≤7) and window length 3. Extending the window with the next element 4 makes sum 10 (>7), so shrink from the left: remove 2 → sum 8 (>7), remove 1 → sum 7 (≤7) with window length 3 (elements 3,4,2). No longer window can stay ≤7, thus the maximum length is 3.

Example 2

Input

{"resourceValues":[5,6,1,2,3],"targetCapacity":5}

Output

Explanation: The first element 5 already equals the capacity, giving a valid window of length 1. Adding the next element 6 exceeds the capacity, so the window must be reset. All subsequent elements are ≤5 individually, but none can be combined without exceeding 5. Hence the longest feasible sub‑array length is 1.

Example 3

Input

{"resourceValues":[1,1,1,1,1],"targetCapacity":3}

Output

Explanation: Expanding the window from the start, the sum after three elements is 3 (≤3) giving length 3. Adding a fourth element raises the sum to 4 (>3), so the window must shrink; any window containing more than three elements will exceed the capacity. Therefore the maximum length achievable is 3.

Constraints

1 <= resourceValues.length <= 100000
1 <= resourceValues[i] <= 10^9
1 <= targetCapacity <= 10^14

Optimal Approach & Strategy

Use a sliding window with two pointers, expanding right and contracting left when the sum is too big, updating the best length – O(n) time, O(1) space.

Brute Force Approach

Check every possible start index and extend the end index until the sum exceeds the target, recording the longest valid length – O(n²).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
const n = parseInt(input[idx++]||'0');
let arr=[];
for(let i=0;i<n;i++) arr.push(parseInt(input[idx++]||'0'));
const target = parseInt(input[idx++]||'0');
function maxSubarrayLength(resourceValues, targetCapacity){
    let left=0, sum=0, best=0;
    for(let right=0; right<resourceValues.length; ++right){
        sum+=resourceValues[right];
        while(left<=right && sum>targetCapacity){
            sum-=resourceValues[left++];
        }
        best=Math.max(best, right-left+1);
    }
    return best;
}
console.log(maxSubarrayLength(arr,target).toString());

#include <bits/stdc++.h>
using namespace std;
int maxSubarrayLength(const vector<int>& a, int target){
    int n=a.size();
    int left=0; long long sum=0; int best=0;
    for(int right=0; right<n; ++right){
        sum+=a[right];
        while(left<=right && sum>target){
            sum-=a[left++];
        }
        best=max(best, right-left+1);
    }
    return best;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    int target; cin>>target;
    cout<<maxSubarrayLength(a,target);
    return 0;
}

import java.io.*;
import java.util.*;
public class Main {
    public static int maxSubarrayLength(int[] a, int target){
        int left=0; long sum=0; int best=0;
        for(int right=0; right<a.length; ++right){
            sum+=a[right];
            while(left<=right && sum>target){
                sum-=a[left++];
            }
            best=Math.max(best, right-left+1);
        }
        return best;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if(line==null||line.isEmpty()) return;
        int n = Integer.parseInt(line.trim());
        int[] arr = new int[n];
        if(n>0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++) arr[i]=Integer.parseInt(st.nextToken());
        }
        int target = Integer.parseInt(br.readLine().trim());
        System.out.println(maxSubarrayLength(arr,target));
    }
}

import sys
def max_subarray_length(arr, target):
    left=0
    cur_sum=0
    best=0
    for right, val in enumerate(arr):
        cur_sum+=val
        while left<=right and cur_sum>target:
            cur_sum-=arr[left]
            left+=1
        best=max(best, right-left+1)
    return best

def main():
    data=sys.stdin.read().strip().split()
    if not data:
        return
    it=iter(data)
    n=int(next(it))
    arr=[int(next(it)) for _ in range(n)]
    target=int(next(it))
    print(max_subarray_length(arr,target))
if __name__=="__main__":
    main()

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
const n = parseInt(input[idx++]||'0');
let arr=[];
for(let i=0;i<n;i++) arr.push(parseInt(input[idx++]||'0'));
const target = parseInt(input[idx++]||'0');
function maxSubarrayLength(resourceValues, targetCapacity){
    let left=0, sum=0, best=0;
    for(let right=0; right<resourceValues.length; ++right){
        sum+=resourceValues[right];
        while(left<=right && sum>targetCapacity){
            sum-=resourceValues[left++];
        }
        best=Math.max(best, right-left+1);
    }
    return best;
}
console.log(maxSubarrayLength(arr,target).toString());

Asked in Top Tech Interviews

Salesforce

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.

Galactic Resource Allocation 2 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galactic Resource Allocation 2 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor