Leetcode 727. Minimum Window Subsequence

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input: 
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.

Note:

• All the strings in the input will only contain lowercase letters.
• The length of S will be in the range [1, 20000].
• The length of T will be in the range [1, 100]

Analysis:
This is a two-sequence DP problem. We define dp[S.length() + 1][T.length() + 1], where dp[i][j] means the START POSITION of the minimum windows subsequnce for the first i charactgers from S and first j characters from T.

Code (Java):

class Solution {
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return "";
        }
        
        int[][] dp = new int[S.length() + 1][T.length() + 1];
        for (int i = 1; i <= T.length(); i++) {
            dp[0][i] = -1;
        }
        
        for (int i = 1; i <= S.length(); i++) {
            dp[i][0] = i;
        }
        
        int minLen = Integer.MAX_VALUE;
        int startPos = -1;
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                dp[i][j] = -1;
                
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            
            if (dp[i][T.length()] != -1) {
                int len = i - dp[i][T.length()];
                if (len < minLen) {
                    startPos = dp[i][T.length()];
                    minLen = len;
                }
            }
        }
        
        return startPos == -1? "" : S.substring(startPos, startPos + minLen);
    }
}

Leetcode 486. Predict the Winner

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.

Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

1. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

Solution 1: Backtracking + Memo:
Since each player wanna get the optimal results, we can maintain the score each player can get for choosing a number, and only return the best score. 

Code (Java):

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        
        return PredictTheWinnerHelper(nums, 0, nums.length - 1, dp) >= 0;
    }
    
    private int PredictTheWinnerHelper(int[] nums, int start, int end, int[][] dp) {
        if (start == end) {
            return nums[start];
        }
        
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        
        int max =  Math.max(nums[start] - PredictTheWinnerHelper(nums, start + 1, end, dp), 
                            nums[end] - PredictTheWinnerHelper(nums, start, end - 1, dp));
        
        
        dp[start][end] = max;
        
        return max;
    }
}

Solution 2: Top-Down DP:

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            dp[i][i] = nums[i];
        }
        
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], 
                                    nums[j] - dp[i][j - 1]);
            }
        }
        
        return dp[0][nums.length - 1] >= 0;
    }
    
}

Leetcode 467. Unique Substrings in Wraparound String

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string  s.

Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

Code (Java):

class Solution {
    public int findSubstringInWraproundString(String p) {
        if (p == null || p.length() == 0) {
            return 0;
        }
        
        int[] count = new int[26];
        int ans = 0;
        int maxLen = 1;
        count[p.charAt(0) - 'a'] = 1;
        
        for (int i = 1; i < p.length(); i++) {
            char curr = p.charAt(i);
            char prev = p.charAt(i - 1);
            
            if (Character.getNumericValue(curr) == Character.getNumericValue(prev) + 1 
                || (prev == 'z' && curr == 'a')) {
                maxLen++;
            } else {
                maxLen = 1;
            }
            
            count[curr - 'a'] = Math.max(count[curr - 'a'], maxLen);
        }
        
        for (int i = 0; i < count.length; i++) {
            ans += count[i];
        }
                
        return ans;
    }
}

Leetcode 446. Arithmetic Slices II - Subsequence

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

Analysis:
It's a DP problem. Since for each element A[i] when it's part of a arithmetic sequence, its difference can be different. For example, [2, 4, 6] and [2, 6, 10]. For number 2 and 6, they can be in different arithmetic sequences. 

So for each dp[i], we need to maintain a hashmap, the key is the diff, and value is the number of pairs with this diff. 

Then for each pair [i, j] in the array A, we check if we have seen the diff before. If yes, we add a pair and calculate the number of subsequences added in.

Code (Java):

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length < 3) {
            return 0;
        }
        
        Map<Integer, Integer>[] dp = (Map<Integer, Integer>[])new HashMap<?,?>[A.length];
        
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new HashMap<>();
        }
        
        int ans = 0;
        
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                long diff = (long)A[j] - (long)A[i];
                if (diff > Integer.MAX_VALUE || diff < Integer.MIN_VALUE) {
                    continue;
                }
                
                int delta = (int) diff;
                int vali = dp[i].getOrDefault(delta, 0);
                ans += vali;
                
                vali += 1;
                int valj = dp[j].getOrDefault(delta, 0);
                dp[j].put(delta, vali + valj);
            }
        }
        
        return ans;
    }
}

Leetcode 418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won't exceed 100.
5. Length of each word is greater than 0 and won't exceed 10.
6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Code (Java):

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String str = "";
        
        for (String word : sentence) {
            str += word + " ";
        }
        
        int len = str.length();
        
        int start = 0;
        for (int i = 0; i < rows; i++) {
            start += cols;
            
            if (str.charAt(start % len) == ' ') {
                start++;
                continue;
            }
            
            while ((start % len - 1 >= 0) && str.charAt(start % len - 1) != ' ') {
                start--;
            }
        }
        
        return start / len;
    }
}

Leetcode 410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Analysis:
A sequence DP problem. 
Define dp[n + 1][m + 1], where dp[i][k] means for the first i elements, divide into number of k subarrays, dp[i][k] is the minimum largeset sum among them. 

Code (Java):

class Solution {
    public int splitArray(int[] nums, int m) {
        int[] preSum = new int[nums.length + 1];
        
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        
        int[][] dp = new int[nums.length + 1][m + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        dp[0][0] = 0;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = 1; k <= m; k++) {
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], preSum[i] - preSum[j]));
                }
            }
        }
        
        return dp[nums.length][m];
    }
}

Leetcode 403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 231.
• The first stone's position is always 0.

Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

Analysis:
The problem is a classic sequence DP problem. The only trick is we need to define the dp function in a special way: 
dp[i] defines all the possible steps jumps to stone i. So each element of the dp[i] is a list, which stores all the steps from previous stone j. 

So for all previous stone[j], we check if we can reach from stone j to stone i. If yes, we store the steps between stone i and stone j. 

So why not just store the maximal distance between stone j and i. That is, if we can reach stone i in 10 steps, we must reach in 1 - 9 steps? That's wrong. It's because for each jump, we can only move dp[j] - 1, to dp[j] + 1 steps. 

Code (Java):

class Solution {
    public boolean canCross(int[] stones) {
        List<Integer>[] dp = (List<Integer>[]) new ArrayList[stones.length];
        for (int i = 0; i < stones.length; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[0].add(0);

        for (int i = 1; i < stones.length; i++) {
            for (int j = 0; j < i; j++) {
                for (Integer pos : dp[j]) {
                    if (stones[i] >= stones[j] + pos - 1 && 
                        stones[i] <= stones[j] + pos + 1) {
                        dp[i].add(stones[i] - stones[j]);
                        break;
                    }
                }
            }
        }
        
        return !dp[stones.length - 1].isEmpty();
    }
}

Leetcode 377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Analysis:
A classic DP problem. Define dp[k + 1], where dp[i] means for the target i, how many ways do we have. So the transist function would be for each target i, we iterate all the nums, and sum up its ways.

Code (Java):

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        for (int k = 1; k <= target; k++) {
            for (int i = 0; i < nums.length; i++) {
                if (k - nums[i] >= 0) {    
                    dp[k] += dp[k - nums[i]];
                }
            }
        }
        
        return dp[target];
    }
}

最初思路：
1.刚开始拿到这道题时，高兴！这不就是 K Sum 的简单版吗？只不过成员可以重复使用。要知道，重复使用成员是可以把DP降一维的！所以果断列出了一维DP (DP[target + 1]，存DP[num] 的组合数)；
2.然后循环的时候，还是老样子，先循环 nums 中的数，再循环 1 ~ target。但是这样写，结果错了！为什么呢？假设这个 nums 数组是排好序的 (我们也可以先排个序)，那么如果这样子循环的话，我们可以看到，我们得到的所有组合中，数全都是从小到大的！比如 nums = [1,2,3,4]，target = 4，那么我们最后求出的组合为 —— {1111, 112, 22, 13, 4}，是不是漏了很多？没错，乱序组合都没有包括在内！

改进思路：
1.改进思路的1同上面的1，略；
2.然后循环的时候，先循环 1～target，再循环 nums 中的数，反过来了！为什么呢？因为这样可以保证当 target = t 的时候，其包含的组合可以以任何一个 nums 中的数结尾！
3.假设还是上例，target = 1时，只有 1，DP[1] = 1；target = 2时，循环 [1,2,3,4]，得到 {11, 2}，DP[2] = 2；然后target = 3时，得到 DP[3] = 1->DP[2] + 2->DP[1] + 3->DP[0] = 4，which 分别是 {111, 21, 12, 3}，我们可以看出，此时包括了所有的组合了，很好！以此类推。。。

Leetcode 363. Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
             and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

Analysis:

The naive solution would be for each sub-matrix of the matrix, we calculate the sum. We compare with k and get a largest one. Since we can do a presum of the matrix before, so getting the sum of the sub-matrix is O(1) operation. The total time complexity of the solution would be O(m * n * m * n).

A better solution:

Think about the 1D problem: If given a array of nums and target k, how can we get the max sum of the subarray of which its sum is no greater than k? 

The solution is do a presum of the array first, and for each number sum[i], our goal is to find out a sum[j], where sum[i] - sum[j] <= k, In other words,

sum[j] >= sum[i] - k.

Since our goal is to find out the sum cloest to k, here sum[j] should be the smallest number in sum and it's greater or equal to sum[i] - k.

We can use a treeset to store the previous sum[i]. Treeset provides a convenient function called ceiling(val) which returns the smallest number greater or equal to val in the treeSet. So our target is to find out the ceiling of (sum[i] - k).

Overall, the time complexity of the 1D array is O(n * logn).

Then let's go back to the 2-D matrix problem. We can choose any two of the columns, c1 and c2. And do a presum between c1 and c2. Then the 2D problem can be reduced to 1D. 

The overall time complexity is O(n^2 * m * logm). If n >> m, we can do a row-order presum first, find out two rows r1 and r2, do a presum between r1 and r2.

Code (Java):

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] preSum = new int[m][n + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i][j - 1] + matrix[i][j - 1];
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for (int c1 = 1; c1 <= n; c1++) {
            for (int c2 = c1; c2 <= n; c2++) {
                int[] preSumRow = new int[m];
                for (int row = 0; row < m; row++) {
                    preSumRow[row] = preSum[row][c2] - preSum[row][c1 - 1];
                }
                
                ans = Math.max(ans, getMaxSubarrayHelper(preSumRow, k));
            }
        }
        
        return ans;
    }
    
    private int getMaxSubarrayHelper(int[] nums, int target) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        int ans = Integer.MIN_VALUE;
        int[] preSum = new int[nums.length + 1];
        
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        
        treeSet.add(0);
        for (int i = 1; i <= nums.length; i++) {
            Integer num = preSum[i] - target;
            Integer ceiling = treeSet.ceiling(num);
            
            if (ceiling != null) {
                ans = Math.max(ans, preSum[i] - ceiling);
            }
            
            treeSet.add(preSum[i]);
        }
        
        return ans;
    }
}

Leetcode 764. Largest Plus Sign

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

Example 1:

Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.

Example 2:

Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.

Example 3:

Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.

Note:

1. N will be an integer in the range [1, 500].
2. mines will have length at most 5000.
3. mines[i] will be length 2 and consist of integers in the range [0, N-1].
4. (Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)

Code (Java):

class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {
        Set<Integer> set = new HashSet<>();
        
        for (int[] pair : mines) {
            set.add(pair[0] * N + pair[1]);
        }
        
        int[][] dp = new int[N][N];
        
        int ans = 0;
        
        for (int i = 0; i < N; i++) {
            int count = 0;
            
            // left
            //
            for (int j = 0; j < N; j++) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = count;
            }
            
            // right
            //
            count = 0;
            for (int j = N - 1; j >= 0; j--) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = Math.min(dp[i][j], count);
            }
        }
        
        for (int j = 0; j < N; j++) {
            int count = 0;
            
            // up
            //
            for (int i = 0; i < N; i++) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = Math.min(dp[i][j], count);
            }
            
            count = 0;
            // down
            //
            for (int i = N - 1; i >= 0; i--) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = Math.min(dp[i][j], count);
                ans = Math.max(ans,dp[i][j]);
            }
        }
        
        return ans;
    }
}

Leetcode 750. Number Of Corner Rectangles

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

Example 1:

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

Example 2:

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.

Note:

1. The number of rows and columns of grid will each be in the range [1, 200].
2. Each grid[i][j] will be either 0 or 1.
3. The number of 1s in the grid will be at most 6000.

Solution 1:
One straight-forward solution is: we can iterate any two rows, say r1 and r2, and for every column, we check if grid[r1][c] == grid[r2][c]. IF yes, we increate the count by 1. Then the number of rentangles formed by these two rows are count * (count - 1) / 2.

The time complexity of the solution is O(m^2 * n). 

If the number of rows is significantly greater than number of columns, we can iterate the columns and check the rows for each of the two columns. Then the time complexity is O(n^2 * m).

Solution 2:
Solution 2 is similar to solution 1. The main difference is we use a hash map to save the positions of the two rows.

Code (Java):

class Solution {
    public int countCornerRectangles(int[][] grid) {
        if (grid == null || grid.length < 2 || grid[0] == null || grid[0].length < 2) {
            return 0;
        }
        
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        int m = grid.length;
        int n = grid[0].length;
        
        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r1][c] == 1 && grid[r2][c] == 1) {
                        int pos = r1* n + r2;
                        if (map.containsKey(pos)) {
                            int val = map.get(pos);
                            ans += val;
                            map.put(pos, val + 1);
                        } else {
                            map.put(pos, 1);
                        }
                    }
                }
            }
        }
        
        return ans;
    }
}

Leetcode 740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.

Each element nums[i] is an integer in the range [1, 10000].

Analysis:
There are several tricks in the problem.
 -- Since each element nums[i] is within the range of [1, 10000], we can use the bucket sort to sort the nums.
 -- For deleting each nums[i], we can delete all same numbers together. So when we do the bucket sort, we can sum up all the repeated numbers in the same bucket. 
 -- Then the problem is a classic backpack problem. 

Define take[10001] and skip[10001], where take[i] means for number i, we delete the number i, the max number of points. skip[i] means we don't delete it.

Then the transit function should be:
take[i] = skip[i - 1] +  values[i]
skip[i] = Math.max(take[i - 1], skip[i - 1]);


Code (Java):

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] dp = new int[100001];
        
        // step 1: bucket sort
        //
        for (int num : nums) {
            dp[num] += num;
        }
        
        int prevTake = 0;
        int prevSkip = 0;
        
        for (int i = 1; i <= 10000; i++) {
            int currTake = prevSkip + dp[i];
            int currSkip = Math.max(prevSkip, prevTake);
            
            prevTake = currTake;
            prevSkip = currSkip;
        }
        
        return Math.max(prevTake, prevSkip);
    }
}

Leetcode 718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

Code (Java):

class Solution {
    public int findLength(int[] A, int[] B) {
        int[][] dp = new int[A.length + 1][B.length + 1];
        
        int maxLen = 0;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        
        return maxLen;
    }
}