Please use more memory, it is OK!

-
Computer scientists and engineers: use more memory. It is fine.

As a matter of fact, if you want to collaborate to ensure that Moore's Law (and the equivalent memory variant) remains true, then you actually have a duty to keep pushing memory (and CPU/GPU) to the next level! Memory these days is cheap - go on, and cache whatever you want.

Search uses an absurd amount of caching and pre-computed data in memory. It is necessary. When you want to give the information back to the user in a blink of an eye, you have no choice but to do all the very heavy-lifting processing in the background, and "pre-cook" in memory a lot of what you want to serve the user. This is no cheating. It is technology.

In-memory caching makes everyone's life easier - and faster. Here is a problem that exemplifies this concept: https://leetcode.com/problems/range-sum-query-2d-immutable/

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.
How to solve it? Well, we'll pre-compute content - and cache!

  1. Start by having a separate matrix
  2. This matrix will contain the cumulative sum of all the elements from (0,0) to (i,j)
  3. You can compute (2) in linear time
  4. Now, when positions (x1,y1) and (x2,y2) are given, you can compute the result by looking up this auxiliary matrix
  5. Basically by inspection in the below picture, you will notice that to find the area in red:
    1. Sum(red) = Sum(red full) - Sum(orange) - Sum(green) + Sum(blue)
And there you have it. How fast does it work? Fast. Code is below, cheers, ACC.




    public class NumMatrix
    {
        int[][] sumMatrix = null;
        public NumMatrix(int[][] matrix)
        {
            this.sumMatrix = (int[][])matrix.Clone();

            for (int r = 0; r < matrix.GetLength(0); r++)
            {
                for (int c = 0; c < matrix[0].GetLength(0); c++)
                {
                    sumMatrix[r][c] = matrix[r][c];
                    if (r - 1 >= 0) sumMatrix[r][c] += sumMatrix[r - 1][c];
                    if (c - 1 >= 0) sumMatrix[r][c] += sumMatrix[r][c - 1];
                    if (r - 1 >= 0 && c - 1 >= 0) sumMatrix[r][c] -= sumMatrix[r - 1][c - 1];
                }
            }
        }

        public int SumRegion(int row1, int col1, int row2, int col2)
        {
            int sum = 0;

            sum = sumMatrix[row2][col2];
            if (row1 - 1 >= 0) sum -= sumMatrix[row1 - 1][col2];
            if (col1 - 1 >= 0) sum -= sumMatrix[row2][col1 - 1];
            if (row1 - 1 >= 0 && col1 - 1 >= 0) sum += sumMatrix[row1 - 1][col1 - 1];
            return sum;
        }
    }

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more