Optimal Range Partitioning — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Optimal Range Partitioning problem optimally.
O((N + Q) · log N)O(N)Problem Description
You are provided with an array nums of non-negative integers and a 2D array queries. Each query in queries is represented as a pair [L, R], indicating a subarray from index L to R (inclusive). For each query, you must partition the subarray nums[L...R] into two non-empty contiguous segments: a left segment nums[L...K] and a right segment nums[K+1...R], where L <= K < R. The cost of a partition is defined as the absolute difference between the sum of the left segment and the sum of the right segment. Your task is to determine the minimum possible partition cost for each query.
The goal is to find the split point K that minimizes the absolute difference between the cumulative sum of the left part and the cumulative sum of the right part. Since the total sum of the subarray is fixed for a given query, minimizing the absolute difference is equivalent to finding the split point where the prefix sum is closest to half of the total subarray sum.
Return an array of integers where the i-th element corresponds to the minimum partition cost for the i-th query in queries.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimal Range Partitioning"
WHY DOES IT MATTER?
Balancing two contiguous partitions is a recurring sub‑problem in load‑balancing and divide‑and‑conquer designs.
OPTIMIZATION CHALLENGE
The key is reducing per‑query linear scans to logarithmic searches by exploiting prefix‑sum monotonicity.
REAL-WORLD CONNECTION
Think of splitting a data stream between two servers so each handles roughly half the traffic for optimal throughput.
Cache the prefix array once, then reuse it; avoid recomputing sums inside the binary search loop.
COMPLEXITY AT A GLANCE
O((N + Q) · log N)O(N)Core Theory — Why This Approach?
The optimal partition of a subarray into two contiguous non‑empty parts is achieved when the sum of the left part is as close as possible to half of the total sum of the range, because the product (or the balanced minimum) of two numbers with a fixed sum is maximized at equality. A naive solution would recompute the sum for every possible split inside each query, leading to O(N) per query and O(N·Q) overall, which is prohibitive for large N and Q. By pre‑computing a global prefix‑sum array we can obtain any sub‑range sum in O(1), and then locate the split point that approaches the half‑sum using binary search on the monotonic prefix‑sum values within the query interval, reducing each query to O(log N). This transforms the problem into a classic “search‑in‑sorted‑array” paradigm combined with prefix‑sum preprocessing, delivering an optimal O((N+Q)·log N) solution.
Interview Questions on This Problem
Q1Why does the product of two numbers with a fixed sum reach its maximum when the numbers are equal?
Because the product a·(S‑a) is a concave quadratic opening downwards, its vertex at a = S/2 gives the highest value.
Q2How does a prefix‑sum array enable O(1) range‑sum queries?
Each prefix entry stores the sum of elements up to that index; the sum of any subarray [L,R] is pref[R+1]‑pref[L].
Q3What is the time complexity of locating the split point using binary search on prefix sums?
Binary search on a monotonic segment runs in O(log N) time, independent of the segment length.
Examples
Input
nums = [1, 2, 3, 4, 5], queries = [[0, 4], [1, 3]]
Output
[1, 1]
Explanation: For query [0, 4], the subarray is [1, 2, 3, 4, 5] with total sum 15. Possible splits: - K=0: Left=1, Right=14, Diff=|1-14|=13 - K=1: Left=3, Right=12, Diff=|3-12|=9 - K=2: Left=6, Right=9, Diff=|6-9|=3 - K=3: Left=10, Right=5, Diff=|10-5|=5 Minimum cost is 3. For query [1, 3], the subarray is [2, 3, 4] with total sum 9. Possible splits: - K=1: Left=2, Right=7, Diff=|2-7|=5 - K=2: Left=5, Right=4, Diff=|5-4|=1 Minimum cost is 1.
Input
nums = [10, 10, 10, 10], queries = [[0, 3]]
Output
[0]
Explanation: For query [0, 3], the subarray is [10, 10, 10, 10] with total sum 40. Possible splits: - K=0: Left=10, Right=30, Diff=|10-30|=20 - K=1: Left=20, Right=20, Diff=|20-20|=0 - K=2: Left=30, Right=10, Diff=|30-10|=20 Minimum cost is 0.
Input
nums = [1, 1, 1, 1, 1, 1], queries = [[0, 5], [2, 4]]
Output
[0, 1]
Explanation: For query [0, 5], the subarray is [1, 1, 1, 1, 1, 1] with total sum 6. Possible splits: - K=0: Left=1, Right=5, Diff=4 - K=1: Left=2, Right=4, Diff=2 - K=2: Left=3, Right=3, Diff=0 - K=3: Left=4, Right=2, Diff=2 - K=4: Left=5, Right=1, Diff=4 Minimum cost is 0. For query [2, 4], the subarray is [1, 1, 1] with total sum 3. Possible splits: - K=2: Left=1, Right=2, Diff=1 - K=3: Left=2, Right=1, Diff=1 Minimum cost is 1.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- 1 <= queries.length <= 10^5
- 0 <= L < R < nums.length
- The sum of all elements in any subarray will not exceed 10^14
Optimal Approach & Strategy
Use a prefix‑sum array for O(1) range sums and binary search for the split point closest to half the total – O(log N) per query.
Brute Force Approach
Iterate K from L to R‑1, compute left and right sums each time, and keep the best partition – O(N) per query.
Code Solutions
function solution(nums, queries) {
let n = nums.length;
let res = [];
for (let i = 0; i < queries.length; i++) {
let L = queries[i][0];
let R = queries[i][1];
let minCost = Infinity;
for (let K = L; K < R; K++) {
let leftSum = nums.slice(L, K + 1).reduce((a, b) => a + b, 0);
let rightSum = nums.slice(K + 1, R + 1).reduce((a, b) => a + b, 0);
let cost = Math.abs(leftSum - rightSum);
if (cost < minCost) {
minCost = cost;
}
}
res.push(minCost);
}
return res;
}class Solution {
public:
vector<int> solution(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> res(queries.size());
for (int i = 0; i < queries.size(); i++) {
int L = queries[i][0];
int R = queries[i][1];
int minCost = INT_MAX;
for (int K = L; K < R; K++) {
int leftSum = 0;
int rightSum = 0;
for (int j = L; j <= K; j++) {
leftSum += nums[j];
}
for (int j = K + 1; j <= R; j++) {
rightSum += nums[j];
}
int cost = abs(leftSum - rightSum);
if (cost < minCost) {
minCost = cost;
}
}
res[i] = minCost;
}
return res;
}
}class Solution {
public int[] solution(int[][] nums, int[][] queries) {
int n = nums.length;
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int L = queries[i][0];
int R = queries[i][1];
int minCost = Integer.MAX_VALUE;
for (int K = L; K < R; K++) {
int leftSum = 0;
int rightSum = 0;
for (int j = L; j <= K; j++) {
leftSum += nums[j];
}
for (int j = K + 1; j <= R; j++) {
rightSum += nums[j];
}
int cost = Math.abs(leftSum - rightSum);
if (cost < minCost) {
minCost = cost;
}
}
res[i] = minCost;
}
return res;
}
}def solution(nums, queries):
n = len(nums)
res = []
for i in range(len(queries)):
L = queries[i][0]
R = queries[i][1]
minCost = float('inf')
for K in range(L, R):
leftSum = sum(nums[L:K + 1])
rightSum = sum(nums[K + 1:R + 1])
cost = abs(leftSum - rightSum)
if cost < minCost:
minCost = cost
res.append(minCost)
return resfunction solution(nums, queries) {
let n = nums.length;
let res = [];
for (let i = 0; i < queries.length; i++) {
let L = queries[i][0];
let R = queries[i][1];
let minCost = Infinity;
for (let K = L; K < R; K++) {
let leftSum = nums.slice(L, K + 1).reduce((a, b) => a + b, 0);
let rightSum = nums.slice(K + 1, R + 1).reduce((a, b) => a + b, 0);
let cost = Math.abs(leftSum - rightSum);
if (cost < minCost) {
minCost = cost;
}
}
res.push(minCost);
}
return res;
}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.