454. 4Sum II (Medium)

https://leetcode.com/problems/4sum-ii/

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

 

Solutions

1.

class Solution {

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int count = 0;

        // check corner case
        if (A == null || A.length == 0) {
            return count;
        }

        int len = A.length;

        // Sort four arrays
        Arrays.sort(A);
        Arrays.sort(B);
        Arrays.sort(C);
        Arrays.sort(D);

        // Fixate array A and B
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {

                // Traverse C from left to right
                int left = 0;

                // Traverse D from right to left
                int right = len - 1;

                while (left < len && right >= 0) {
                    // In case of overflow issue
                    long sum = A[i] * 1l + B[j] * 1l + C[left] * 1l + D[right] * 1l;

                    // Increase count by 1 once find combination sums up to zero. Meanwhile, move either
                    // left or right to search for new pairs.
                    if (sum == 0) {
                        int cRepeatNum = 1;
                        int dRepeatNum = 1;

                        while(left < len - 1 && C[left] == C[left + 1]) {
                            left++;
                            cRepeatNum++;
                        }

                        while (right > 0 && D[right] == D[right - 1]) {
                            right--;
                            dRepeatNum++;
                        }

                        left++;
                        right--;

                        /*

                        // forever loop issue

                        while(left < len - 1 && C[left] == C[++left]) {
                            cRepeatNum++;
                        }

                        while (right > 0 && D[right] == D[--right]) {
                            dRepeatNum++;
                        }
                        */

                        count += cRepeatNum * dRepeatNum;

//                            System.out.println(A[i] + ", " + B[j] + ", " + C[left] + ", " + D[right]);

                        /*
                        // FIXME Didn't consider situation C=[0, 0, 1], left=0, D=[1,1,1], right=2;

                        // Imagine that array C has already fully scanned and D still remains a few candidates
                        // to be visited. As a consequence, we cannot move either left or right randomly which
                        // is determined by the specific situation.

                        // In case left pointer has already hit the right boundary. If left pointer gets to
                        // the right boundary, move right pointer if it is still movable.
                        if (left == len - 1) {
                            right--;
                        } else {
                            left++;
                        }
                        */
                    }
                    // move left pointer to propose larger value such that sum gets close to 0
                    else if (sum < 0) {
                        left++;
                    }
                    // move right pointer to propose smaller value such that sum gets close to 0
                    else {
                        right--;
                    }
                }
            }
        }

        // return ans;
        return count;
    }
}

2.

class Solution2 {

    // Brute force solution to validate above solution's answer.

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        // Sort four arrays
        Arrays.sort(A);
        Arrays.sort(B);
        Arrays.sort(C);
        Arrays.sort(D);

        int len = A.length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int m = 0; m < len; m++) {
                    for (int n = 0; n < len; n++) {
                        if (A[i] + B[j] + C[m] + D[n] == 0) {
//                                System.out.println(i + ", " + j + ", " + m + ", " + n);
                            System.out.println(A[i] + ", " + B[j] + ", " + C[m] + ", " + D[n]);
                        }
                    }
                }
            }
        }

        return 0;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""