548. Split Array with Equal Sum

This page provides solutions for the leetcode problem 548. Split Array with Equal Sum.

Problem Explanation

The problem asks us to check if there is a triplet $\text{(i, j, k)}$ which satisfies the following conditions:

• $\text{0 < i, i + 1 < j, j + 1 < k < n - 1}$
• The sum of subarrays $\text{(0, i - 1), (i + 1, j - 1), (j + 1, k - 1)}$ and $\text{(k + 1, n - 1)}$ is equal.

Solution

This problem can be solved using the Prefix Array technique. More such questions can be found here.

Java

import java.util.HashSet;

class Solution {
  public boolean splitArray(int[] nums) {
    int[] prefix = new int[nums.length];
    prefix[0] = nums[0];

    // calculate prefix sums
    for(int i = 1; i < nums.length; i++) {
      prefix[i] = prefix[i - 1] + nums[i];
    }

    // picking value of 'j'
    for(int middle = 3; middle < nums.length; middle++) {
      HashSet<Integer> set = new HashSet<>();

      // picking value of 'i'
      for(int left = 1; left + 1 < middle; left++) {
        int first = sum(0, left - 1, prefix);
        int second = sum(left + 1, middle - 1, prefix);
        if (first == second) set.add(first);
      }

      // picking value of 'k'
      for(int right = middle + 2; right + 1 < nums.length; right++) {
        int third = sum(middle + 1, right - 1, prefix);
        int fourth = sum(right + 1, nums.length - 1, prefix);
        if(third == fourth && set.contains(third)) return true;
      }
    }
    return false;
  }

  // method to calculate sum within a range using prefix sums
  private int sum(int from, int to, int[] prefix) {
    return prefix[to] - (from - 1 > 0 ? prefix[from - 1] : 0);
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time complexity

To pick the triplet $\text{i, j}$, and $\text{k}$ we are running two for loop, so time complexity will be:

$$\text{O(N}^\text{2})$$

Space complexity

Solution uses prefix array and hashset which will have at most $\text{N}$ element, so space complexity will be:

$$\text{O(N)}$$