LeetCode 923 - 3Sum With Multiplicity


https://leetcode.com/problems/3sum-with-multiplicity/
Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.
As the answer can be very large, return it modulo 10^9 + 7.

Example 1:
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
Example 2:
Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Note:
  1. 3 <= A.length <= 3000
  2. 0 <= A[i] <= 100
  3. 0 <= target <= 300

X. Map store pair sum
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution
    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        int res = 0;
        int mod = 1000000007;
        for (int i = 0; i < A.length; i++) {
            res = (res + map.getOrDefault(target - A[i], 0)) % mod;
            
            for (int j = 0; j < i; j++) {
                int temp = A[i] + A[j];
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }
        return res;
    }




public int threeSumMulti(int[] A, int target) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int n = A.length;
        long result = 0;
        
        for(int i = 0; i + 1 < n; i++){
            for(int j = i + 1; j < n; j++){
                if(count.containsKey(target - A[i] - A[j])){
                    result += 1L * count.get(target - A[i] - A[j]); 
                    //System.out.println(result);
                }
            }
            count.put(A[i], count.getOrDefault(A[i], 0) + 1);
        }
        
       // System.out.println(result);
        return (int) (result%(1000000000 + 7));
    }

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)
    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Long> map = new HashMap<>();
        for (int a : A) {
            map.put(a, map.getOrDefault(a, 0l) + 1);
        }
        long result = 0;
        int M = (int)1e9 + 7;
        for (int a : map.keySet()) {
            for (int b : map.keySet()) {
                if (b < a || a == b && map.get(a) == 1) {
                    continue;
                }
                int c = target - a - b;
                if (c < b || !map.containsKey(c)) {
                    continue;
                }
                if (a == b && b == c) {
                    if (map.get(a) == 2) {
                        continue;
                    }
                    result += nCk(map.get(a), 3);
                } else if (a == b) {
                    result += nCk(map.get(a), 2) * map.get(c);
                } else if (b == c) {
                    if (map.get(b) == 1) {
                        continue;
                    }
                    result += nCk(map.get(b), 2) * map.get(a);
                } else {
                    result += (map.get(a) * map.get(b) * map.get(c));
                }
                result %= M;
            }
        }
        return (int)result;
    }
    private long nCk(long n, int k) {
        if (k == 3) {
            return (n * (n - 1) * (n - 2)) / 6;
        } else {
            return n * (n - 1) / 2;
        }
    }

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)
Count the occurrence of each number.
using hashmap or array up to you.
Loop i on all numbers,
loop j on all numbers,
check if k = target - i - j is valid.
Add the number of this combination to result.
3 cases covers all possible combination:
  1. i == j == k
  2. i == j != k
  3. i < k && j < k
Time Complexity:
3 <= A.length <= 3000, so N = 3000
But 0 <= A[i] <= 100
So my solution is O(N + 101 * 101)


    public int threeSumMulti(int[] A, int target) {
        long[] c = new long[101];
        for (int a : A) c[a]++;
        long res = 0;
        for (int i = 0; i <= 100; i++)
            for (int j = i; j <= 100; j++) {
                int k = target - i - j;
                if (k > 100 || k < 0) continue;
                if (i == j && j == k)
                    res += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
                else if (i == j && j != k)
                    res += c[i] * (c[i] - 1) / 2 * c[k];
                else if (j < k)
                    res += c[i] * c[j] * c[k];
            }
        return (int)(res % (1e9 + 7));
    }

X. 3 pointers
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.

while (j + l < k && A[j + l] == A[j]) { ++l; } 
while (j < k - r && A[k - r] == A[k]) { ++r; }
solving the duplicated cases is quite impressive, that is the solution I am looking for

    private static final int  m = 1_000_000_007;
    public int threeSumMulti(int[] A, int target) {
        Arrays.sort(A);
        int res = 0;
        for (int i = 0; i < A.length - 2; ++i) {
            int j = i + 1;
            int k = A.length - 1;
            while (j < k) {
                if (A[j] + A[k] < target - A[i]) { ++j; }
                else if (A[j] + A[k] > target - A[i]) { --k; }
                else {
                    if (A[j] == A[k]) {
                        // If A[j...k] are all equal, then there are C(k - j + 1, 2) 
                        // combinations that meet the requirement.
                        res = (res + (k - j + 1) * (k - j) / 2) % m;
                        break;
                    }
                    int l = 1, r = 1;
                    while (j + l < k && A[j + l] == A[j]) { ++l; } // l: number of elements equal to A[j].
                    while (j < k - r && A[k - r] == A[k]) { ++r; } // r: number of elements equal to A[k].
                    res = (res + l * r) % m; // found l * r cases that meet the requirement.
                    j += l; // forward j by l steps.
                    k -= r; // backward k by r steps.
                }
            }
        }
        return res;
    }


X. DP
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)

dp[i][j][k] represents number of combinations using k numbers within A[0] ... A[i] with the sum of j.
Then dp[n][target][3] is the result. O(n * target)

    public int threeSumMulti(int[] A, int target) {
        int n = A.length, M = (int)1e9 + 7;
        int[][][] dp = new int[n + 1][target + 1][4];
        for (int i = 0; i <= n; i++) {
            dp[i][0][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                for (int k = 1; k <= 3; k++) {
                    dp[i + 1][j][k] = dp[i][j][k];
                    dp[i + 1][j][k] %= M;
                    if (j >= A[i]) {
                        dp[i + 1][j][k] += dp[i][j - A[i]][k - 1];
                        dp[i + 1][j][k] %= M;
                    }
                }
            }
        }
        return dp[n][target][3];
    }

X. https://zxi.mytechroad.com/blog/math/leetcode-923-3sum-with-multiplicity/
Time complexity: O(n + |target|^2)
Space complexity: O(|target|)

# step1 统计数组中每个元素出现的次数
一个元素I出现的次数记为count(I)

# step2 分类
记：I=A[i], J=A[j], K=A[k], C(count(I),3) 表示从count(I)个数中取3个的组合数
I=J=K     C(count(I), 3)
I=J!=K    C(count(I), 2) * count(K)
I!=J=K    count(I) * C(count(K), 2)
I!=J!=K   count(I) * count(J) * count(K)

# 复杂度
Time complexity: O(n + target^2)
Space complexity: O(100)
下面是参考视频中的截图，其中的i,j,k是数而不是index

public int threeSumMulti(int[] A, int target) {
    int MOD = 1_000_000_007; // 因为最大数为10^9+7

    // 计算数组中不同元素出现的个数   因为 0 <= A[i] <=100
    long[] c = new long[101]; // 定义成long，在计算中不用转换
    for (int a : A) c[a]++;

    long ans = 0;
    for (int i = 0; i <= target; i++) {
        for (int j = i; j <= target; j++) {
            int k = target - i - j;
            if (k < 0 || k >= c.length || k < j) continue;
            if (c[i] == 0 || c[j] == 0 || c[k] == 0) continue;
            if (i ==j && j == k) {
                ans += (c[i] - 2) * (c[i] - 1) * c[i] / 6;
            } else if (i ==j && j != k) {
                ans += c[i] * (c[i] - 1) / 2 * c[k];
            } else if (i != j && j == k) {
                ans += c[i] * (c[j] - 1) * c[j] / 2;
            } else {
                ans += c[i] * c[j] * c[k];
            }
            ans %= MOD;
        }
    }
    return (int)ans;
}



  public int threeSumMulti(int[] A, int target) {
    int MOD = 1_000_000_007;
    long ans = 0;
    Arrays.sort(A);

    for (int i = 0; i < A.length; ++i) {
      // We'll try to find the number of i < j < k
      // with A[j] + A[k] == T, where T = target - A[i].

      // The below is a "two sum with multiplicity".
      int T = target - A[i];
      int j = i + 1, k = A.length - 1;

      while (j < k) {
        // These steps proceed as in a typical two-sum.
        if (A[j] + A[k] < T)
          j++;
        else if (A[j] + A[k] > T)
          k--;
        else if (A[j] != A[k]) { // We have A[j] + A[k] == T.
          // Let's count "left": the number of A[j] == A[j+1] == A[j+2] == ...
          // And similarly for "right".
          int left = 1, right = 1;
          while (j + 1 < k && A[j] == A[j + 1]) {
            left++;
            j++;
          }
          while (k - 1 > j && A[k] == A[k - 1]) {
            right++;
            k--;
          }

          ans += left * right;
          ans %= MOD;
          j++;
          k--;
        } else {
          // M = k - j + 1
          // We contributed M * (M-1) / 2 pairs.
          ans += (k - j + 1) * (k - j) / 2;
          ans %= MOD;
          break;
        }
      }
    }

    return (int) ans;

  }

  public int threeSumMulti(int[] A, int target) {
    int MOD = 1_000_000_007;
    long[] count = new long[101];
    for (int x : A)
      count[x]++;

    long ans = 0;

    // All different
    for (int x = 0; x <= 100; ++x)
      for (int y = x + 1; y <= 100; ++y) {
        int z = target - x - y;
        if (y < z && z <= 100) {
          ans += count[x] * count[y] * count[z];
          ans %= MOD;
        }
      }

    // x == y != z
    for (int x = 0; x <= 100; ++x) {
      int z = target - 2 * x;
      if (x < z && z <= 100) {
        ans += count[x] * (count[x] - 1) / 2 * count[z];
        ans %= MOD;
      }
    }

    // x != y == z
    for (int x = 0; x <= 100; ++x) {
      if (target % 2 == x % 2) {
        int y = (target - x) / 2;
        if (x < y && y <= 100) {
          ans += count[x] * count[y] * (count[y] - 1) / 2;
          ans %= MOD;
        }
      }
    }

    // x == y == z
    if (target % 3 == 0) {
      int x = target / 3;
      if (0 <= x && x <= 100) {
        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
        ans %= MOD;
      }
    }

    return (int) ans;

  }

  public int threeSumMulti(int[] A, int target) {
    int MOD = 1_000_000_007;

    // Initializing as long saves us the trouble of
    // managing count[x] * count[y] * count[z] overflowing later.
    long[] count = new long[101];
    int uniq = 0;
    for (int x : A) {
      count[x]++;
      if (count[x] == 1)
        uniq++;
    }

    int[] keys = new int[uniq];
    int t = 0;
    for (int i = 0; i <= 100; ++i)
      if (count[i] > 0)
        keys[t++] = i;

    long ans = 0;
    // Now, let's do a 3sum on "keys", for i <= j <= k.
    // We will use count to add the correct contribution to ans.

    for (int i = 0; i < keys.length; ++i) {
      int x = keys[i];
      int T = target - x;
      int j = i, k = keys.length - 1;
      while (j <= k) {
        int y = keys[j], z = keys[k];
        if (y + z < T) {
          j++;
        } else if (y + z > T) {
          k--;
        } else { // # x+y+z == T, now calc the size of the contribution
          if (i < j && j < k) {
            ans += count[x] * count[y] * count[z];
          } else if (i == j && j < k) {
            ans += count[x] * (count[x] - 1) / 2 * count[z];
          } else if (i < j && j == k) {
            ans += count[x] * count[y] * (count[y] - 1) / 2;
          } else { // i == j == k
            ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
          }

          ans %= MOD;
          j++;
          k--;
        }
      }
    }

    return (int) ans;

  }

at
Labels: , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts