Java solution, DFS


  • 7

    Just think this problem as a DFS. What we need is to search for 3 positions (i, j, k) and see if they divide the array to 4 parts with same summary. Some tricks:

    1. Calculate left on the fly. Thus at last we don't need to calc summary of the 4th part.
    2. Skip 0 during calculate target because adding zero won't change it.
    public class Solution {
        public boolean splitArray(int[] nums) {
            int sum = 0, target = 0;
            for (int num : nums) sum += num;
            for (int i = 1; i + 5 < nums.length; i++) {
                if (i != 1 && nums[i - 1] == 0  && nums[i] == 0) continue;
                target += nums[i - 1];
                if (dfs(nums, i + 1, target, sum - target - nums[i], 1)) return true;
            }
            return false;
        }
        
        private boolean dfs(int[] nums, int start, int target, int left, int depth) {
            if (depth == 3) {
                if (left == target) return true;
                return false;
            }
            
            int sub = 0;
            for (int j = start + 1; j + 5 - depth * 2 < nums.length; j++) {
                sub += nums[j - 1];
                if (sub == target) {
                    if (dfs(nums, j + 1, target, left - sub - nums[j], depth + 1)) {
                        return true;
                    }
                }
            }
            
            return false;
        }
    }
    

  • 0

    Good Solution, Thanks!


  • 0
    P

    @shawngao
    Although the test cases can be passed, I don't think the trick of skipping 0 would be correct because that will ignore the possible split point right after 0. For example, this simple test case [0,0,1,0,1,0,1,0] will lead to incorrect result. I came up with this because I wrote something similar to you but got time limit exceeded... -_-!


  • 0

    @polarvenezia Thanks for pointing out the bug. Just fixed that by adding another condition && nums[i] == 0


  • 0
    P

    @shawngao Yes that will make a lot more sense! Nice solution.


  • 0

    I came up with the similar idea but afterwards I realized it is an O(n^3) solution, although you got AC through the 'skipping 0' trick. Basically, an O(n^2) solution with hash table may do a better job.


  • 0
    I

    Similar Idea and borrowed your idea to skip 0.

    public boolean splitArray(int[] nums) {
        if (nums.length < 6) {
            return false;
        }
        int target = 0;
        int c = 3;
        for (int i = 0; i + c * 2 < nums.length; i++) {
            if (i < nums.length - 1 && nums[i + 1] == 0  && nums[i] == 0) continue;
            target += nums[i];
            if (helper(nums, i + 2, target, c - 1)) {
                return true;
            }
        }
        return false;
    }
    
    public boolean helper(int[] nums, int start, int target, int c) {
        if (start > nums.length && c == -1) {
            return true;
        } if (c < 0) {
            return false;
        }
        int sum = 0;
        for (int i = start; i + c * 2 < nums.length; i++) {
            sum += nums[i];
            if (sum == target && helper(nums, i + 2, target, c - 1)) {
                return true;
            }
        }
        return false;
    }

  • 1
    Z

    Is the time complexity O(n^3)?
    It seems that the optimization is to skip continuous 0s. What if replacing 0 with -1 1 pairs? For example,
    [1 -1 1 -1 1 -1 1 -1 1 -1 .... 1 1 1 1 1 1 1]


  • 0
    J

    Trick no. 2 is so important that my similar solution beat 95+% but TLE without it. Thanks a lot man.


  • 0
    J

    @zestypanda Seems like it's worse case O(n^3) and hard to avoid with this approach. I think that zero skipping trick is designed for specific test cases (e.g. no. 115 which I previously stuck at). It's legit to do so though.


  • 1
    Z

    @JasonX By the end, we are targeting interviews instead of test cases.


Log in to reply
 

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