2270. Number of Ways to Split Array Medium

1/**
2 * [2270] Number of Ways to Split Array
3 *
4 * You are given a 0-indexed integer array nums of length n.
5 * nums contains a valid split at index i if the following are true:
6 * 
7 * The sum of the first i + 1 elements is greater than or equal to 
8 * the sum of the last n - i - 1 elements.
9 * There is at least one element to the right of i. That is, 0 <= i < n - 1.
10 * 
11 * Return the number of valid splits in nums.
12 *  
13 * Example 1:
14 * 
15 * Input: nums = [10,4,-8,7]
16 * Output: 2
17 * Explanation: 
18 * There are three ways of splitting nums into two non-empty parts:
19 * - Split nums at index 0. Then, the first part is [10], and its sum is
20 * 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, 
21 * i = 0 is a valid split.
22 * - Split nums at index 1. Then, the first part is [10,4], and its sum
23 * is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 
24 * is a valid split.
25 * - Split nums at index 2. Then, the first part is [10,4,-8], and its 
26 * sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is 
27 * not a valid split.
28 * Thus, the number of valid splits in nums is 2.
29 * 
30 * Example 2:
31 * 
32 * Input: nums = [2,3,1,0]
33 * Output: 2
34 * Explanation: 
35 * There are two valid splits in nums:
36 * - Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The
37 * second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
38 * - Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6.
39 * The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.
40 * 
41 *  
42 * Constraints:
43 * 
44 * 2 <= nums.length <= 10^5
45 * -10^5 <= nums[i] <= 10^5
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/number-of-ways-to-split-array/
51// discuss: https://leetcode.com/problems/number-of-ways-to-split-array/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn ways_to_split_array(nums: Vec<i32>) -> i32 {
57        let mut sum_right: i64 = nums.iter().map(|i| *i as i64).sum();
58        let mut sum_left: i64 = 0;
59        let mut result = 0;
60        for i in 0..nums.len() - 1 {
61            sum_right -= nums[i] as i64;
62            sum_left += nums[i] as i64;
63
64            if sum_left >= sum_right {
65                result += 1;
66            }
67        }
68        result
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_2270() {
80        assert_eq!(Solution::ways_to_split_array(vec![10,4,-8,7]), 2);
81        assert_eq!(Solution::ways_to_split_array(vec![2,3,1,0]), 2);
82    }
83}
84