1712. Ways to Split Array Into Three Subarrays LeetCode Solution

In this guide, you will get 1712. Ways to Split Array Into Three Subarrays LeetCode Solution with the best time and space complexity. The solution to Ways to Split Array Into Three Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Ways to Split Array Into Three Subarrays solution in C++
Ways to Split Array Into Three Subarrays solution in Java
Ways to Split Array Into Three Subarrays solution in Python
Additional Resources

1712. Ways to Split Array Into Three Subarrays LeetCode Solution image

Problem Statement of Ways to Split Array Into Three Subarrays

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays – named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 109 + 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].
Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 105
0 <= nums[i] <= 104

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1712. Ways to Split Array Into Three Subarrays LeetCode Solution in C++

class Solution {
 public:
  int waysToSplit(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    int ans = 0;
    vector<int> prefix(n);

    partial_sum(nums.begin(), nums.end(), prefix.begin());

    // Finds the first index j s.t.
    // mid = prefix[j] - prefix[i] >= left = prefix[i].
    auto firstGreaterEqual = [&](int i) {
      int l = i + 1;
      int r = n - 1;
      while (l < r) {
        const int m = (l + r) / 2;
        if (prefix[m] - prefix[i] >= prefix[i])
          r = m;
        else
          l = m + 1;
      }
      return l;
    };

    // Finds the first index k s.t.
    // mid = prefix[k] - prefix[i] > right = prefix[-1] - prefix[k].
    auto firstGreater = [&](int i) {
      int l = i + 1;
      int r = n - 1;
      while (l < r) {
        const int m = (l + r) / 2;
        if (prefix[m] - prefix[i] > prefix.back() - prefix[m])
          r = m;
        else
          l = m + 1;
      }
      return l;
    };

    for (int i = 0; i < n - 2; ++i) {
      const int j = firstGreaterEqual(i);
      if (j == n - 1)
        break;
      const int mid = prefix[j] - prefix[i];
      const int right = prefix.back() - prefix[j];
      if (mid > right)
        continue;
      const int k = firstGreater(i);
      ans = (ans + k - j) % kMod;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1712. Ways to Split Array Into Three Subarrays LeetCode Solution in Java

class Solution {
  public int waysToSplit(int[] nums) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    int ans = 0;
    int[] prefix = nums.clone();

    for (int i = 1; i < n; ++i)
      prefix[i] += prefix[i - 1];

    for (int i = 0; i < n - 2; ++i) {
      final int j = firstGreaterEqual(prefix, i);
      if (j == n - 1)
        break;
      final int mid = prefix[j] - prefix[i];
      final int right = prefix[prefix.length - 1] - prefix[j];
      if (mid > right)
        continue;
      final int k = firstGreater(prefix, i);
      ans = (ans + k - j) % kMod;
    }

    return ans;
  }

  // Finds the first index j s.t.
  // mid = prefix[j] - prefix[i] >= left = prefix[i].
  private int firstGreaterEqual(int[] prefix, int i) {
    int l = i + 1;
    int r = prefix.length - 1;
    while (l < r) {
      final int m = (l + r) / 2;
      if (prefix[m] - prefix[i] >= prefix[i])
        r = m;
      else
        l = m + 1;
    }
    return l;
  };

  // Finds the first index k s.t.
  // mid = prefix[k] - prefix[i] > right = prefix[-1] - prefix[k].
  private int firstGreater(int[] prefix, int i) {
    int l = i + 1;
    int r = prefix.length - 1;
    while (l < r) {
      final int m = (l + r) / 2;
      if (prefix[m] - prefix[i] > prefix[prefix.length - 1] - prefix[m])
        r = m;
      else
        l = m + 1;
    }
    return l;
  };
}
// code provided by PROGIEZ

1712. Ways to Split Array Into Three Subarrays LeetCode Solution in Python

class Solution:
  def waysToSplit(self, nums: list[int]) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    ans = 0
    prefix = list(itertools.accumulate(nums))

    def firstGreaterEqual(i: int) -> int:
      """Finds the first index j s.t.
         Mid = prefix[j] - prefix[i] >= left = prefix[i]
      """
      l = i + 1
      r = n - 1
      while l < r:
        m = (l + r) // 2
        if prefix[m] - prefix[i] >= prefix[i]:
          r = m
        else:
          l = m + 1
      return l

    def firstGreater(i: int) -> int:
      """Finds the first index k s.t.
         mid = prefix[k] - prefix[i] > right = prefix[-1] - prefix[k]
      """
      l = i + 1
      r = n - 1
      while l < r:
        m = (l + r) // 2
        if prefix[m] - prefix[i] > prefix[-1] - prefix[m]:
          r = m
        else:
          l = m + 1
      return l

    for i in range(n - 2):
      j = firstGreaterEqual(i)
      if j == n - 1:
        break
      mid = prefix[j] - prefix[i]
      right = prefix[-1] - prefix[j]
      if mid > right:
        continue
      k = firstGreater(i)
      ans = (ans + k - j) % kMod

    return ans
 # code by PROGIEZ