74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution:

This is a binary search problem.

We map the two dimensional coordinates to one dimensional number.

Thus, the time complexity can be optimized to O(log(mn)).



Code:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / n][mid % n] <= target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (matrix[end / n][end % n] == target) {
            return true;
        }
        if (matrix[start / n][start % n] == target) {
            return true;
        }
        return false;
    }
}

119. Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Solution:

The idea is that in each level, we need to know the previous level first.

Based on the result of the previous level, we insert a 1 at the beginning.

Then, start from the second element, we update its value by adding the value of the next element.

Since the last element has no next element, it will be always 1.

We use linked list to store the numbers so that we can achieve constant space requirement.

The time complexity is O(n²) and the space complexity is O(1).



Code:

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new LinkedList<>();
        if (rowIndex < 0) {
            return result;
        }
        for (int i = 0; i <= rowIndex; i++) {
            result.add(0, 1);
            for (int j = 1; j < result.size() - 1; j++) {
                result.set(j, result.get(j) + result.get(j + 1));
            }
        }
        return result;
    }
}

643. Maximum Average Subarray I

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1. 1 <= k <= n <= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

Solution:

This is a sliding window problem.

If we know how to deal with sliding window, this problem is easy to solve.

We keep a window of size k, and move from left to right.

In each move, we remove the leftmost element in this window and add the new element from right.

The time complexity is O(n) and the space complexity is O(1).



Code:

public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double sum = 0;
        double max = Integer.MIN_VALUE;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        max = Math.max(max, sum / k);
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            max = Math.max(max, sum / k);
        }
        return max;
    }
}

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.

Solution:

At any stone, we need to have the previous states of the previous stones such that we can decide whether this stone is reachable:

1. Whether this stone is reachable?

2. What is the length of the last jump to reach this stone?

To record these, we can use a HashMap to record the mapping of a stone and a set of last jumps to this stone.

We start from the first stone and fill the possible jumps to the later stones.

After filling all possible jumps, we simply check whether is last stone is reachable by checking its possible jump set.



Code:

public class Solution {
    public boolean canCross(int[] stones) {
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int stone : stones) {
            map.put(stone, new HashSet<Integer>());
        }
        map.get(0).add(0);
        for (int stone : stones) {
            for (int lastJump : map.get(stone)) {
                for (int nextJump = lastJump - 1; nextJump <= lastJump + 1; nextJump++) {
                    if (nextJump > 0 && map.containsKey(stone + nextJump)) {
                        map.get(stone + nextJump).add(nextJump);
                    }
                }
            }
        }
        return !map.get(stones[stones.length - 1]).isEmpty();
    }
}

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board = 

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

Solution:

We use a Trie to store all valid words.

Then use DFS to try if any word is valid in the board.

Code:

public class Solution {
    
    class TrieNode {
        TrieNode[] link;
        String word;
        public TrieNode() {
            this.link = new TrieNode[26];
            this.word = null;
        }
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return result;
        }
        if (words == null || words.length == 0) {
            return result;
        }
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, root, i, j, result);
            }
        }
        return result;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.link[c - 'a'] == null) {
                    curr.link[c - 'a'] = new TrieNode();
                }
                curr = curr.link[c - 'a'];
            }
            curr.word = word;
        }
        return root;
    }
    
    public void dfs(char[][] board, TrieNode curr, int i, int j, List<String> result) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        char c = board[i][j];
        if (c == '#' || curr.link[c - 'a'] == null) {
            return;
        }
        curr = curr.link[c - 'a'];
        if (curr.word != null) {
            result.add(curr.word);
            curr.word = null;
        }
        board[i][j] = '#';
        dfs(board, curr, i - 1, j, result);
        dfs(board, curr, i + 1, j, result);
        dfs(board, curr, i, j - 1, result);
        dfs(board, curr, i, j + 1, result);
        board[i][j] = c;
    }
}

126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution:

We first apply BFS to construct a adjacent list storing the mapping of each node and its neighbors.

In the BFS process, we also create a distance map which maps the shortest distance of each node from start.

Having these information, we can then apply DFS to add all valid path.

In each recursion step, we check if the distance of the neighbor of the current node has exactly one steps further than the current node, it is a valid candidate.



Code:

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        HashMap<String, Integer> distance = new HashMap<>();
        HashMap<String, List<String>> adj = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dict.add(beginWord);
        bfs(beginWord, endWord, dict, adj, distance);    
        path.add(beginWord);
        dfs(beginWord, endWord, result, path, dict, adj, distance);
        return result;
    }
    
    public List<String> getNeighbor(String word, HashSet<String> dict) {
        List<String> result = new ArrayList<>();
        char[] arr = word.toCharArray();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == c) {
                    continue;
                }
                char ch = arr[i];
                arr[i] = c;
                if (dict.contains(String.valueOf(arr))) {
                    result.add(String.valueOf(arr));
                }
                arr[i] = ch;
            }
        }
        return result;
    }
    
    public void bfs(String start, 
                    String end, 
                    HashSet<String> dict, 
                    HashMap<String, List<String>> adj, 
                    HashMap<String, Integer> distance) {
        
        for (String word : dict) {
            adj.put(word, new ArrayList<String>());
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        distance.put(start, 0);
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            int level = distance.get(curr);
            List<String> neighbor = getNeighbor(curr, dict);
            for (String nei : neighbor) {
                adj.get(curr).add(nei);
                if (!distance.containsKey(nei)) {
                    distance.put(nei, level + 1);
                    if (!end.equals(nei)) {
                        queue.offer(nei);
                    }
                }
            }
        }
    }
    
    public void dfs(String curr,
                    String end, 
                    List<List<String>> result, 
                    List<String> path, 
                    HashSet<String> dict, 
                    HashMap<String, List<String>> adj, 
                    HashMap<String, Integer> distance) {
        
        if (curr.equals(end)) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (String nei : adj.get(curr)) {
            path.add(nei);
            if (distance.containsKey(nei) && distance.get(nei) == distance.get(curr) + 1) {
                dfs(nei, end, result, path, dict, adj, distance);
            }
            path.remove(path.size() - 1);
        }
    }
}

52. N-Queens II

Follow up for N-Queens problem.

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

Solution:

This problem is a simplified version of N-Queens.

We use the same DFS to keep inserting queens to valid positions.

The only difference is that we do not need to draw the board.



Code:

public class Solution {
    public int sum;
    public int totalNQueens(int n) {
        sum = 0;
        if (n <= 0) {
            return sum;
        }
        int[] col = new int[n];
        helper(n, col, 0);
        return sum;
    }
    public void helper(int n, int[] col, int row) {
        if (row == n) {
            sum++;
            return;
        }
        for (int i = 0; i < n; i++) {
            col[row] = i;
            if (isValid(col, row)) {
                helper(n, col, row + 1);
            }
        }
    }
    public boolean isValid(int[] col, int row) {
        for (int i = 0; i < row; i++) {
            if (col[row] == col[i] || Math.abs(col[row] - col[i]) == row - i) {
                return false;
            }
        }
        return true;
    }
}

51. N-Queens

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.

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

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution:

This is a classic DFS problem.

We recursively insert a queen to a row and check if the board is still valid.

To record the status, we know each row only has one queen, and each column only has one queen.

We use an col[] array and use col[i] to denote which column we insert the queen in row i.

Therefore, when we try to insert a queen in the current row, we can check if a column j has already been used.

To check diagonal attack, we check if Math.abs(col[row2] - col[row1]) == row2 - row1.



Code:

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        int[] col = new int[n];
        helper(n, result, 0, col);
        return result;
    }
    
    public void helper(int n, List<List<String>> result, int row, int[] col) {
        if (row == n) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder s = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (j == col[i]) {
                        s.append("Q");
                    }
                    else {
                        s.append(".");
                    }
                }
                list.add(s.toString());
            }
            result.add(list);
        }
        else {
            for (int i = 0; i < n; i++) {
                col[row] = i;
                if (isValid(row, col)) {
                    helper(n, result, row + 1, col);
                }
            }
        }
    }
    
    public boolean isValid(int row, int[] col) {
        for (int i = 0; i < row; i++) {
            if (col[row] == col[i] || Math.abs(col[row] - col[i]) == row - i) {
                return false;
            }
        }
        return true;
    }
}

64. 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.

Solution:

Since we can only go right or go down, the minimum sum at each point only depends on its top and its left value.

We use f[i][j] to denote the minimum sum from the origin to coordinate (i, j).



Code:

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    f[i][j] = j == 0 ? grid[0][0] : grid[i][j] + f[i][j - 1];
                    continue;
                }
                if (j == 0) {
                    f[i][j] = i == 0 ? grid[0][0] : grid[i][j] + f[i - 1][j];
                    continue;
                }
                f[i][j] = grid[i][j] + Math.min(f[i - 1][j], f[i][j - 1]);
            }
        }
        return f[m - 1][n - 1];
    }
}

291. Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

Solution:

We use DFS + backtracking to check if the substring of pattern can be used to match there previous pattern.

In the recursion, we check if the current character has already had a mapping.

If so, we check if it can go along with this path to the end.

Otherwise, we use backtracking to put all candidate mapping of this character and check if it has its path to the end.

The end condition is that when we finish putting all character in the pattern string to the HashMap, we check if the target string has also been finished putting all its elements.



Code:

public class Solution {
    
    public HashMap<Character, String> map = new HashMap<>();
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        char c = pattern.charAt(0);
        if (map.containsKey(c)) {
            String value = map.get(c);
            if (value.length() > str.length() || !str.substring(0, value.length()).equals(value)) {
                return false;
            }
            if (wordPatternMatch(pattern.substring(1), str.substring(value.length()))) {
                return true;
            }
        }
        else {
            for (int i = 1; i <= str.length(); i++) {
                String value = str.substring(0, i);
                if (map.containsValue(value)) {
                    continue;
                }
                map.put(c, value);
                if (wordPatternMatch(pattern.substring(1), str.substring(value.length()))) {
                    return true;
                }
                map.remove(c);
            }
        }
        return false;
    }
}

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Solution:

This problem is a simplified version of Word Pattern.



Code:

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (!map.containsKey(c1)) {
                map.put(c1, c2);
            }
            else {
                if (map.get(c1) != c2) {
                    return false;
                }
            }
        }
        map.clear();
        for (int i = 0; i < t.length(); i++) {
            char c1 = t.charAt(i);
            char c2 = s.charAt(i);
            if (!map.containsKey(c1)) {
                map.put(c1, c2);
            }
            else {
                if (map.get(c1) != c2) {
                    return false;
                }
            }
        }
        return true;
    }
}

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution:

The idea is to create two HashMaps.

We first check the uniqueness between each character in the pattern to words in string using one HashMap.

Then we check the uniqueness between each words in the string to the character in the pattern using the second HashMap.

The reason to check twice is to handle such case:

"abcb" -> "dog cat dog cat"



Code:

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<Character, String> map1 = new HashMap<>();
        String[] strarr = str.split(" ");
        if (strarr.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map1.containsKey(c)) {
                map1.put(c, strarr[i]);
            }
            else {
                if (!map1.get(c).equals(strarr[i])) {
                    return false;
                }
            }
        }
        HashMap<String, Character> map2 = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map2.containsKey(strarr[i])) {
                map2.put(strarr[i], c);
            }
            else {
                if (map2.get(strarr[i]) != c) {
                    return false;
                }
            }
        }
        return true;
    }
}

72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution:

We use f[i][j] to denote the minimum edits to convert the first i element in word1 to become the first j elements in word2.

This state depends on four conditions:

1. remove the last character of the first i characters in word1 and line up with the first j characters in word2.

2. add a character at the end of the first i characters in word1 and line up with the first j characters in word2.

3. replace the character at the end of the first i characters and line up with the first j characters in word2.

4. the last characters of the first i characters in word1 and the first j characters in word2 are the same, no edit needed.



Code:

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        int[][] f = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    f[i][j] = j;
                    continue;
                }
                if (j == 0) {
                    f[i][j] = i;
                    continue;
                }
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                }
            }
        }
        return f[m][n];
    }
}