LeetCode: 4Sum II

-
https://leetcode.com/problems/4sum-ii/, here is the problem copied/pasted for easy access:

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
With the input in the N=500 range, it is clear that an N^4 solution won't work (62,500,000,000) or even an N^3 solution would take some non-negligible time (125,000,000). The goal is to try to come up with something better: an N^2 solution might do the trick here (250,000). Here is the approach:

  • Go thru each element c of C and each element d of D and add that sum (c+d) to a hash table
  • In case that sum already exists, increment its count
  • Now go thru each element a of A and each element b of B and get the sum=a+b
  • Every time that you see -sum ("minus" sum) in the hash table, increment the solution
At the end the complexity becomes 2*500*500 (500k) at the cost of 250k space. Code is below.


    public class Solution

    {
        public int FourSumCount(int[] A, int[] B, int[] C, int[] D)
        {
            Hashtable htCD = new Hashtable();
            for (int i = 0; i < C.Length; i++)
            {
                for (int j = 0; j < D.Length; j++)
                {
                    int sum = C[i] + D[j];
                    if (!htCD.ContainsKey(sum)) htCD.Add(sum, 0);
                    htCD[sum] = (int)htCD[sum] + 1;
                }
            }

            int result = 0;
            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < B.Length; j++)
                {
                    int sum = -(A[i] + B[j]);
                    if (htCD.ContainsKey(sum)) result += (int)htCD[sum];
                }
            }

            return result;
        }
    }

Comments

  1. TarasDecember 26, 2016 at 8:03 PM

    This seems to be the best solution! Although, back in the days, when I solved this problem using the exact same algorithm:
    class Solution {
    public:
    int fourSumCount(vector& A, vector& B, vector& C, vector& D) {
    unordered_map cache;
    for (int a : A) for (int b : B) cache[a+b] += 1;
    int count = 0;
    for (int c : C)
    for (int d : D) {
    auto it = cache.find(-(c+d));
    if (it != cache.cend()) count += it->second;
    }
    return count;
    }
    };

    my submission was better than 94% of other submissions with 609ms. Interestingly looks like there are solutions that take less than 400ms, which is impressive! My bet is that its due to a different hash implementation - I used a standard chaining hash map, so maybe cuckoo hashing would work better here.

    In fact an easy way to get a bit more performance is to provide an initial capacity to a map, so that it does not have to rehash as frequently. By changing unordered_map cache; to unordered_map cache(A.size()*B.size()); my solution ran in 516ms and beats 98.90% of other submissions and by changing it to unordered_map cache(A.size()*B.size()*4); to 492ms and 99.26% - not bad for such a tiny change :)

    Thanks for sharing this!

    ReplyDelete
    Replies
    1. Marcelo M De BarrosDecember 26, 2016 at 11:35 PM

      Good point about the rehash, something that is often overlooked but can definitely shed off double-digit milliseconds. The approach used to solve this problem in fact can be used to solve any problem involving N number of vectors (in our case here N happened to be 4 vectors).

      Delete
    2. TarasDecember 27, 2016 at 1:08 PM

      yep, it's very nice and general, indeed.

      Delete
  2. Turner GroupAugust 27, 2018 at 6:18 PM

    Working Java solution (cleaned the article's syntax to actually run):

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

    Map map = new HashMap<>();

    for (int i = 0; i < C.length; i++) {
    for (int j = 0; j < D.length; j++) {
    int sum = C[i] + D[j];
    if (!map.containsKey(sum)) {
    map.put(sum, 1);
    } else {
    map.put(sum, map.get(sum) + 1);
    }
    }
    }

    int result = 0;
    for (int i = 0; i < A.length; i++) {
    for (int j = 0; j < B.length; j++) {
    int sum = -( A[i] + B[j] );
    if (map.containsKey(sum)) {
    result += map.get(sum);
    }
    }
    }

    return result;
    }

    ReplyDelete
  3. raviMarch 4, 2019 at 7:54 AM

    There is another way ( i saw this in other submission) - without having a hash:
    Sort two of the arrays C and D. Iterate over A and B and find a target sum - from two values from the sorted C and D.

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

Prompt Engineering and LeetCode

-
Image
With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here:  The Knight’s Tour - LeetCode 2664. The Knight’s Tour Medium 11 0 Add to List Share Given two positive integers  m  and  n  which are the height and width of a  0-indexed  2D-array  board , a pair of positive integers  (r, c)  which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the  board  gets visited  exactly  once (the starting cell is considered visited and you  shouldn't  visit it again). Return  the array   board   in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight). Note that a  knight  can  move  from cell  (r1, c1)  to cell  (r2, c2)  if  0 <= r2 <= m - 1  and  0 <= c2 <= n - 1  and  min(abs(r1 - r2), abs(c1 - c2)) = 1  and  max(abs(r1 - r2), abs(c1 - c2)) = 2 .  
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more