⚡Flashcard Drill➔
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

  1. Compute the total sum once, then sweep the split point while maintaining the left sum.
  2. At split index i (the first part being nums[0..i]), the condition is left >= total - left.
  3. Count the splits satisfying it. The split point only ranges over 0..n-2 so both parts are non-empty.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems