LeetCode Entry

2270. Number of Ways to Split Array

03.01.2025 medium 2025 kotlin rust

Count splits left sum >= right sum sum

2270. Number of Ways to Split Array medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/853

Problem TLDR

Count splits left_sum >= right_sum #medium #prefix_sum

Intuition

Prefix sum can help solve this.

Approach

  • careful with an int overflow
  • this is not about the balance and con’t be done in a single pass, as adding negative number decreases the sum, we should hold left and right part separately

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun waysToSplitArray(nums: IntArray): Int {
        var r = nums.sumOf { it.toLong() }; var l = 0L
        return (0..<nums.lastIndex).count {
            l += nums[it]; r -= nums[it]; l >= r
        }
    }



    pub fn ways_to_split_array(nums: Vec<i32>) -> i32 {
        let (mut l, mut r) = (0, nums.iter().map(|&x| x as i64).sum());
        (0..nums.len() - 1).filter(|&i| {
            l += nums[i] as i64; r -= nums[i] as i64; l >= r
        }).count() as _
    }



    int waysToSplitArray(vector<int>& nums) {
        int res = 0; long long r = reduce(begin(nums), end(nums), 0LL), l = 0;
        for (int i = 0; i < nums.size() - 1; ++i)
            res += (l += nums[i]) >= (r -= nums[i]);
        return res;
    }