BackmediumTwo PointersMicrosoft

Galactic Supply Chain Optimization Solution

Problem Statement

Given an integer array nums, split it into two non‑empty contiguous parts by choosing a partition index i (0 ≤ i < nums.length‑1). The left part consists of elements nums[0]…nums[i] and the right part consists of nums[i+1]…nums[nums.length‑1]. Let L be the sum of the left part and R be the sum of the right part. Your task is to find the index i that minimizes the absolute difference |L‑R|. If several indices yield the same minimal difference, return the smallest such index. Output the chosen index.

Example 1
Input
[4,1,7,3,6]
Output
2

Explanation: Total sum = 21. Prefix sums: i=0 → L=4, R=17, |L‑R|=13; i=1 → L=5, R=16, |L‑R|=11; i=2 → L=12, R=9, |L‑R|=3 (minimum); i=3 → L=15, R=6, |L‑R|=9. The smallest index with the minimal difference is 2.

Example 2
Input
[10,-5,3,-2,8]
Output
2

Explanation: Total sum = 14. Prefix sums: i=0 → L=10, R=4, |L‑R|=6; i=1 → L=5, R=9, |L‑R|=4; i=2 → L=8, R=6, |L‑R|=2 (minimum); i=3 → L=6, R=8, |L‑R|=2 (same difference but larger index). The smallest index achieving the minimum is 2.

Example 3
Input
[1,2,3,4,5,6]
Output
3

Explanation: Total sum = 21. Prefix sums: i=0 → L=1, R=20, |L‑R|=19; i=1 → L=3, R=18, |L‑R|=15; i=2 → L=6, R=15, |L‑R|=9; i=3 → L=10, R=11, |L‑R|=1 (minimum); i=4 → L=15, R=6, |L‑R|=9. The optimal partition index is 3.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^9 ≤ nums[i] ≤ 10^9
  • The array contains at least two elements so a split is always possible
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Galactic Supply Chain Optimization — Problem Statement & Solution Guide

Two PointersMediumMixed
TimeO(n)
|
SpaceO(1)

Problem Description

Given an integer array nums, split it into two non‑empty contiguous parts by choosing a partition index i (0 ≤ i < nums.length‑1). The left part consists of elements nums[0]…nums[i] and the right part consists of nums[i+1]…nums[nums.length‑1]. Let L be the sum of the left part and R be the sum of the right part. Your task is to find the index i that minimizes the absolute difference |L‑R|. If several indices yield the same minimal difference, return the smallest such index. Output the chosen index.

DSA Pattern Breakdown

DSA Pattern Breakdown

"Galactic Supply Chain Optimization"

medium

WHY DOES IT MATTER?

The Two Pointers pattern is essential for problems involving contiguous subarrays, sliding windows, or partitioning. It allows us to solve problems that seem to require O(n^2) brute force in O(n) time by leveraging the relationship between adjacent states. In this specific case, it highlights the power of prefix sums and the ability to derive one part of a partition from the whole and the other part.

OPTIMIZATION CHALLENGE

The key optimization is recognizing that the sum of the right part is not independent of the left part. Instead of calculating two separate sums for each partition, we calculate the total sum once and then use a running sum for the left part to derive the right part. This reduces the number of arithmetic operations from O(n^2) to O(n).

REAL-WORLD CONNECTION

This pattern is analogous to load balancing in distributed systems. Imagine you have a list of tasks (the array) and you need to split them into two batches for two servers. You want to minimize the difference in total processing time (sum) between the two servers to ensure balanced load. The two-pointer approach efficiently finds the optimal split point without recalculating the load for each server from scratch.

In an interview, explicitly state the time complexity of the naive approach first to show you understand the problem's constraints. Then, introduce the prefix sum optimization as a natural extension. Mention that this pattern is a special case of the 'sliding window' or 'prefix sum' techniques, which are fundamental in array processing.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)
💾 Space:O(1)

Core Theory — Why This Approach?

The problem of minimizing the absolute difference between two contiguous partitions of an array is a classic application of the Two Pointers technique, specifically leveraging the concept of prefix sums. A naive approach would involve iterating through every possible partition index and calculating the sum of the left and right subarrays from scratch for each index. This results in a time complexity of O(n^2), which is computationally expensive for large arrays (e.g., n = 10^5). The key insight is that the sum of the right part can be derived from the total sum of the array and the sum of the left part. By maintaining a running sum of the left part as we iterate from left to right, we can compute the right part's sum in constant time using the formula: RightSum = TotalSum - LeftSum. This reduces the time complexity to O(n), as we only need a single pass through the array.

Interview Questions on This Problem

Q1How would you modify this solution if the array contained negative numbers? Does the two-pointer approach still hold?

Yes, the approach remains valid. The logic relies on the algebraic identity R = Total - L, which holds regardless of the sign of the elements. The absolute difference |L - R| is still minimized by finding the partition where L is closest to Total/2. The only change is that the 'closest' value might not be monotonic in the same way if we were searching for a specific target, but since we are simply scanning all possible partitions, the O(n) linear scan remains optimal and correct.

Q2In a distributed system context, if this array represents a time-series log of events, how would you handle the case where the array is too large to fit in memory?

If the array is too large to fit in memory, we can use an external sorting or streaming approach. However, since we need contiguous partitions, we must process the data in order. We can compute the total sum in a first pass (if the data is seekable) or store the total sum in a metadata header. Then, in a second pass, we stream the elements, maintaining a running left sum. This requires O(1) extra space (excluding the input storage) and O(n) time, assuming we can read the data sequentially. If random access is not possible, we might need to buffer a small window, but for contiguous sums, sequential access is sufficient.

Q3What if we needed to find the partition that minimizes the difference between the *maximum* element in the left part and the *maximum* element in the right part, instead of the sum?

This changes the problem significantly. We can no longer use the simple prefix sum trick. We would need to precompute the maximum of the left part for each index (LeftMax[i]) and the maximum of the right part for each index (RightMax[i]). LeftMax can be computed in a forward pass, and RightMax in a backward pass. Then, we iterate through the array to find the index i that minimizes |LeftMax[i] - RightMax[i+1]|. This still results in O(n) time and O(n) space (for the two auxiliary arrays), or O(1) space if we can recompute or use a more complex in-place strategy, but O(n) space is standard for clarity.

Examples

Example 1

Input

[4,1,7,3,6]

Output

2

Explanation: Total sum = 21. Prefix sums: i=0 → L=4, R=17, |L‑R|=13; i=1 → L=5, R=16, |L‑R|=11; i=2 → L=12, R=9, |L‑R|=3 (minimum); i=3 → L=15, R=6, |L‑R|=9. The smallest index with the minimal difference is 2.

Example 2

Input

[10,-5,3,-2,8]

Output

2

Explanation: Total sum = 14. Prefix sums: i=0 → L=10, R=4, |L‑R|=6; i=1 → L=5, R=9, |L‑R|=4; i=2 → L=8, R=6, |L‑R|=2 (minimum); i=3 → L=6, R=8, |L‑R|=2 (same difference but larger index). The smallest index achieving the minimum is 2.

Example 3

Input

[1,2,3,4,5,6]

Output

3

Explanation: Total sum = 21. Prefix sums: i=0 → L=1, R=20, |L‑R|=19; i=1 → L=3, R=18, |L‑R|=15; i=2 → L=6, R=15, |L‑R|=9; i=3 → L=10, R=11, |L‑R|=1 (minimum); i=4 → L=15, R=6, |L‑R|=9. The optimal partition index is 3.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^9 ≤ nums[i] ≤ 10^9
  • The array contains at least two elements so a split is always possible

Optimal Approach & Strategy

Calculate the total sum of the array once. Iterate through the array, maintaining a running sum for the left part. For each index, compute the right part's sum as TotalSum - LeftSum, calculate the absolute difference, and update the minimum difference and index if the current difference is smaller.

Brute Force Approach

Iterate through every possible partition index i from 0 to n-2. For each i, calculate the sum of nums[0...i] and nums[i+1...n-1] separately, compute the absolute difference, and keep track of the minimum difference and its corresponding index.

Verified Code Solutions

JavaScript Solution
Time: O(n)
function findPartition(nums){
    const n = nums.length;
    if(n<2) return -1;
    let total = 0n;
    for(const v of nums) total += BigInt(v);
    let left = 0n;
    let bestDiff = null;
    let bestIdx = -1;
    for(let i=0;i<n-1;i++){
        left += BigInt(nums[i]);
        const right = total - left;
        const diff = left>right ? left-right : right-left;
        if(bestDiff===null || diff < bestDiff){
            bestDiff = diff;
            bestIdx = i;
        }
    }
    return bestIdx;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
    const n = data[0];
    const nums = data.slice(1,1+n);
    console.log(findPartition(nums).toString());
}

Asked in Top Tech Interviews

Microsoft

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.