Java O(n2) solution - beats 99%of submissions


  • 0
    M

    This question is a good example to use DFS and DP. However, using a simple O(n2) solution is the most efficient here as the boundaries are -
    a. Each of the array element will not exceed 100.
    b. The array size will not exceed 200.

    public class Solution {
        public boolean canPartition(int[] nums) {
            if(nums == null || nums.length == 0)
                return true;
            
            int sum = 0;
            for(int num : nums)
                sum += num;
            
            if(sum % 2 != 0)
                return false;
            
            int i = 0;
            while(i < nums.length) {
                int currSum = nums[i];
                if (currSum == sum/2)
                    return true;
                
                int currIndex = i+1;
                while(currIndex < nums.length) {
                    if (currSum + nums[currIndex] == sum/2) {
                        return true;
                    } else if(currSum + nums[currIndex] < sum/2) {
                        currSum += nums[currIndex];
                        currIndex++;
                    } else {
                        currIndex++;
                    }
                }
                i++;
            }
            return false;
        }
    }
    

  • 0
    T

    It will give wrong answer if input array is [4,5,6,7,10];


Log in to reply
 

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