Split an array into two halves with equal sums
I was asked this
No reports yet. Sign in to say where you were asked it.
You are given an array nums of positive integers. Find an index i that splits it into two non-empty contiguous parts with the same sum:
- the left part is
nums[0..i](it includesnums[i]), - the right part is
nums[i+1..n-1].
Return i, or -1 if no such index exists.
def find_split_index(nums: list[int]) -> int: ...
Constraints
0 <= len(nums) <= 10^51 <= nums[k] <= 10^9- Both parts must contain at least one element.
Example 1
nums = [4, 2, 3, 3]
output: 1
Left [4, 2] sums to 6 and right [3, 3] sums to 6.
Example 2
nums = [1, 2, 5]
output: -1
The total is 8, but no prefix sums to 4 (the prefixes are 1, 3, 8).
Aim for O(n) time and O(1) extra space.
Reconstructed from the reported question; details may differ from what interviewers ask.
Sign in to see the worked answer
The full answer, chapter by chapter, with what interviewers expect at each level. Free with an account: one full answer per company.
Sign in to see the worked answer
The full answer, chapter by chapter, with what interviewers expect at each level. Free with an account: one full answer per company.
Sign in to submit your code; every attempt is kept here.
