Optimizing Warehouse Storage — Problem Statement & Solution Guide
Problem Description
You are given an integer n, an array weights of length n containing the weight of each crate, and an integer capacity representing the maximum total weight that can be stored. The crates are positioned consecutively around a circular warehouse, so a segment may start at any index and continue forward, wrapping around to the beginning if necessary. Choose a non‑empty contiguous segment (allowing wrap‑around) whose total weight does not exceed capacity and is as large as possible. If no crate fits, the answer is 0. Return the maximum achievable total weight. An optimal solution runs in linear time using a two‑pointer (sliding‑window) technique that treats the circular array by virtually extending it to length 2·n.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimizing Warehouse Storage"
WHY DOES IT MATTER?
The sliding‑window on circular arrays is a cornerstone pattern for any problem that asks for the longest/most‑valuable contiguous segment under a constraint, common in networking, finance, and storage optimization.
OPTIMIZATION CHALLENGE
The key insight is that with non‑negative weights the window sum only grows when the right edge moves and only shrinks when the left edge moves, allowing us to adjust pointers greedily instead of recomputing sums for every possible segment.
REAL-WORLD CONNECTION
Think of a conveyor belt that loops around a warehouse; you want to load the belt with as many crates as possible without exceeding the truck’s weight limit. The belt’s continuous motion mirrors the circular array, and the two‑pointer scan mimics moving the loading gate forward while keeping the load under the limit.
During an interview, start by handling the linear case, then explain how duplicating the array or using modulo arithmetic turns the circle into a line; this shows you understand both the core algorithm and the edge‑case handling.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to finding the maximum‑weight contiguous segment on a circular array whose total does not exceed a given capacity. A naïve solution enumerates every possible start‑end pair, leading to O(n²) time – infeasible for n up to 10⁵ or higher. Because all crate weights are non‑negative, the sum of a window is monotonic as the right pointer moves, which enables a two‑pointer (sliding‑window) technique. By conceptually duplicating the array (or using modulo arithmetic) we can treat the circle as a linear sequence of length 2n, slide a left and right pointer while keeping the current sum ≤ capacity, and record the best sum encountered. This yields an O(n) time, O(1) extra‑space solution, which is optimal for this class of problems.
Interview Questions on This Problem
Q1How would you adapt the sliding‑window solution if some crate weights could be negative?
With negative values the sum is no longer monotonic, so the classic two‑pointer window fails. You would need to use a prefix‑sum array combined with a balanced binary search tree (or deque) to query the smallest prefix greater than current‑prefix‑capacity, achieving O(n log n) time.
Q2Explain how to modify the algorithm to also return the start and end indices of the optimal segment in the original circular layout.
Maintain the indices of the left pointer when a new best sum is found. Because we slide over a virtual array of length 2n, map the left index back to the original range using modulo n, and ensure the segment length never exceeds n to avoid wrapping more than once.
Q3A company asks you to handle up to 10⁶ crates with real‑time updates to individual weights. Which data structure would you choose to keep the solution efficient?
A segment tree or Fenwick tree storing prefix sums allows point updates in O(log n) and range‑sum queries in O(log n). To answer the capacity‑constrained maximum‑segment query you would combine binary search on the prefix‑sum tree with a sliding‑window‑like scan, yielding O(log² n) per update/query.
Examples
Input
5 4 2 1 7 3 10
Output
10
Explanation: Starting at index 1 (weight 2) and taking crates 2,3,4 (2+1+7) gives a sum of 10, which equals the capacity and is the largest possible sum not exceeding 10.
Input
6 5 1 2 6 4 3 12
Output
12
Explanation: The segment 3‑5 (weights 2,6,4) sums to 12, exactly matching the capacity. Another valid segment is the wrap‑around 5‑1 (weights 4,3,5) also totaling 12. No segment can exceed 12 without violating the limit, so the answer is 12.
Input
4 8 9 10 11 7
Output
0
Explanation: Every individual crate weighs more than the capacity 7, therefore no non‑empty segment satisfies the constraint. The optimal total weight is 0.
Constraints
- 1 <= n <= 100000
- 1 <= weights[i] <= 10^9
- 1 <= capacity <= 10^15
Optimal Approach & Strategy
Use a sliding window on a duplicated array, moving right pointer forward and shrinking from the left whenever the sum exceeds capacity, tracking the maximum valid sum.
Brute Force Approach
Check every possible start index and extend to every possible end index (wrapping around), compute the sum each time, and keep the best that fits the capacity.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0;
function maxSegmentWeight(n, w, C){
if(n===0) return 0;
let best=0, cur=0, left=0;
for(let right=0; right<2*n; ++right){
cur+= w[right % n];
while(cur> C || right-left+1> n){
cur-= w[left % n];
left++;
}
if(right-left+1>0) best = Math.max(best, cur);
}
return best;
}
if(data.length===0) process.exit(0);
const n=data[p++];
const w=data.slice(p,p+n); p+=n;
const C=data[p];
console.log(maxSegmentWeight(n,w,C).toString());#include <bits/stdc++.h>
using namespace std;
int maxSegmentWeight(int n, const vector<int>& w, int C){
if(n==0) return 0;
long long best = 0;
long long cur = 0;
int left = 0;
// duplicate the array logically by using modulo
for(int right=0; right<2*n; ++right){
cur += w[right % n];
while(cur > C || right-left+1 > n){
cur -= w[left % n];
++left;
}
if(right-left+1>0) best = max(best, cur);
}
return (int)best;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> w(n);
for(int i=0;i<n;++i) cin>>w[i];
int C; cin>>C;
cout<<maxSegmentWeight(n,w,C);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
private static int maxSegmentWeight(int n, int[] w, int C){
if(n==0) return 0;
long best = 0;
long cur = 0;
int left = 0;
for(int right=0; right<2*n; ++right){
cur += w[right % n];
while(cur > C || right - left + 1 > n){
cur -= w[left % n];
left++;
}
if(right - left + 1 > 0) best = Math.max(best, cur);
}
return (int)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[] w = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) w[i]=Integer.parseInt(st.nextToken());
int C = Integer.parseInt(br.readLine().trim());
System.out.print(maxSegmentWeight(n,w,C));
}
}import sys
def max_segment_weight(n, w, C):
if n==0:
return 0
best = 0
cur = 0
left = 0
for right in range(2*n):
cur += w[right % n]
while cur > C or (right - left + 1) > n:
cur -= w[left % n]
left += 1
if right - left + 1 > 0:
best = max(best, cur)
return best
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
n = int(next(it))
w = [int(next(it)) for _ in range(n)]
C = int(next(it))
print(max_segment_weight(n,w,C))
if __name__ == "__main__":
main()const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0;
function maxSegmentWeight(n, w, C){
if(n===0) return 0;
let best=0, cur=0, left=0;
for(let right=0; right<2*n; ++right){
cur+= w[right % n];
while(cur> C || right-left+1> n){
cur-= w[left % n];
left++;
}
if(right-left+1>0) best = Math.max(best, cur);
}
return best;
}
if(data.length===0) process.exit(0);
const n=data[p++];
const w=data.slice(p,p+n); p+=n;
const C=data[p];
console.log(maxSegmentWeight(n,w,C).toString());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.