Optimal Range Partitioning — Problem Statement & Solution Guide
Problem Description
You are given an array of non-negative integers nums and a 2D array queries where queries[i] = [L, R]. For each query, you need to partition the subarray nums[L...R] into two non-empty contiguous parts: a left part nums[L...K] and a right part nums[K+1...R] (where L <= K < R). The partition cost is the absolute difference between the sum of the left part and the sum of the right part. Find the minimum possible partition cost for each query and return them as an array of integers.
Examples
Input
[1, 2, 3, 4] queries = [[1, 3], [1, 4]]
Output
[1, 2]
Explanation: Step 1: For the first query [1, 3], we need to find the minimum cost partition. The possible partitions are [1, 2] and [3], [1, 3] and [2]. The partition costs are |1+2-3| = 2 and |1+3-2| = 1. The minimum cost is 1. Step 2: For the second query [1, 4], we need to find the minimum cost partition. The possible partitions are [1, 2] and [3, 4], [1, 3] and [2, 4], [1, 4] and [2, 3]. The partition costs are |1+2-3-4| = 6, |1+3-2-4| = 2, |1+4-2-3| = 2. The minimum cost is 2.
Input
[1, 2, 3, 4] queries = [[2, 4], [3, 4]]
Output
[2, 1]
Explanation: Step 1: For the first query [2, 4], we need to find the minimum cost partition. The possible partitions are [2, 3] and [4], [2, 4] and [3]. The partition costs are |2+3-4| = 1 and |2+4-3| = 1. The minimum cost is 1. Step 2: For the second query [3, 4], we need to find the minimum cost partition. The possible partitions are [3, 4] and [], [3] and [4]. The partition costs are |3+4-0| = 7 and |3+0-4| = 1. The minimum cost is 1.
Constraints
- 2 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^4
- 1 <= queries.length <= 10^5
- queries[i].length == 2
- 0 <= L < R < nums.length
Optimal Approach & Strategy
We precompute a prefix sum array to perform range sum queries in O(1) time. Since all array elements are non-negative, the prefix sums are monotonically increasing. For each query [L, R], we can binary search within the bounds [L, R-1] to find the partition index K that minimizes the difference. This reduces the query time to O(log N), giving a total time complexity of O(N + Q log N).
Brute Force Approach
For each query [L, R], we iterate through all possible split points K from L to R-1. For each split, we calculate the sum of the left subarray [L...K] and the right subarray [K+1...R] and compute their absolute difference. We track the minimum difference found, resulting in an O(Q * N) overall time complexity.
Verified 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.