LintCode - Submatrix Sum


http://cherylintcode.blogspot.com/2015/07/submatrix-sum.html
Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.
Example

Given matrix
[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]
return [(1,1), (2,2)]
http://blog.csdn.net/gqk289/article/details/69809685
这道题和求数组中哪些元素和为0的解决方法一样,只是数组中求的是前i个元素和前j个元素和相等,则i-j元素和为0,而这里只是变成2维的而已。
sum[i][j]表示matrix[0][0]到matrix[i-1][j-1]所有元素的和。
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + matrix[i][j] - sum[i - 1][j - 1]
然后用一条竖线k扫描,diff表示0 ~ k && i ~ j的子矩阵的和,如果与前序某个子矩阵的和相等,则找到对应和为零的子矩阵
注意map初始化的位置
  1.     public int[][] submatrixSum(int[][] matrix) {  
  2.         int[][] res = new int[2][2];  
  3.         if (matrix == null || matrix.length == 0) {  
  4.             return res;  
  5.         }  
  6.         int row = matrix.length;  
  7.         int col = matrix[0].length;  
  8.         int[][] sum = new int[row + 1][col + 1];  
  9.         for (int i = 0; i < row; i++) {  
  10.             for (int j = 0; j < col; j++) {  
  11.                 sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] + matrix[i][j] - sum[i][j];  
  12.             }  
  13.         }  
  14.         for (int i = 0; i < row; i++) {  
  15.             for (int j = i + 1; j <= row; j++) {  
  16.                 HashMap<Integer, Integer> map = new HashMap();  
  17.                 for (int k = 0; k <= col; k++) {  
  18.                     int diff = sum[j][k] - sum[i][k];  
  19.                     if (map.containsKey(diff)) {  
  20.                         res[0][0] = i;  
  21.                         res[0][1] = map.get(diff);  
  22.                         res[1][0] = j - 1;  
  23.                         res[1][1] = k - 1;  
  24.                         return res;  
  25.                     } else {  
  26.                         map.put(diff, k);  
  27.                     }  
  28.                 }  
  29.             }  
  30.         }  
  31.         return res;  
  32.     }  
https://segmentfault.com/a/1190000004878083
先对矩阵matrix的每个点到左顶点之间的子矩阵求和,存在新矩阵sum上。注意,sum[i+1][j+1]代表的是matrix[0][0]matrix[i][j]的子矩阵求和。如下所示:
Given matrix[m][n]
------------------
[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]
Get sum[m+1][n+1]
-----------------
0  0  0  0
0  1  6  13
0  4  16 15
0  8  12 20
然后,我们进行这样的操作,从0开始,确定两行i1i2,再将第k列的sum[i1][k]sum[i2][k]相减,就得到matrix[i1][0]matrix[i2][k-1]的子矩阵(i2-i1行,k列)求和diff,存入map。还是在这两行,假设计算到第j列,得到了相等的和diff。说明从i1到i2行,从k到j列的子矩阵求和为0,即相当于两个平行放置的矩形,若左边的值为diff,左边与右边之和也是diff,那么右边的值一定为0。下面是map中存放操作的例子:
diff-j chart
------------
diff    j

1       1       i1 = 0, i2 = 1
6       2
13      3
4       1       i1 = 0, i2 = 2
16      2
15      3
8       1       i1 = 0, i2 = 3
12      2
20      3
3       1       i1 = 1, i2 = 2
10      2
2       3
------------------------------
(above res has no same pair in same region)
7       1       i1 = 1, i2 = 3
6       2       
7       3       diff-j pair exists in map

res[0][0] = i1 = 1, res[0][1] = map.get(diff) = 1,
res[1][0] = i2 - 1 = 3 - 1 = 2, res[1][1] = j = 2,

so res = [(1, 1), (2, 2)]
http://techinpad.blogspot.com/2015/06/lintcode-submatrix-sum.html
If the matrix is Nx1, we can solve it easily like sum of contiguous subsequense. If it's Nx2, we just need to repeat the same process 3 times --  the first column, the second column and sum of the two columns as an Nx1 array. That's applicable to any cases.

    public int[][] submatrixSum(int[][] matrix) {
        int[][] result = new int[2][2];
        int M = matrix.length;
        if (M == 0) return result;
        int N = matrix[0].length;
        if (N == 0) return result;
        // pre-compute: sum[i][j] = sum of submatrix [(0, 0), (i, j)]
        int[][] sum = new int[M+1][N+1];
        for (int j=0; j<=N; ++j) sum[0][j] = 0;
        for (int i=1; i<=M; ++i) sum[i][0] = 0;
        for (int i=0; i<M; ++i) {
            for (int j=0; j<N; ++j)
                sum[i+1][j+1] = matrix[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j];
        }
        for (int l=0; l<M; ++l) {
            for (int h=l+1; h<=M; ++h) {
                Map<Integer, Integer> map = new HashMap<Integer, Integer>();
                for (int j=0; j<=N; ++j) {
                    int diff = sum[h][j] - sum[l][j];
                    if (map.containsKey(diff)) {
                        int k = map.get(diff);
                        result[0][0] = l;   result[0][1] = k;
                        result[1][0] = h-1; result[1][1] = j-1;
                        return result;
                    } else {
                        map.put(diff, j);
                    }
                }
            }
        }
        return result;
    }

    public int[][] submatrixSum(int[][] matrix) {
        // Write your code here
        int m = matrix.length, n = matrix[0].length;
       
        int[][] res = new int[2][2];
       
        for(int i = 0; i < n; i++){
            int[] sum = new int[m];
            for(int j = i; j < n; j++){
               
                for(int k = 0; k < m; k++){
                    sum[k] += matrix[k][j];
                }
               
                HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
                int lastSum = 0;
                map.put(0, -1); // important
                for(int l = 0; l < m; l++){
                    lastSum += sum[l];
                    if(map.containsKey(lastSum)){
                       
                        res = new int[][] {{map.get(lastSum)+1, i}, {l, j}};
                        return res;
                    }
                    map.put(lastSum, l);
                }
            }
        }
        return res;
    }

http://sidbai.github.io/2015/06/11/Submatrix-Sum/
http://www.1point3acres.com/bbs/thread-146423-1-1.html
Given an array, find whether it exist an subarray that sum of subarray is equal to given number
简单的说就是给一个array,和一个数字,问存在一个subarray,他的和等于那个数字。注意,subarray的意思是一个连续的元素的subarray from array。
一开始给了N^2的暴力算法,之后给了O(N)的算法,解法是用一个新的数组保存从0到当前元素的和,然后再用hash表保存下,再搜索一次即可。

上面那题的follow up,不过array变成了matrix,找的也是submatrix

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