NeetCode #130LC-2270MediumArrays & Hashing
← Back to All Problems#130 · #2270 · Number of Ways to Split Array(分割数组的方案数)
📌 Problem Statement & Constraints
Given an array
nums, count the number of ways to split it into two non-empty parts such that the sum of the first part is at least the sum of the second part. Constraints: 2 <= nums.length <= 10^5, -10^5 <= nums[i] <= 10^5.💡 Core Algorithmic Approaches
- Compute the total sum once, then sweep the split point while maintaining the left sum.
- At split index
i(the first part beingnums[0..i]), the condition isleft >= total - left. - Count the splits satisfying it. The split point only ranges over
0..n-2so both parts are non-empty. - Avoid recomputing
sum(nums[:i])inside the loop, which would be O(n^2).
💻 Benchmark Python3 Implementation
class Solution:
def waysToSplitArray(self, nums: List[int]) -> int:
total = sum(nums)
left = 0
res = 0
for i in range(len(nums) - 1): # the right part must be non-empty
left += nums[i]
if left >= total - left: # left sum at least the right sum
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass for the total and one for the splits.
💾 Space Complexity
O(1): two accumulators.
⚠️ Interview Pitfalls & Follow-ups
- Using
>instead of>=: the condition is *at least*, so equality counts. - Including
i == n - 1: the right part would be empty, which is not a valid split. - Recounting the prefix sum each iteration: O(n^2); maintain it incrementally.
- Assuming all values are non-negative: the constraints allow negatives, so the left sum is not monotone -- but the direct comparison still works because we simply test every split.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.