Lazy java 27ms O(n^2) solution explained.


  • 1
    Q

    The point in this algorithm is to do as less work as possible. And if we already found the answer, the program should stop immediately.
    In the first round, I compute all possible sum for the 4th subarray.
    In the second round, I check if there is a possibility that the sum of 1st subarray is the same as the 4th subarray.
    In the last round, I check if I can found a valid j value and stop when I found it.
    The best case: O(N); the worst case: O(N^2).
    Welcome to any optimization!

    public static boolean splitArray(int[] nums) {
            if(nums.length < 7) return false;
            int sum = nums[nums.length - 1];
            HashMap<Integer, LinkedList<Integer>> map = new HashMap();
            for(int i = nums.length - 2; i > 0; i--) {
            	if(map.containsKey(sum)) map.get(sum).add(i);
            	else {
            		LinkedList<Integer> tmp = new LinkedList();
            		tmp.add(i);
            		map.put(sum, tmp);
            	}
            	sum += nums[i];
            }
            sum = nums[0];
            for(int i = 1; i < nums.length - 5; i++) {
            	if(map.containsKey(sum)) {
            		LinkedList<Integer> list = map.get(sum);
            		for(Integer k : list) {
            			if(k > i + 3 && checker(sum, nums, i + 1, k - 1)) return true;
            		}
            	}
            	sum += nums[i];
            }
            return false;
        }
    	
    	private static boolean checker(int target, int[] array, int start, int end) {
    		int sum = 0;
    		for(int i = start; i <= end; i++) sum += array[i];
    		int left = array[start], right = sum - array[start] - array[start + 1];
    		for(int i = start + 1; i < end; i++) {
    			if(left == right && left == target) return true;
    			else {
    				left += array[i];
    				right -= array[i + 1];
    			}
    		}
    		return false;
    	}
    

  • 0
    Z

    @qswawrq Nice solution to calculate 4th array first to handle the test case
    [0 0 0 0 0 ... 1 1 1 1 1 1 1 1 ]! However, I think your solution is still O(n^3) in the worst case. For example,
    [0 0 0 0 0 0 ... 01 1 1 1 1 1 1 1 1..1 0 0 0 ... 0], which has n/3 0s, n/3 1s, and n/3 0s.
    The function checker() is O(n); for i = 1 to n/3, list = map.get(0) size is n/3, so the total time is O(n^3).


Log in to reply
 

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