Galactic Resource Allocation — Problem Statement & Solution Guide
Problem Description
Given an array nums of n non‑negative integers, determine whether there exist two indices i and j with 0 < i < j < n‑1 such that the three contiguous subarrays [0…i], [i+1…j] and [j+1…n‑1] are all non‑empty and satisfy sum(0…i) > sum(i+1…j) and sum(j+1…n‑1) > sum(i+1…j). Output "YES" if such a partition exists, otherwise output "NO". The solution must run in O(n) time and O(1) extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Resource Allocation"
WHY DOES IT MATTER?
This problem highlights the power of prefix sums and maintaining running aggregates to avoid nested loops. It is a critical pattern for optimizing partition problems where global constraints (like total sum) can be leveraged to simplify local checks.
OPTIMIZATION CHALLENGE
The key insight is converting the two inequalities involving three segments into a single condition on the prefix sum at the right boundary, leveraging the maximum prefix sum seen so far to represent the best possible left boundary.
REAL-WORLD CONNECTION
Analogous to resource allocation in cloud computing, where you want to ensure a 'buffer' resource (middle) is not over-allocated compared to primary and backup resources (left/right) to maintain system stability and cost efficiency.
In interviews, explicitly state the transformation of the inequalities. Show how sum_left > sum_mid becomes 2*P_i > P_j and sum_right > sum_mid becomes S + P_i > 2*P_j. This demonstrates mathematical rigor and clarity.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem requires partitioning an array into three non-empty contiguous segments where the middle segment's sum is strictly less than both the left and right segments. A naive approach involving nested loops to check all possible partitions results in O(n^2) time complexity, which is infeasible for large inputs (n up to 10^5 or more). The key insight is that the condition sum_left > sum_mid and sum_right > sum_mid can be rephrased using prefix sums. Specifically, if we fix the middle segment boundaries, we are looking for a local minimum in the sequence of prefix sums relative to the total sum. However, a more direct O(n) approach leverages the fact that if a valid partition exists, the middle segment must be 'small' relative to the rest. By iterating through possible middle segments or using a two-pointer technique, we can maintain running sums. Actually, the most robust O(n) O(1) approach involves realizing that we just need to find *any* valid split. We can iterate through the array, maintaining the sum of the left part and the sum of the right part. For each potential middle segment, we check if the middle sum is less than both neighbors. A simpler O(n) logic: Iterate j from 1 to n-2. Maintain left_sum (sum of 0..j-1) and right_sum (sum of j+1..n-1). The middle sum is nums[j]. We need left_sum > nums[j] and right_sum > nums[j]. We can precompute the total sum. As we iterate j, left_sum accumulates nums[j-1] and right_sum decreases by nums[j+1]. This allows checking each potential single-element middle segment in O(1). Wait, the middle segment can have multiple elements. The problem states i < j, so the middle segment is [i+1...j]. This means the middle segment can have length > 1. The O(n) constraint is tight. Let's re-evaluate. If the middle segment can be any length, checking all pairs (i, j) is O(n^2). Is there an O(n) solution? Yes, if we observe that if a valid partition exists with a middle segment of length > 1, we can often shrink it or find a single element that works? No, that's not necessarily true. However, a known property for this specific 'three parts' problem where middle < left and middle < right is that we can iterate through the array and maintain the minimum prefix sum and maximum suffix sum? No. Let's look at the constraints again. O(n) time. This implies a linear scan. The trick is that we don't need to check all (i, j). We can iterate j from 1 to n-2. For a fixed j, the middle segment ends at j. The left segment ends at i. We need sum(0..i) > sum(i+1..j) and sum(j+1..n-1) > sum(i+1..j). Let S be total sum. sum(j+1..n-1) = S - sum(0..j). sum(i+1..j) = sum(0..j) - sum(0..i). Let P_k be prefix sum up to k. Condition: P_i > P_j - P_i => 2P_i > P_j. And S - P_j > P_j - P_i => S + P_i > 2P_j. We need to find i < j such that P_i > P_j/2 and P_i > 2P_j - S. Since P_i must be greater than both P_j/2 and 2P_j - S, we need P_i > max(P_j/2, 2P_j - S). Also i < j. As we iterate j from 1 to n-2, we can maintain the maximum P_i for i < j. If max_P_i > max(P_j/2, 2P_j - S), we return YES. This is O(n).
Interview Questions on This Problem
Q1At a fintech company, you are optimizing a risk allocation model where a portfolio is split into three buckets: Low Risk, Medium Risk, and High Risk. The Medium Risk bucket must have a lower total value than both the Low and High Risk buckets to ensure diversification. Given an array of asset values, how would you determine in O(n) time if such a split exists?
I would use prefix sums. Let S be the total sum. I iterate through the array with index j representing the end of the middle segment. I maintain the maximum prefix sum seen so far (for indices i < j). For each j, I check if there exists an i such that the sum of the left segment (P_i) is greater than the middle segment (P_j - P_i) and the right segment (S - P_j) is greater than the middle segment. This simplifies to checking if max_prefix_sum > max(P_j/2, 2*P_j - S). If this condition is met for any j, the answer is YES.
Q2In a distributed systems context, you are balancing load across three server clusters. The middle cluster's load must be strictly lower than both the first and third clusters to prevent bottlenecks. How can you verify this condition in linear time without storing the entire load history?
This is a classic array partitioning problem. I would perform a single pass through the load array. I keep track of the cumulative load (prefix sum) and the maximum prefix sum encountered so far. For each potential boundary j, I calculate the required threshold for the left cluster's load to satisfy the inequality. If the maximum left load seen so far exceeds this threshold, a valid configuration exists. This ensures O(n) time and O(1) space.
Q3A high-growth startup is analyzing user engagement data split into three phases: Onboarding, Active, and Churned. They want to know if there is a period where the 'Active' phase engagement is lower than both 'Onboarding' and 'Churned' phases. How would you solve this efficiently for a stream of data?
I would treat the engagement values as an array. Using a prefix sum approach, I iterate through the data points. I maintain the maximum prefix sum up to the current index. For each index j, I check if the maximum prefix sum (representing the best possible left segment) is greater than half of the current prefix sum and greater than twice the current prefix sum minus the total sum. This linear scan allows us to determine the existence of such a partition in O(n) time.
Examples
Input
5 4 1 2 3 5
Output
YES
Explanation: Prefix sums: [4,5,7,10,15]. Choose i=1 (first subarray sum=5) and j=2 (second subarray sum=2). Third subarray sum=15‑7=8. Conditions 5>2 and 8>2 hold, so answer is YES.
Input
4 1 1 1 1
Output
NO
Explanation: All possible partitions produce a middle sum of at least 1. No left or right sum can be strictly greater than the middle sum while keeping all parts non‑empty, thus NO.
Input
5 10 0 0 5 1
Output
YES
Explanation: Take i=0 (left sum=10) and j=2 (middle sum=0+0=0). Right sum = total‑(10+0)=6. Both 10>0 and 6>0 are true, so the partition is valid.
Constraints
- 1 <= nums.length <= 100000
- 0 <= nums[i] <= 10000
- All sums fit in 64‑bit signed integer
Optimal Approach & Strategy
Use prefix sums and a single pass. Iterate j from 1 to n-2, maintaining the maximum prefix sum seen so far (for i < j). Check if this maximum prefix sum satisfies the derived inequalities P_i > P_j/2 and P_i > 2P_j - S for the current j.
Brute Force Approach
Iterate through all possible pairs of indices (i, j) where 0 < i < j < n-1. For each pair, calculate the sums of the three segments and check if the middle sum is strictly less than both the left and right sums.
Verified Code Solutions
function canPartition(nums) {
const n = nums.length;
if (n < 3) return false;
let total = 0;
for (let x of nums) total += x;
let prefix = 0;
for (let i = 0; i < n; i++) {
prefix += nums[i];
// j = i+1, so we need i >= 1 (j >= 2) and i+1 <= n-2 (i <= n-3)
if (i >= 1 && i <= n - 3) {
const prefix_j = prefix + nums[i + 1]; // prefix[i+1]
const prefix_i = prefix; // prefix[i]
// Check conditions:
// 2*prefix_i > prefix_j
// total + prefix_i > 2*prefix_j
if (2 * prefix_i > prefix_j && total + prefix_i > 2 * prefix_j) {
return true;
}
}
}
return false;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
let lineCount = 0;
rl.on('line', (line) => {
lines.push(line);
lineCount++;
if (lineCount === 2) {
const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
if (canPartition(nums)) {
console.log("YES");
} else {
console.log("NO");
}
rl.close();
}
});#include <iostream>
#include <vector>
using namespace std;
bool canPartition(const vector<int>& nums) {
int n = nums.size();
if (n < 3) return false;
// We need to find i and j such that:
// 0 < i < j < n-1
// sum(0...i) > sum(i+1...j)
// sum(j+1...n-1) > sum(i+1...j)
// Let prefix[i] = sum(0...i)
// Let suffix[j] = sum(j...n-1)
// sum(i+1...j) = prefix[j] - prefix[i]
// sum(j+1...n-1) = total - prefix[j]
// Conditions become:
// prefix[i] > prefix[j] - prefix[i] => 2*prefix[i] > prefix[j]
// total - prefix[j] > prefix[j] - prefix[i] => total + prefix[i] > 2*prefix[j]
// We can iterate j from 2 to n-2 (since i < j and i >= 1, j <= n-2)
// For each j, we need to check if there exists an i in [1, j-1] such that:
// 1. 2*prefix[i] > prefix[j]
// 2. total + prefix[i] > 2*prefix[j]
// Since all numbers are non-negative, prefix is non-decreasing.
// So for a fixed j, the maximum prefix[i] for i in [1, j-1] is prefix[j-1].
// If prefix[j-1] satisfies both conditions, then YES.
// Otherwise, no smaller i will work because prefix[i] <= prefix[j-1].
long long total = 0;
for (int x : nums) total += x;
long long prefix = 0;
for (int i = 0; i < n; i++) {
prefix += nums[i];
// j = i+1, so we need i >= 1 (j >= 2) and i+1 <= n-2 (i <= n-3)
// So i ranges from 1 to n-3
if (i >= 1 && i <= n - 3) {
long long prefix_j = prefix + nums[i + 1]; // prefix[i+1]
long long prefix_i = prefix; // prefix[i]
// Check conditions:
// 2*prefix_i > prefix_j
// total + prefix_i > 2*prefix_j
if (2 * prefix_i > prefix_j && total + prefix_i > 2 * prefix_j) {
return true;
}
}
}
return false;
}
int main() {
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
if (canPartition(nums)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}import java.util.Scanner;
public class Main {
public static boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 3) return false;
long total = 0;
for (int x : nums) total += x;
long prefix = 0;
for (int i = 0; i < n; i++) {
prefix += nums[i];
// j = i+1, so we need i >= 1 (j >= 2) and i+1 <= n-2 (i <= n-3)
if (i >= 1 && i <= n - 3) {
long prefix_j = prefix + nums[i + 1]; // prefix[i+1]
long prefix_i = prefix; // prefix[i]
// Check conditions:
// 2*prefix_i > prefix_j
// total + prefix_i > 2*prefix_j
if (2 * prefix_i > prefix_j && total + prefix_i > 2 * prefix_j) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
if (!scanner.hasNextInt()) {
return;
}
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
if (scanner.hasNextInt()) {
nums[i] = scanner.nextInt();
}
}
if (canPartition(nums)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
scanner.close();
}
}def can_partition(nums):
n = len(nums)
if n < 3:
return False
total = sum(nums)
prefix = 0
for i in range(n):
prefix += nums[i]
# j = i+1, so we need i >= 1 (j >= 2) and i+1 <= n-2 (i <= n-3)
if 1 <= i <= n - 3:
prefix_j = prefix + nums[i + 1] # prefix[i+1]
prefix_i = prefix # prefix[i]
# Check conditions:
# 2*prefix_i > prefix_j
# total + prefix_i > 2*prefix_j
if 2 * prefix_i > prefix_j and total + prefix_i > 2 * prefix_j:
return True
return False
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
if not data:
sys.exit(0)
n = int(data[0])
nums = list(map(int, data[1:n+1]))
if can_partition(nums):
print("YES")
else:
print("NO")function canPartition(nums) {
const n = nums.length;
if (n < 3) return false;
let total = 0;
for (let x of nums) total += x;
let prefix = 0;
for (let i = 0; i < n; i++) {
prefix += nums[i];
// j = i+1, so we need i >= 1 (j >= 2) and i+1 <= n-2 (i <= n-3)
if (i >= 1 && i <= n - 3) {
const prefix_j = prefix + nums[i + 1]; // prefix[i+1]
const prefix_i = prefix; // prefix[i]
// Check conditions:
// 2*prefix_i > prefix_j
// total + prefix_i > 2*prefix_j
if (2 * prefix_i > prefix_j && total + prefix_i > 2 * prefix_j) {
return true;
}
}
}
return false;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
let lineCount = 0;
rl.on('line', (line) => {
lines.push(line);
lineCount++;
if (lineCount === 2) {
const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
if (canPartition(nums)) {
console.log("YES");
} else {
console.log("NO");
}
rl.close();
}
});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.