Simple Java solution O(n^2)


  • 46

    Here j is used for middle cut, i for left cut and k for right cut.
    Iterate middle cuts and then find left cuts which divides the first half into two equal quarters, store that quarter sums in the hashset. Then find right cuts which divides the second half into two equal quarters and check if quarter sum is present in the hashset. If yes return true.

    public class Solution {
        public boolean splitArray(int[] nums) {
            if (nums.length < 7)
                return false;
            int[] sum = new int[nums.length];
            sum[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                sum[i] = sum[i - 1] + nums[i];
            }
            for (int j = 3; j < nums.length - 3; j++) {
                HashSet < Integer > set = new HashSet < > ();
                for (int i = 1; i < j - 1; i++) {
                    if (sum[i - 1] == sum[j - 1] - sum[i])
                        set.add(sum[i - 1]);
                }
                for (int k = j + 2; k < nums.length - 1; k++) {
                    if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))
                        return true;
                }
            }
            return false;
        }
    }

  • 0
    D

    Neat!
    Your solutions shows that you have a thorough understanding of this question.


  • 0

    Clear and concise.


  • 0
    Y

    why [1,4,1,3,1,-14,1,-13] return false. it shoudl be true for i = 1, j = 3, k = 6 match.
    [1,4,1,3,1,-14,1,-13]
    i = 1, j = 3, k = 6
    sum(0, i - 1) = sum(0, 0) = 1
    sum(i + 1, j - 1) = sum(2, 2) = 1
    sum(j + 1, k - 1) = sum(4, 5) = 1 + (-14) = -13
    sum(k + 1, n - 1) = sum(7, 7) = -13


  • 1

    @yin10 If all four sums are equal, then only return true.


  • 0
    Y

    @vinod23 thanks for your clear reply.


  • 1

    Another approach. Applying careful bruteforce. Beats 85% submissions.

    public boolean splitArray(int[] nums) {
        if (nums.length < 7) return false;
        int [] sums = new int [nums.length];
        sums [0] = nums [0];
        for (int idx = 1; idx < nums.length; idx ++) sums [idx] += sums [idx - 1] + nums [idx];
            
        for (int idx1 = 1; idx1 < nums.length - 5; idx1 ++) {
            if (idx1 == 1 || sums [idx1 - 2] != sums [idx1 - 1]) {
                int s1 = sums [idx1 - 1];
                for (int idx2 = idx1 + 2; idx2 < nums.length - 3; idx2 ++) {
                    int s2 = sums [idx2 - 1] - sums [idx1];    
                    if (s1 == s2) {
                        for (int idx3 = idx2 + 2; idx3 < nums.length - 1; idx3 ++) {
                            int s3 = sums [idx3 - 1] - sums [idx2];        
                            int s4 = sums [sums.length - 1] - sums [idx3];    
                            if (s2 == s3 && s3 == s4) return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    

  • 0

    Why do we need presum? Can't we iterate through all elements from 0 to j for left and right, then just update them for different i? This is an O(n) operation so it will not add to the overall complexity.
    (e.g., left += nums[i-1], right -= nums[i])

    Also, why do we need a hash set? Is it possible for the subarrays to have multiple equal values?

    Thanks for reading this and I would really appreciate an answer. :)


  • 1
    Q

    @cannot_stop_eatingT-T
    for you second question, because there might exist multiple equal values for the subarray.
    considering the following subarray 3,2,1,-1,6, if we separate from 1, then both ends have the equal value of 5, if we separate from -1, then both ends have the equal value of 6.


  • 0
    M

    @vinod23 thanks for sharing. A C++ version:

        bool splitArray(vector<int>& nums) {
            int n = nums.size();
            if(n < 7) return false;
            vector<int> sum(n);
            sum[0] = nums[0];
            for(int i = 0; i < n; ++i) sum[i] = sum[i - 1] + nums[i];
            
            for(int j = 3; j < n - 3; ++j){
                unordered_set<int> st;
                for(int i = 1; i < j - 1; ++i)
                    if(sum[i - 1] == sum[j - 1] - sum[i])
                        st.insert(sum[i - 1]);
                for(int k = j + 2; k < n - 1; ++k)
                    if(sum[k - 1] - sum[j] == sum[n - 1] - sum[k] && st.count(sum[k - 1] - sum[j]))
                        return true;
            }
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.