# Shortest Word Distance I, II & III

Word Distance I – Only called once

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“coding”`, word2 = `“practice”`, return 3.
Given word1 = `"makes"`, word2 = `"coding"`, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: One pass. O(n), Every time find an occurrence of word1 or word2, compare the distance of p1 and p2.

```public int shortestDistance(String[] words, String word1, String word2) {
int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1))
p1 = i;

if (words[i].equals(word2))
p2 = i;

if (p1 != -1 && p2 != -1)
min = Math.min(min, Math.abs(p1 - p2));
}

return min;
}```

Shortest Word Distance II – API, will be called multiple times

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“coding”`, word2 = `“practice”`, return 3.
Given word1 = `"makes"`, word2 = `"coding"`, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: First preprocess the word to dict, which is a <word, list of index>map.

Then every time just get the word only check two list of indexes.

```public class WordDistance {
Map<String, List<Integer>> dict;
public WordDistance(String[] words) {
dict = new HashMap<>();
for(int i=0;i<words.length;i++){
if(dict.containsKey(words[i])){
}else{
List<Integer> indexes = new ArrayList<>();
dict.put(words[i], indexes);
}
}
}

public int shortest(String word1, String word2) {
if(dict==null||!dict.containsKey(word1)||!dict.containsKey(word2)){
return 0;
}
int res = Integer.MAX_VALUE;
List<Integer> indexes1 = dict.get(word1);
List<Integer> indexes2 = dict.get(word2);
int index1 = 0;
int index2 = 0;
while(index1<indexes1.size()&&index2<indexes2.size()){
res = Math.min(res, Math.abs(indexes1.get(index1)-indexes2.get(index2)));
if(indexes1.get(index1)<indexes2.get(index2)){
index1++;
}else{
index2++;
}
}
return res;

}
}```

Shortest Word Distance III – word1 could be the same as word2

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“makes”`, word2 = `“coding”`, return 1.
Given word1 = `"makes"`, word2 = `"makes"`, return 3.

Note:
You may assume word1 and word2 are both in the list.

Solution: if word1==word2==words[], then p1=p2=i, and every time we update p1, we check the distance between p1 and p2.

```public int shortestWordDistance(String[] words, String word1, String word2) {
int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
p1 = i;
if (word1.equals(word2) && p1 != -1 && p2 != -1) {
min = Math.min(min, Math.abs(p1 - p2));
}
}

if (words[i].equals(word2)) {
p2 = i;
}

if (!word1.equals(word2) && p1 != -1 && p2 != -1) {
min = Math.min(min, Math.abs(p1 - p2));
}
}

return min;
}```
Share

# Longest Palindromic Substring

#### Longest Palindromic Substring

Given a string `S`, find the longest palindromic substring in `S`. You may assume that the maximum length of `S` is 1000, and there exists one unique longest palindromic substring.

Example

Given the string = `"abcdzdcab"`, return `"cdzdc"`.

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Solution1. DP O(n^2)

P[i,j] = 字符串区间[i,j]是否为palindrome.

S=    a  b  c  c  b
Index = 0  1  2  3  4

P[0,0] =1  //each char is a palindrome
P[0,1] =S[0] == S[1]    , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3],  P[3,3]=1
………………….

P[i,j] = 1  if i ==j
=  S[i] ==S[j]   if j = i+1
=  S[i] == S[j] && P[i+1][j-1]  if j>i+1

```public String longestPalindrome(String s) {
if (s == null) {
return "";
}
String res = "";
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (i - j <= 2) {
dp[j][i] = s.charAt(i) == s.charAt(j);
} else {
dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
}
if (dp[j][i]) {
if (i - j + 1 > res.length()) {
res = s.substring(j, i + 1);
}
}
}
}
return res;
}```

Solution2: Check both aba and abba 2 cases. O(n^2)

```public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
String result = "";

//1. if it is like 'aba'
for (int i = 0; i < s.length(); i++) {
int count = 0;
while (i - count >= 0 && i + count < s.length() && s.charAt(i - count) == s.charAt(i + count)) {
count++;
}
String palindrome = s.substring(i - count + 1, i + count);
if (palindrome.length() > result.length()) {
result = palindrome;
}
}

//2. if it is like 'abba', the pivot would be the interval between i and i+1
for (int i = 0; i < s.length() - 1; i++) {
int count = 1;
while (i - count + 1 >= 0 && i + count < s.length() && s.charAt(i - count + 1) == s.charAt(i + count)) {
count++;
}
if (count > 1) {
String palindrome = s.substring(i - count + 2, i + count);
if (palindrome.length() > result.length()) {
result = palindrome;
}
}
}

return result;
}```

# Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example `[4,4,6,1,1,4,2,5]`, return `6`.

Note

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法

`max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])`

`Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);`

```public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int length = prices.length;
int[] maxProfitEndedAt = new int[length];
int[] maxProfitStartedFrom = new int[length];

//get the max profit from 0 to i with one transaction
maxProfitEndedAt[0] = 0;
for (int i = 1; i < length; i++) {
maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
}
}
//get the max profit form i to length-1 with one transaction
maxProfitStartedFrom[length - 1] = 0;
int sellDay = length - 1;
for (int i = length - 2; i >= 0; i--) {
maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]);
if (prices[i] > prices[sellDay]) {
sellDay = i;
}
}
//to have two transactions
//pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
int maxWithTwoTransaction = 0;
for (int i = 0; i < length - 2; i++) {
maxWithTwoTransaction = Math.max(maxWithTwoTransaction,
maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]);
}
return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
}```

# Maximum Product Subarray

#### Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array `[2,3,-2,4]`, the contiguous subarray `[2,3]` has the largest product = `6`.

Solution: One Pass O(n) time.

So for each index i, max(i) = the maximum product ending at i, so we have

max(i) = max(max(i-1)*nums[i], nums[i]) //nums[i]>=0

since you can either append from the previous one, or just start a new contiguous subarray.

Be careful on negative nums, if nums[i] < 0, the equation now becomes:

max(i) = max(min(i-1)*nums[i], nums[i]) //nums[i]<0

```public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxProduct = Integer.MIN_VALUE;
int preMax = 1;
int preMin = 1;
for (int i = 0; i < nums.length; i++) {
int max, min;
if (nums[i] >= 0) {
max = Math.max(preMax * nums[i], nums[i]);
min = Math.min(preMin * nums[i], nums[i]);
} else {
max = Math.max(preMin * nums[i], nums[i]);
min = Math.min(preMax * nums[i], nums[i]);
}
maxProduct = Math.max(maxProduct, max);
preMax = max;
preMin = min;
}
return maxProduct;
}```

# Maximum Subarray I & II & III

Maximum Subarray I

Given an array of integers, find a contiguous subarray which has the largest sum.

Example

For example, given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note

The subarray should contain at least one number

Challenge

Can you do it in time complexity O(n)?

Solution: O(n) time O(1) space. one pass. Prefix Sum

```public int maxSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int maxSum = Integer.MIN_VALUE;
int sum = 0;
int minSum = 0;
for (Integer num : nums) {
sum += num;
maxSum = Math.max(maxSum, sum - minSum);
minSum = Math.min(minSum, sum);
}
return maxSum;
}```

# Minimum Subarray

Minimum Subarray

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

Example

For [1, -1, -2, 1], return -3

Note

The subarray should contain at least one integer.

Solution: O(n) time O(1) space. one pass. Prefix Sum

```public int minSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int minSum = Integer.MAX_VALUE;
int sum = 0;
int maxSum = 0;
for (Integer num : nums) {
sum += num;
minSum = Math.min(minSum, sum - maxSum);
maxSum = Math.max(maxSum, sum);
}
return minSum;
}```

# Largest Rectangle in Histogram

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

The largest rectangle is shown in the shaded area, which has area = `10` unit.

Example

Given height = `[2,1,5,6,2,3]`,
return `10`.

Solution: max(the area of rectangle which height[i] is the shortest bar)

leftBound[i]: index of the first element less than height[i] starting from the left +1

rightBound[i]: index of the first element less than height[i] starting from the right -1

result = max(height[i]*(rightBound[i]-leftBound[i]))

O(n) time.

Solution 1. Straightforward Version

```public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int[] leftBound = new int[height.length];
int[] rightBound = new int[height.length];
Stack<Integer> minStack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
leftBound[i] = 0;
} else {
leftBound[i] = minStack.peek() + 1;
}
minStack.push(i);
}
minStack = new Stack<>();
for (int i = height.length - 1; i >= 0; i--) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
rightBound[i] = height.length - 1;
} else {
rightBound[i] = minStack.peek() - 1;
}
minStack.push(i);
}
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
int area = height[i] * (rightBound[i] - leftBound[i] + 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}```

Solution 2. Fancy Version, One pass

```public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> minStack = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= height.length; i++) {
int curr = (i == height.length) ? -1 : height[i];
while (!minStack.isEmpty() && curr <= height[minStack.peek()]) {
int tmp = minStack.pop();
int left = minStack.isEmpty() ? 0 : minStack.peek() + 1;
int area = (i - left) * height[tmp];
maxArea = Math.max(area, maxArea);
}
minStack.push(i);
}
return maxArea;
}```

# N-Queens I &&II

N-Queens I

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example

There exist two distinct solutions to the 4-queens puzzle:

[

[“.Q..”, // Solution 1

“…Q”,

“Q…”,

“..Q.”],

[“..Q.”, // Solution 2

“Q…”,

“…Q”,

“.Q..”]

]

Solution1: Recursion DFS, Permutation模板，判断条件换一下

```ArrayList<ArrayList<String>> solveNQueens(int n) {
ArrayList<ArrayList<String>> result = new ArrayList<>();
if (n <= 0) {
return result;
}
int[][] chessBoard = new int[n][n];
solveNQueensHelper(chessBoard, 0, result);
return result;
}

//DFS
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<ArrayList<String>> result) {
if (row == chessBoard.length) {
return;
}
for (int col = 0; col < chessBoard[row].length; col++) {
if (isValid(chessBoard, row, col)) {
chessBoard[row][col] = 1;
solveNQueensHelper(chessBoard, row + 1, result);
chessBoard[row][col] = 0;
}
}
}

public boolean isValid(int[][] chessBoard, int row, int col) {
for (int i = 1; i <= row; i++) {
if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
(col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
chessBoard[row - i][col] == 1) {
return false;
}
}
return true;
}

public ArrayList<String> toStringList(int[][] chessBoard) {
ArrayList<String> result = new ArrayList<>();
for (int i = 0; i < chessBoard.length; i++) {
StringBuilder row = new StringBuilder();
for (int j = 0; j < chessBoard[i].length; j++) {
if (chessBoard[i][j] == 0) {
row.append('.');
} else {
row.append('Q');
}
}
}
return result;
}```

Solution 2. Non-Recursive

N-Queens II

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution 1. Recursive. DFS

Solution 1. Recursive

```public int totalNQueens(int n) {
ArrayList<Integer> result = new ArrayList<>();
if (n <= 0) {
return 0;
}
int[][] chessBoard = new int[n][n];
solveNQueensHelper(chessBoard, 0, result);
return result.size();
}

public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<Integer> result) {
if (row == chessBoard.length) {
return;
}
for (int col = 0; col < chessBoard[row].length; col++) {
if (isValid(chessBoard, row, col)) {
chessBoard[row][col] = 1;
solveNQueensHelper(chessBoard, row + 1, result);
chessBoard[row][col] = 0;
}
}
}

public boolean isValid(int[][] chessBoard, int row, int col) {
for (int i = 1; i <= row; i++) {
if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
(col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
chessBoard[row - i][col] == 1) {
return false;
}
}
return true;
}```

Solution 2. Non-Recursive

# Leetcode: Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?1. O(m+n) space solutionAnalysis:
To achieve O(m+n) space, you need two array to store information while traversal the matrix for the first time checking if it is zero or not. You can also combine two arrays into one, but still cost O(m+n) space. So I just use two to store row and column information.
```public class Solution {
public void setZeroes(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return;
}
boolean[] zeroRows = new boolean[matrix.length];
boolean[] zeroCols = new boolean[matrix[0].length];
//traversal the entire matrix to check if it is zero or not
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
zeroRows[i] = true;
zeroCols[j] = true;
}
}
}
//now set matrix zero based on the two boolean arrays
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (zeroRows[i] || zeroCols[j]) {
matrix[i][j] = 0;
}
}
}
}
}```

2. *Optimal* O(1) space solution

Analysis:
To save space, we can just make use of the space inside the matrix. Which means, we use the first row and first column to store the information.
In the first traversal, we set the corresponding cell on the first row or first column to 0 if there is any cell which is zero in this row or column.
In the second traversal, we set the matrix to zeros based on the first row and first column.

``` public void setZeroes(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return;
}
boolean firstRowHasZero = false;
boolean firstColHasZero = false;
//traversal the entire matrix to check if it is zero or not
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
if (i == 0) {
firstRowHasZero = true;
}
if (j == 0) {
firstColHasZero = true;
}
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
//now set matrix zero based on first row and first column
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[i].length; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
//deal with the first column
if (firstColHasZero) {
for (int i = 1; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
//deal with the first row
if (firstRowHasZero) {
for (int i = 1; i < matrix[0].length; i++) {
matrix[0][i] = 0;
}
}
}```

Note: The tricky part of this algorithm is, if without those two boolean variables to keep track of if there is any zero in the first row or first column , when matrix[0][0]==0, we have no idea if the first row contains zero, or it is the first column contains zero, or both. also, we should deal with the rest part first based on the first row and first column and then deal with the first row and first column based on the two boolean values.

# Leetcode: Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

1. Recursive Solution

``` public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int[][] resultMap = new int[grid.length][grid[0].length];
return minPathSum(grid, resultMap, grid.length-1, grid[0].length-1);
}

public int minPathSum(int[][] grid, int[][] resultMap, int row, int col) {
if (row < 0 || col < 0) {
return Integer.MAX_VALUE;
}
if (row == 0 && col == 0) {
return grid[0][0];
}
if (resultMap[row][col] == 0) {
resultMap[row][col] = grid[row][col] + Math.min(minPathSum(grid, resultMap, row - 1, col), minPathSum(grid, resultMap, row, col - 1));
}
return resultMap[row][col];
}```

Note:

This is a very typical dp problem. where dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] ); To prevent same cell being visited and calculated multiple times, we have a resultMap 2d array to store the result. We also need to check the edge carefully to ensure the index is not out of bounds of the given array.

2. Iterative Solution (O(m*n) space)

```public class Solution {
public int minPathSum(int[][] grid) {
if(grid.length==0||grid[0].length==0){
return 0;
}
//2D map -- O(m*n) space
int[][] resultMap = new int[grid.length][grid[0].length];
resultMap[0][0] = grid[0][0];
//Calculate the first row
for(int i = 1;i<grid[0].length;i++){
resultMap[0][i] = grid[0][i] + resultMap[0][i-1];
}
//Calculate the first col
for(int i = 1;i<grid.length;i++){
resultMap[i][0] = grid[i][0] + resultMap[i-1][0];
}
//Calculate the rest
for(int i=1;i<grid.length;i++){
for(int j=1;j<grid[0].length;j++){
resultMap[i][j] = grid[i][j]+Math.min(resultMap[i-1][j],resultMap[i][j-1]);
}
}
return resultMap[grid.length-1][grid[0].length-1];
}
}```

Note: First calculate first row and first col which is there own grid value, then calculate other cells based on it.

3. *Optimal* Iterative Solution (O(n) space)

```public class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;

//1D map -- O(n) space, n is # of cols
int[] resultMap = new int[cols];
resultMap[0] = grid[0][0];

//Calculate the first row
for (int i = 1; i < grid[0].length; i++) {
resultMap[i] = grid[0][i] + resultMap[i - 1];
}

for (int i = 1; i < rows; i++) {
resultMap[0] = resultMap[0] + grid[i][0];
for (int j = 1; j < cols; j++) {
resultMap[j] = grid[i][j] + Math.min(resultMap[j], resultMap[j - 1]);
}
}
return resultMap[cols - 1];
}
}```

Note: You don’t necessarily need a 2d map to store which cost O(n) space where n is the # of columns. You can just use one row to stored the result of previous row, and replace the value with the current row from left to right one by one. One thing worth mentioning is this code is more space efficient though, it has lower readability.

More information and further thoughts for minimum path sum questions can be found here.