JP Morgan·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

JP Morgan software engineer interview with a logistics-style coding problem. Nothing too wild but the problem had a subtle constraint that tripped me up at first.

Questions Asked (1)

You have an array of n item quantities. Split the array into two non-empty parts at some index j, where the first part is items 1 through j and the second is the rest. You can increment or decrement any item's quantity by 1 as many times as you want, but no quantity can drop to zero or below. Find the minimum total operations to make the sum of both parts equal, over all possible split points.

Algorithms & Data Structures

Author's notes

The positive quantity constraint is what got me initially.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the total sum must be even for equal partition sums, otherwise it's impossible. Then, for each split point j, compute the difference between the sum of the first part and half of the total sum, and the minimum operations is the absolute value of that difference, provided no element becomes non-positive. Finally, take the minimum over all valid splits.

Pro tip: Mention that the non-positive constraint is automatically satisfied if the target sum for each part is at least the number of elements in that part, since each element must be at least 1. This shows you consider edge cases and constraints.

1. Understand the problem and constraints

Restate the problem: we need to split the array into two non-empty contiguous parts and adjust quantities so both parts have equal sum, minimizing total increments/decrements. Note that each quantity must remain at least 1.

2. Check feasibility

If the total sum S is odd, equal partition sums are impossible because the sum of both parts must be S and each part must be an integer. So return -1 or indicate impossibility.

3. Compute prefix sums

Precompute prefix sums to quickly get the sum of the first part for any split point j. The second part sum is S minus the first part sum.

4. Evaluate each split point

For each j from 1 to n-1, compute the difference d = |prefixSum[j] - S/2|. The minimum operations for this split is d, provided that after adjustments no element becomes ≤0. Check that the target sum for each part is at least the number of elements in that part (since each element ≥1).

5. Return the minimum

Track the minimum d over all valid splits and return it. If no valid split exists, return -1.

Key Points to Mention

Total sum must be even for equal partition sums; otherwise impossible.
Use prefix sums to compute part sums in O(1) per split.
Minimum operations for a split is the absolute difference between the part sum and half the total sum.
Ensure no element becomes non-positive: target sum for each part must be at least the number of elements in that part.
Time complexity O(n) after prefix sums, space O(n) or O(1) if prefix sums computed on the fly.
Edge cases: n=1 (no split possible), all elements 1, large differences.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.