Equal Sum Split After One Removal
Google● MediumINTERNFULLTIMEPHONE SCREENONSITE INTERVIEWProblem statement
Given an array nums of positive integers, remove exactly one element while preserving the relative order of all remaining elements.
If nums contains one element, return true: deleting it leaves an empty sequence, and this singleton case treats two empty parts as having equal sum 0.
For every longer input, return true if the remaining sequence can be split into two non-empty contiguous subarrays with equal sums. Otherwise, return false. In particular, an input with two elements returns false.
Removal and split rules
- You may choose any one index to remove.
- After the removal, every remaining element must belong to exactly one of the two subarrays.
- Both subarrays must be contiguous in the remaining sequence.
- Empty parts are permitted only for the explicit singleton case. An empty input array is outside the valid input domain.
Function
canSplitAfterRemoval(nums: int[]) → booleanExamples
Example 1
nums = [1,2,3,3]return = trueRemove the last 3. The remaining sequence is [1,2,3], which splits into [1,2] and [3]. Both sums are 3.
Example 2
nums = [1,2,5]return = falseEvery removal leaves two unequal single-element subarrays, so no valid split exists.
Example 3
nums = [2,1,1,2]return = trueRemove the first 2. The remaining sequence [1,1,2] splits into [1,1] and [2], each with sum 2.
Example 4
nums = [7]return = trueThe explicit singleton rule applies: deleting 7 leaves an empty sequence, treated as two empty parts of sum 0.
Example 5
nums = [2,2]return = falseDeleting either element leaves only one value. The singleton exception applies to the original input length, so this remaining value cannot form two non-empty parts.
Constraints
1 <= nums.length <= 2 * 10^51 <= nums[i] <= 10^9