Binary search 11ms beats 98.31%


  • 0
    I

    I'm not so sure about the complexity. It looks like it would be O(n^2 log(n)) but in practice it's very fast (at least with the OJ's test case) beating 97.51%, so I think it would be around O(nlogn) in practice.

    The basic idea is to sort the array, calculate half of the total sum.
    Create a variable called currentSum, then use binary search to look for the element that if add it to our currentSum we'll get closest to the halfsum. If that element is in the array already, it means the array can be partitioned.

    One small note here is when I was designing this algo, I thought I could do it O(nlogn) (without the outer while loop), but the inner while loop alone would fall test case like:
    2 3 4 6 15 20

    So I added the outer while loop which makes the algo runs correctly but to me, that could lead to worst case is n^2 * log(n)

    Anyways, no more bs, here is the code.

            public boolean canPartition(int[] nums) {
                int sum = 0;
                for (int i : nums) sum += i;
                if ((sum & 1) == 1) return false;
                int half = sum / 2;
    
                Arrays.sort(nums);
    
                int start = nums.length;
    
                while (start > 0) {
                    int right = start;
                    int goal = half;
                    while (true) {
                        int idx = Arrays.binarySearch(nums, 0, right, goal);
                        if (idx >= 0) {
                            return true;
                        } else {
                            if (idx < 0) idx = ~idx;
                            if (idx == 0) break;
                            idx--; // get the one right before
                            goal -= nums[idx];
                            right = idx; // from now, we'll only search in the right size of idx
                        }
                    }
                    start--;
                }
                return false;
            }
    

Log in to reply
 

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