DFS

841. Keys and Rooms

Start room 0 to DFS all rooms. Use a set to keep track of the visited rooms. Return true if the visited number of rooms equals total number of rooms.

public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    Set<Integer> visited = new HashSet<>();
    dfs(0, rooms, visited);
    return visited.size() == rooms.size();
}

private void dfs(int curt, List<List<Integer>> rooms, Set<Integer> visited) {
    visited.add(curt);
    if (rooms.get(curt) == null) return;
    for (int next : rooms.get(curt)) {
        if (visited.contains(next)) continue;
        dfs(next, rooms, visited);
    }
}

733. Flood Fill

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    dfs(image, sr, sc, image[sr][sc], newColor);
    return image;
}

private void dfs(int[][] image, int x, int y, int orginal, int newColor) {
    if (x < 0 || x >= image.length || y < 0 || y >= image[0].length 
    || image[x][y] != orginal 
    || image[x][y] == newColor ) return;
    image[x][y] = newColor;
    dfs(image, x + 1, y, orginal, newColor);
    dfs(image, x - 1, y, orginal, newColor);
    dfs(image, x, y + 1, orginal, newColor);
    dfs(image, x, y - 1, orginal, newColor);
}

130. Surrounded Regions

DFS to fill the edge nodes and its linked nodes to a temporary state (eg. 'T'). Fill the middle nodes then fill all 'T's back to it is original state 'O'.

int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public void solve(char[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) return;
    int m = board.length, n = board[0].length;
    // fill boarder 'O' as 'T';
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') fill(board, i, 0);
        if (board[i][n - 1] == 'O') fill(board, i, n - 1);
    }
    for (int j = 0; j < n ; j++) {
        if (board[0][j] == 'O') fill(board, 0, j);
        if (board[m - 1][j] == 'O') fill(board, m - 1, j);
    }
    // flip all 'O' to 'X'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
        }
    }
    
    // flip all 'T' to 'O'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'T') board[i][j] = 'O';
        }
    }
}

private void fill(char[][] board, int x, int y) {
    if (!inbound(board, x, y) || board[x][y] != 'O') return;
    board[x][y] = 'T';
    for (int[] d : dirs) {
        fill(board, x + d[0], y + d[1]);
    }
}

private boolean inbound(char[][] board, int x, int y) {
    return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}

directions = [[0,1],[1,0],[-1,0], [0,-1]]
def solve(self, board: List[List[str]]) -> None:
    if not board or len(board) == 0 or len(board[0]) == 0:
        return
    m = len(board)
    n = len(board[0])
    queue = []
    for i in range(0, m):
        if board[i][0] == "O":
            queue.append([i, 0])
        if board[i][n - 1] == "O":
            queue.append([i, n - 1])
    for j in range(0, n):
        if board[0][j] == "O":
            queue.append([0, j])
        if board[m - 1][j] == "O":
            queue.append([m - 1, j])
    while queue:
        x, y = queue.pop(0)
        board[x][y] = "B"  
        for d in self.directions:  ## x= 3,y=1
            nx = x + d[0]
            ny = y + d[1]
            if self.inbound(board, nx, ny) and board[nx][ny] == "O":
                queue.append([nx, ny])
    
    for i in range(0, m):
        for j in range(0, n):
            if board[i][j] == "O":
                board[i][j] = "X"
            if board[i][j] == "B":
                board[i][j] = "O"
    

def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

1020. Number of Enclaves

int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int numEnclaves(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) {
            fill(grid, i, 0, 2);
        }
        if (grid[i][n - 1] == 1) {
            fill(grid, i, n - 1, 2);
        }
    }
    for (int i = 0; i < n; i++) {
        if (grid[0][i] == 1) {
            fill(grid, 0, i, 2);
        }
        if (grid[m - 1][i] == 1) {
            fill(grid, m - 1, i, 2);
        }
    }
    int total = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                total += fill(grid, i, j, 0);
            }
        }
    }
    return total;
}

private int fill(int[][] grid, int x, int y, int fillNum) {
    if (!inbound(grid, x, y) || grid[x][y] != 1) {
        return 0;
    }
    int total = 1;
    grid[x][y] = fillNum;
    for (int[] d : dir) {
        int nx = x + d[0], ny = y + d[1];
        total += fill(grid, nx, ny, fillNum);
    }
    return total;
}

private boolean inbound(int[][] grid, int x, int y) {
    return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}

200. Number of Islands

When reach a node of an Island, DFS all nodes and fill the grid with '0'. This would eliminate repeated traversal.

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    this.n = grid.length;
    this.m = grid[0].length;
    this.grid = grid;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 
        || i >= grid.length 
        || j < 0 
        || j >= grid[0].length 
        || grid[i][j] != '1') return;
    grid[i][j] = '0';
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
}

directions = [[0,1],[1,0],[-1,0], [0,-1]]
def numIslands(self, grid: List[List[str]]) -> int:
    count = 0
    for x in range(0, len(grid)):
        for y in range(0, len(grid[0])):
            if grid[x][y] == "1":
                self.bfs(grid, x, y)
                count += 1
    return count

def bfs(self, grid, x, y):
    queue = []
    queue.append([x, y])
    grid[x][y] = "0"
    while queue:
        curt = queue.pop(0)   
        for d in self.directions:
            nextx = curt[0] + d[0]  
            nexty = curt[1] + d[1]
            if nextx >= 0 and nextx < len(grid) and nexty >= 0 and nexty < len(grid[0]) and grid[nextx][nexty] == "1":
                queue.append([nextx, nexty])
                grid[nextx][nexty] = "0"

directions = [[0,1],[1,0],[-1,0], [0,-1]]
def numIslands(self, grid: List[List[str]]) -> int:
    count = 0
    for x in range(0, len(grid)):
        for y in range(0, len(grid[0])):
            if grid[x][y] == "1":
                self.dfs(grid, x, y)
                count += 1
    return count

def dfs(self, grid, x, y):
    grid[x][y] = "0"
    for d in self.directions:
        nextx = x + d[0]  
        nexty = y + d[1]
        if nextx >= 0 and nextx < len(grid) and nexty >= 0 and nexty < len(grid[0]) and grid[nextx][nexty] == "1":
            self.dfs(grid, nextx, nexty)

695. Max Area of Island

public int maxAreaOfIsland(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int max = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                max = Math.max(max, dfs(grid, i, j));
            }
        }
    }
    return max;
}

private int dfs(int[][] grid, int x, int y) {
    if (!inbound(grid, x, y) || grid[x][y] == 0) return 0;
    int count = grid[x][y] == 1 ? 1 : 0;
    grid[x][y] = 0;
    count += dfs(grid, x + 1, y) 
           + dfs(grid, x - 1, y) 
           + dfs(grid, x, y + 1) 
           + dfs(grid, x, y - 1);
    return count;
}

private boolean inbound(int[][] board, int x, int y) {
    return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}

directions = [[0,1],[1,0],[-1,0],[0,-1]]
res = 0
curtRes = 0
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                self.curtRes = 0
                self.dfs(grid, i, j)
                self.res = max(self.res, self.curtRes)
    return self.res

def dfs(self, grid, x, y):
    grid[x][y] = 0
    self.curtRes += 1
    for dx, dy in self.directions:
        nx = x + dx
        ny = y + dy
        if self.inbound(grid, nx, ny) and grid[nx][ny] == 1:
            self.dfs(grid, nx, ny)
    
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

directions = [[0,1],[1,0],[-1,0],[0,-1]]
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    res = 0
    m = len(grid)
    n = len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                res = max(res, self.dfs(grid, i, j))
    return res

def dfs(self, grid, x, y):
    if not self.inbound(grid, x, y) or grid[x][y] != 1:
        return 0
    count = 0
    if grid[x][y] == 1:
        count = 1
    grid[x][y] = 0
    for dx, dy in self.directions:
        nx = x + dx
        ny = y + dy
        count += self.dfs(grid, nx, ny)
    return count
    
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

694. Number of Distinct Islands

Distinctness can be determined by the shape of the island, however saving the shape might be a bit difficult. An easier way is to save the pattern of traversal.

Starting with top left corner fo the island, DFS and use a StringBuilder to save the directions. Save "0" at when breaking out the recursion

sb.append("0");

since it represents the pattern of recursive traversal, move both forward and backwards.

int[][] dirs = {{1,0},{0,1},{-1,0}, {0,-1}};
boolean[][] visited;
public int numDistinctIslands(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    visited = new boolean[m][n];
    Set<String> set = new HashSet<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                StringBuilder sb = new StringBuilder();
                dfs(grid, i, j, 0, sb);
                set.add(sb.toString());
            }
        }
    }
    return set.size();
}

private void dfs(int[][] grid, int x, int y, int dir, StringBuilder sb) {
    visited[x][y] = true;
    grid[x][y] = 0;
    sb.append(dir);
    for (int i = 0; i < dirs.length; i++) {
        int next_x = x + dirs[i][0];
        int next_y = y + dirs[i][1];
        if (next_x >= 0 
            && next_y >= 0 
            && next_x < grid.length 
            && next_y < grid[0].length 
            && grid[next_x][next_y] == 1 
            && !visited[next_x][next_y]) {
            dfs(grid, next_x, next_y, i, sb);
        }
    }
    sb.append("0");
}

directions = [[-1,0],[0,1], [1,0],[0,-1]]
path = ""
def numDistinctIslands(self, grid: List[List[int]]) -> int:
    res = set()
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                self.path = ""
                self.dfs(grid, i, j)
                print(self.path)
                res.add(self.path)
    return len(res)

def dfs(self, grid, x, y):
    if not self.inbound(grid, x, y) or grid[x][y] != 1:
        return
    grid[x][y] = 0
    for k in range(0, 4):
        self.path += str(k) + ","
        nx = x + self.directions[k][0]
        ny = y + self.directions[k][1]
        self.dfs(grid, nx, ny)
    
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

1254. Number of Closed Islands

This problem is similar as other 'island on graph' problems. However, the DFS is quite tricky. You have to make sure all nodes are filled. Also the DFS of each level can't terminate early. For example:

res = dfs(grid, next_x, next_y) && res;

is the only way to complete the traversal. Other ways such as:

if (true) : return true
if (false): return false
res = res && dfs(grid, next_x, next_y)

will terminate the recursion early.

public int closedIsland(int[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 0 && dfs(grid, i, j)) {
                count++;
            }
        }
    }
    return count;
}
int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
private boolean dfs(int[][] grid, int x, int y) {
    if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
        return false;
    }
    if (grid[x][y] == 1 || grid[x][y] == 2) {
        return true;
    }
    boolean res = true;
    grid[x][y] = 2;
    for (int[] dir : dirs) {
        int next_x = x + dir[0];
        int next_y = y + dir[1];
        res = dfs(grid, next_x, next_y) && res;
    }
    return res;
}

305. Number of Islands II305. Number of Islands II

UnionFind

419. Battleships in a Board

DFS when see the ship

public int countBattleships(char[][] board) {
    int count = 0;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 'X') {
                count++;
                dfs(board, i, j, true);
                board[i][j] = 'X';
                dfs(board, i, j, false);
            }
        }
    }
    return count;
}

private void dfs(char[][] board, int x, int y, boolean hori) {
    if (!inbound(board, x, y) || board[x][y] != 'X') return;
    board[x][y] = '.';
    if (hori) {
        dfs(board, x, y + 1, hori);
        dfs(board, x, y - 1, hori);
    } else {
        dfs(board, x + 1, y, hori);
        dfs(board, x - 1, y, hori);
    }
}

private boolean inbound(char[][] board, int x, int y) {
    return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}

Solution2: one pass

public int countBattleships(char[][] board) {
    int m = board.length;
    if (m==0) return 0;
    int n = board[0].length;
    
    int count=0;
    
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (board[i][j] == '.') continue;
            if (i > 0 && board[i-1][j] == 'X') continue;
            if (j > 0 && board[i][j-1] == 'X') continue;
            count++;
        }
    }
    return count;
}

529. Minesweeper

Get number of mines of each grid. If mine count == 0, set board to 'B' and keep traversing. Otherwise set the grid to that mine number.

T: O( 8* (m*n) ^ 2)

    int[][] dirs = new int[][]{
        {0,1}, {0, -1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1},{-1,-1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0];
        int y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        dfs(board, x, y);
        return board;
    }
    
    private void dfs(char[][] board, int x, int y) {
        if (!inbound(board, x, y) || board[x][y] != 'E') return;
        int num = getMineNum(board, x, y);
        if (num == 0) {
            board[x][y] = 'B';
            for (int[] dir : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                dfs(board, newX, newY);
            }
        } else {
            board[x][y] = (char) ('0' + num);
        }
    }
    
    private int getMineNum(char[][] board, int x, int y) {
        int count = 0;
        for (int[] dir : dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (inbound(board, newX, newY) && 
                (board[newX][newY] == 'M' || board[newX][newY] == 'X')) {
                count++;
            }
        }
        return count;
    }
    
    private boolean inbound(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

339. Nested List Weight Sum

public int depthSum(List<NestedInteger> nestedList) {
    return dfs(nestedList, 1);
}

private int dfs(List<NestedInteger> nestedList, int level) {
    int sum = 0;
    for (NestedInteger ni : nestedList) {
        if (ni.isInteger()) {
            sum += ni.getInteger() * level;
        } else {
            sum += dfs(ni.getList(), level + 1);
        }
    }
    return sum;
}

364. Nested List Weight Sum II

public int depthSumInverse(List<NestedInteger> nestedList) {
    int maxDepth = getDepth(nestedList);
    return getSum(nestedList, maxDepth);
}

private int getSum(List<NestedInteger> nestedList, int depth) {
    int sum = 0;
    for (NestedInteger ni : nestedList) {
        if (ni.isInteger()) {
            sum += depth * ni.getInteger();
        } else {
            sum += getSum(ni.getList(), depth - 1);
        }
    }
    return sum;
}

private int getDepth(List<NestedInteger> nestedList) {
    int depth = 0;
    for (NestedInteger ni : nestedList) {
        if (ni.isInteger()) {
            depth = Math.max(depth, 1);
        } else {
            depth = Math.max(depth, getDepth(ni.getList()) + 1);
        }
    }
    return depth;
}

public int depthSumInverse(List<NestedInteger> nestedList) {
   Queue<NestedInteger> q = new LinkedList(nestedList);
   int prevSum = 0, total = 0;
   while(!q.isEmpty()){
       int size = q.size();
       for(int i = 0; i < size; ++i){
           NestedInteger ni = q.poll();
           if(ni.isInteger()){
               prevSum += ni.getInteger();
           }else{
               q.addAll(ni.getList());
           }
       }
       total += prevSum;
   }
   return total;
}

79. Word Search

int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || board[0].length == 0) return false;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, i, j, word.toCharArray(), 0)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, int x, int y, char[] word, int index) {
    if (index == word.length)  return true;
    if (index == word.length - 1 && word[index] == board[x][y]) return true;
    if (!inbound(board, x, y)) return false;
    if (word[index] != board[x][y]) return false;
    char curt = board[x][y];
    board[x][y] = '#';
    for (int[] d : dirs) {
        int nx = x + d[0];
        int ny = y + d[1];
        if (inbound(board, nx, ny) && dfs(board, nx, ny, word, index + 1)) {
            return true;
        }
    }
    board[x][y] = curt;
    return false;
}

private boolean inbound(char[][] board, int x, int y) {
    return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
}

directions = [[0,1],[1,0],[-1,0],[0,-1]]
def exist(self, board: List[List[str]], word: str) -> bool:
    m = len(board) 
    n = len(board[0])
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and self.dfs(board, i, j, word, 0):
                return True
    return False
            
def dfs(self, board, x, y, word, index):
    if not self.inbound(board, x, y) or board[x][y] != word[index]:
        return False
    if index == len(word) or (index + 1 == len(word) and word[index] == board[x][y]):
        return True
    temp = board[x][y]
    board[x][y] = '#'
    for dx, dy in self.directions:
        nx = x + dx
        ny = y + dy
        if self.dfs(board, nx, ny, word, index + 1) :
            return True
    board[x][y] = temp
    return False
        
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

139. Word Break

Search words on that input String s to find if that set contains a prefix of s. Use memorization to eliminate redundant traversal.

T: O (n^2) S : O (n)

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>();
        dict.addAll(wordDict);
        Map<String, Boolean> memo = new HashMap<>();
        return dfs(s, dict, memo);
    }
    
    private boolean dfs(String s, 
                        Set<String> dict, 
                        Map<String, Boolean> memo) {
        if (dict.contains(s)) return true;
        if (memo.containsKey(s)) return memo.get(s);
        for (int i = 0; i < s.length(); i++) {
            if (dict.contains(s.substring(0, i)) && dfs(s.substring(i), dict, memo)) {
                memo.put(s, true);
                return true;
            }
        }
        memo.put(s, false);
        return false;
    }

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    dic = set(wordDict)
    memo = {}
    return self.dfs(s, dic, memo)
    
def dfs(self, s, dic, memo):
    if s in dic:
        return True
    if s in memo:
        return memo[s]
    for i in range(1, len(s)):
        if s[:i] in dic and self.dfs(s[i:], dic, memo):
            memo[s[i:]] = True
            return True
    memo[s] = False
    return False

Solution2 : dp

140. Word Break II

Instead of return boolean, carry results.

T: O(n^2 + 2^n + W) W is number of words in the dictionary. S: O(2^n * n + W)

public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>();
    dict.addAll(wordDict);
    return dfs(s, 0,  dict, new HashMap<Integer, List<String>>());
}

private List<String> dfs(String s, int index, 
    Set<String> dict, HashMap<Integer, List<String>> memo) {
    if (memo.containsKey(index)) return memo.get(index);
    List<String> res = new ArrayList<>();
    if (index == s.length()) {
        res.add("");
        return res;
    }
    for (String prefix : dict) {
        if (s.substring(index).startsWith(prefix)) {
            List<String> next = dfs(s, index + prefix.length(), dict, memo);
            for (String nxt : next) {
                res.add(prefix + (nxt.equals("") ? "" : " ") + nxt);
            }
        }
    }
    memo.put(index, res);
    return res;
}

261. Graph Valid Tree

Build graph from edge. Traverse to see no repeated visited node. Also add count visited nodes to see if it equals n, which means there is no left over nodes.

T: O(n) S: O(n)

int visits = 0;
public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for (int[] e : edges) {
        map.putIfAbsent(e[0], new HashSet<>());
        map.putIfAbsent(e[1], new HashSet<>());
        map.get(e[0]).add(e[1]);
        map.get(e[1]).add(e[0]);
    }
    return dfs(0, -1, new boolean[n], map) && visits == n;
}

private boolean dfs(int curt, int parent, boolean[] visited, Map<Integer, Set<Integer>> map) {
    visited[curt] = true;
    visits++;
    if (map.get(curt) == null) return true;
    for (int next : map.get(curt)) {
        if (next == parent) continue;
        if (visited[next]) return false;
        if (!dfs(next, curt, visited, map)) return false;
    }
    return true;
}

def validTree(self, n: int, edges: List[List[int]]) -> bool:
    if n - 1 != len(edges):
        return False
    graph = [[] for i in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    return self.dfs(-1, 0, graph, visited) and len(visited) == n
    
def dfs(self, parent, curt, graph, visited):
    if curt in visited:
        return False
    visited.add(curt)
    for nxt in graph[curt]:
        if parent == nxt:
            continue
        if not self.dfs(curt, nxt, graph, visited):
            return False
    return True

399. Evaluate Division

This is a weighted edge graph. Construct the graph of the equations and values. Traverse the graph by using DFS or BFS to query result. Starting with 1.0 and cumulate the weight of each traversal.

public double[] calcEquation(List<List<String>> equations,
                             double[] values,
                             List<List<String>> queries) {
    Map<String, Map<String, Double>> map = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0);
        String b = equations.get(i).get(1);
        map.putIfAbsent(a, new HashMap<>());
        map.putIfAbsent(b, new HashMap<>());
        map.get(a).put(b, values[i]);
        map.get(b).put(a, 1.0 / values[i]);
    }
    double[] res = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        double r = dfs(map,
                new HashSet<>(),
                queries.get(i).get(0),
                queries.get(i).get(1),
                1.0);
        res[i] = r == Double.MAX_VALUE ? -1.0 : r;
    }
    return res;
}

private double dfs(Map<String, Map<String, Double>> map,
                   Set<String> visited,
                   String curt,
                   String target,
                   double curtRes) {
    if (map.get(curt) == null) return Double.MAX_VALUE;
    if (curt.equals(target)) return curtRes;
    visited.add(curt);
    for (String next : map.get(curt).keySet()) {
        if (visited.contains(next)) continue;
        double res = dfs(map, visited, next, target, curtRes * map.get(curt).get(next));
        if (res != Double.MAX_VALUE) {
            return res;
        }
    }
    return Double.MAX_VALUE;
}

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    graph = {}
    for i in range(len(equations)):
        u, v, value = equations[i][0], equations[i][1], values[i]
        if u not in graph:
            graph[u] = []
        graph[u].append([v, value])
        if v not in graph:
            graph[v] = []
        graph[v].append([u, 1 / value])
        
    res = []
    for u, v in queries:
        visited = set()
        res.append(self.dfs(u, v, graph, visited))
    return res

def dfs(self, u, v, graph, visited):
    if u not in graph or u in visited:
        return -1.0
    visited.add(u)
    for nxt, value in graph[u]:
        if nxt == v:
            return value
        res = self.dfs(nxt, v, graph, visited)
        if res != -1.0:
            return res * value
    return -1.0

37. Sudoku Solver

Backtracking and solve.

public void solveSudoku(char[][] board) {
    if (board == null || board.length == 0){
        return;
    }
    dfs(board);
}

private boolean dfs(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') continue;
            for (char c = '1'; c <= '9'; c++) {
                if (isValid(board, i, j, c)) {
                    board[i][j] = c;
                    if (dfs(board)) return true;
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }
    return true;
}

public boolean isValid(char[][] board, int row, int col, char c){
    for(int i = 0; i < 9; i++) {
        if(board[i][col] == c) return false; //check row
        if(board[row][i] == c) return false; //check column
        if(board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
    }
    return true;
}

1197. Minimum Knight Moves

DFS to get the shortest path. Using Memo. Also cutting branch by only goes in one direction will help to reduce the total paths.

public int minKnightMoves(int x, int y) {
    int[][] memo = new int[301][301];
    for (int[] row : memo) {
        Arrays.fill(row, -1);
    }
    memo[1][2] = 1;
    memo[2][1] = 1;
    memo[0][0] = 0;
    memo[1][1] = 2;
    memo[1][0] = 3;
    memo[2][0] = 2;
    return dfs(x, y, memo);
}

private int dfs(int x, int y, int[][] memo) {
    if (x == 0 && y == 0) {
        return 0;
    }
    if (y > x) {
        int temp = x;
        x = y;
        y = temp;
    }
    x = Math.abs(x);
    y = Math.abs(y);
    if (memo[x][y] != -1) {
        return memo[x][y];
    }
    int res = Math.min(dfs(x - 1, y - 2, memo), dfs(x - 2, y - 1, memo)) + 1;
    memo[x][y] = res;
    return res;
}

1335. Minimum Difficulty of a Job Schedule

public int minDifficulty(int[] jobDifficulty, int d) {
    int n = jobDifficulty.length;
    if (n < d) return -1;
    int[][] cache = new int[n][d + 1];
    for (int[] row : cache) {
        Arrays.fill(row, -1);
    }
    return dfs(jobDifficulty, 0, n, d, cache);
}

private int dfs(int[] nums, int i, int n, int d, int[][] cache) {
    if (cache[i][d] != -1) {
        return cache[i][d];
    }
    if (d == 1) {
        int max = 0;
        while (i < n) {
            max = Math.max(max, nums[i++]);
        }
        return max;
    }
    int res = Integer.MAX_VALUE, maxOnDay = 0;
    for (int j = i; j < n - d + 1; j++) {
        maxOnDay = Math.max(maxOnDay, nums[j]);
        res = Math.min(res, dfs(nums, j + 1, n, d - 1, cache) + maxOnDay);
    }
    cache[i][d] = res;
    return res;
}

329. Longest Increasing Path in a Matrix

Store the longest path from current position x, y in a memo matrix.

int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int[][] memo;
int res = 1;
public int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    memo = new int[m][n];
    for (int[] row : memo) Arrays.fill(row, -1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dfs(i, j, matrix, memo);
        }
    }
    return res;
}

private int dfs(int x, int y, int[][] matrix, int[][] memo) {
    int len = 1;
    for (int[] d : dir) {
        int nx = x + d[0], ny = y + d[1];
        if (inbound(matrix, nx, ny) && matrix[nx][ny] > matrix[x][y]) {
            if (memo[nx][ny] != -1) {
                len = Math.max(len, 1 + memo[nx][ny]);
            } else {
                len = Math.max(len, 1 + dfs(nx, ny, matrix, memo));
            }
        }
    }
    memo[x][y] = len;
    res = Math.max(res, memo[x][y]);
    return len;
}

private boolean inbound(int[][] m, int x, int y) {
    return x >= 0 && y >= 0 && x < m.length && y < m[0].length;
}

980. Unique Paths III

679. 24 Game

public boolean judgePoint24(int[] nums) {
    if (nums == null || nums.length != 4) {
        return false;
    }
    List<Double> list = new ArrayList<>();
    for (int n : nums) list.add((double) n);
    return dfs(list);
}

private boolean dfs(List<Double> list) {
    if (list.size() == 1) {
        return Math.abs(list.get(0) - 24) < 0.001;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        for (int j = i + 1; j < list.size(); j++) {
            for (double d :  compute(list.get(i), list.get(j))) {
                List<Double> nexts = new ArrayList<>();
                nexts.add(d);
                for (int k = 0; k < list.size(); k++) {
                    if (i != k && j != k) {
                        nexts.add(list.get(k));
                    }
                }
                if (dfs(nexts)) return true;
            }
        }
    }
    return false;
}

private List<Double> compute(double a, double b) {
    List<Double> list = new ArrayList<>();
    list.add(a + b);
    list.add(a - b);
    list.add(b - a);
    list.add(a * b);
    if (b != 0) list.add(a / b);
    if (a != 0) list.add(b / a);
    return list;
}

2101. Detonate the Maximum Bombs

class Solution {
private: 
    int maxVal = 1;
    void dfs(const vector<vector<int>>& bombs, vector<vector<int>>& graph, unordered_set<int>& visited, int index) {
        visited.insert(index);
        maxVal = max(maxVal, (int)visited.size());
        for (int next : graph[index]) {
            if (visited.count(next)) continue;
            dfs(bombs, graph, visited, next);
        }
    }

public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        vector<vector<int>> graph(n);
        // Build graph: edge from i to j if bomb i can detonate bomb j
        for (int i = 0; i < n; ++i) {
            long long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                long long dx = x1 - bombs[j][0];
                long long dy = y1 - bombs[j][1];
                if (dx * dx + dy * dy <= r1 * r1) {
                    graph[i].push_back(j);
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            unordered_set<int> visited;
            dfs(bombs, graph, visited, i);
        }   
        return maxVal;     
    }
};

PreviousBFS NextDFS on String

Last updated 6 months ago

Was this helpful?

hashtag305. Number of Islands II305. Number of Islands II

305. Number of Islands II305. Number of Islands II