Longest Increasing Path in a Matrix

 Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 

[

  [9,9,4],

  [6,6,8],

  [2,1,1]

] 

Output: 4 

Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 

[

  [3,4,5],

  [3,2,6],

  [2,2,1]

] 

Output: 4 

Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution

We can use graph dfs traversal start at each node for find the increasing paths. Since we need to find the max length path, we need to explore all the possibilities. This is a time we think of backtracking. We need to explore all the other directions once we tested one direction. At each node, there will be 3 possible directions that have increasing number, for a m x n matrix, we could end up exploring power(3, mn) states for each node. We can cut down the computation with memorization. We remember the longest increasing path for each node, that way, each node only have to be processes once and the cost reduced to O(mn) for each node. Since there are mn nodes total, the time complexity is O(mmnn), the space complexity is O(mn) for the memorization cache.

import java.util.*;

class Solution {

  int maxLen =  Integer.MIN_VALUE;

  int[][] nums = 

    {

      {9,9,4},

      {6,6,8},

      {2,1,1}

    };

  int[][] memo = new int[nums.length][nums[0].length];

  public static void main(String[] args) {

    

    Solution sol = new Solution();

    sol.solve();

    System.out.println(sol.maxLen);

  }

  private void solve() {

    for(int row = 0; row < nums.length; row++) {

      for(int col = 0; col < nums[0].length; col++) {

        memo[row][col] = dfs(row, col);

        maxLen = Math.max(maxLen, memo[row][col]);

      }

    }

  }

  

  private int dfs(int row, int col) {

    if(memo[row][col] != 0) {

      return memo[row][col];

    }

    

    int[][] directions = new int[][]{

      {0, 1},

      {0, -1},

      {1, 0},

      {-1, 0}

    };

    int tmpMax = 1;

    for(int[] direct: directions) {

      int newRow = row + direct[0];

      int newCol = col + direct[1];

      if(newRow >= 0 && newRow < nums.length && newCol >= 0 && newCol < nums[0].length && nums[row][col] < nums[newRow][newCol]) {

        int len = dfs(newRow, newCol);

        memo[newRow][newCol] = len;

        tmpMax = Math.max(tmpMax, 1 + len);

      }

    }

    return tmpMax;

  }

}

Robot Room Cleaner

Problem:

The product robot room cleaner works as follows:

robot room cleaner

The robot can move forward, turn 90 degrees left, turn 90 degrees right.These movement allows it to move around. The robot also has a sensor to detect obstacles. Before the robot moves forward, the sensor will detect if an obstacle is located on the position it will move to, if yes, the robot cancels the move, then does a left or right turn then attempts to move forward.

Given a robot cleaner and a room floor that is divided into cells.

Each cell can be empty or blocked.

Design an algorithm to clean the entire floor using only the 4 given APIs shown below.

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is blocked and robot stays on the current cell.
  boolean forward();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}
For Example:

Given room cells
room = [
  [1,0,1,1,1,0,1,1],
  [1,0,0,0,1,0,1,1],
  [1,0,1,1,1,0,1,0],
  [0,0,0,0,0,0,0,0],
  [1,1,1,1,1,1,1,0]
],
All cells in the room are marked by either 0 or 1. All the cells outside of the matrix are blocked.
1 means the cell is blocked, while 0 means the cell is open. All open cells are connected.

The robot is put on a random open position, for example room[0][1] with initial direction of facing up.

Solution:

This is a standard dfs maze traversal problem. The news about this problem is the robot need to take corresponding actions during the dfs traversal, therefore we need to have a deep understanding of dfs process.

import java.util.*;
//import you.hardware.provider.package.*;
//invoke the program with command: java -cp .:HardwareVendorProvided.jar Solution
class Solution {
  private Set<Point> visited = new HashSet<>();
  /*replace this with a large enough all 0 2-d array when used with hardware
     the (room size / distance of robot forward moving) will decide the size of the 2-d array. It is large enough so that you can put the robot at center and there are cells in all 4 directions to cover the whole room area. */
  private static int[][] room = {
      {1,0,1,1,1,0,1,1},
      {1,0,0,0,0,0,1,1},
      {1,0,1,1,1,0,1,0},
      {0,0,0,0,0,0,0,0},
      {1,1,1,1,1,1,1,0}
    };
  private static int N = room.length;
  private static int M = room[0].length;
  //private static Robot robot = RobotFactory.makeRobot();

  public static void main(String[] args) {
    int x = 0;
    int y = 1;
    Solution s = new Solution();
    s.dfs(x, y);
    printRoom();
  }

  private void dfs(int row, int col) {
    visited.add(new Point(row, col));
    //robot.clean();
    room[row][col] = 2;
    int[] rowMask = new int[]{-1, 0, 1, 0};
    int[] colMask = new int[]{0, 1, 0, -1};
    for(int i = 0; i < rowMask.length; i++) {
      int nextRow = row + rowMask[i];
      int nextCol = col + colMask[i];
      if(canMove(nextRow, nextCol)) {
        dfs(nextRow, nextCol);
      } else {
        //robot.turnRight();
      }
    }
    //moveBack();
  }

  private void moveBack() {
    //robot.turnRight();
    //robot.turnRight();
    //robot.forward();
    //robot.turnLeft();
  }

  private boolean canMove(int row, int col) {
    if(visited.contains(new Point(row, col)))
      return false;
    //simulate sensor
    //return robot.forward();
    if(row < 0 || row >= N || col < 0 || col >= M)
      return false;
    return room[row][col] == 0;
  }

  private static class Point {
    int x;
    int y;
    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
    public boolean equals(Object o) {
      if(o == null) return false;
      if(!(o instanceof Point)) return false;
      Point other = (Point)o;
      return this.x == other.x && this.y == other.y;
    }
 
    public int hashCode() {
      return 31*x + y;
    }
  }
  private static void printRoom() {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {
        System.out.print(room[i][j] + " ");
      }
      System.out.println();
    }
  }
}

Time complexity is O(4^N) where N is the number of open cells. At each open cell, there are 4 directions to choose, total number of choices are 4^N. The space complexity is O(N), it is the max size of the caller stack.

Word Search

Problem:

You are given a 2-d array of letters a-zA-Z. Words can be constructed from neighboring cells in the 2-d array. The current cell's neighboring cells are the ones on top, bottom, left and right. One cell can be used only once for a word.

Check if a given word can be constructed from the given 2-d array.

For Example, Given array

[
  ['A','B','E','D'],
  ['E','F','E','H'],
  ['I','J','K','L']
]

word "BEE" can be constructed, so return true.
"SEE" can not be constructed, so return false.
"ABFE", return true.
"KEHD", return true.
"KLHEK", return false.

Solution:

At the first impression, this is a graph dfs traversal problem. We can start at each grid cell, do a dfs search for the word sequence. A second thought suggests that this problem is more than graph dfs. Our goal is to search the right path matching the word among all the possible dfs traversal paths. So we are actually doing the path permutation, and we need to use backtrack. That is to say, when we visit a node, if that visit turns out to be a wrong move, we should track back, unmark the node, then give another neighboring node a try.

Two small techniques we need to pay attention in the following code. 

1. In order to visit all the neighbor nodes, we create a row mask and a column mask

int[] rowmask = new int[1, 0, -1, 0];

int[] colmask = new int[0, 1, 0, -1];

for(int i = 0; i < 4; i++) {

  int i = row + rowmask[d];

  int j = col + colmask[d];

  ...

}

the i and j combinations will cover all the 4 neighbors.

2. we don't have to use a set to keep track of visited node. We can just set the visited node to any character that is not a-zA-Z, that way we saved row*col memory that the set need. The drawback of this approach is side effect, the original 2D array has been modified.

3. we check word.length() == index at the first line, that way, even we are given a one element array, the function still works without throwing java.lang.StringIndexOutOfBoundsException.

import java.util.*;
class Solution {
  private Set<Integer> visited = new HashSet<>();
  public boolean found(char[][] board, String word) {//"KEHD"
    for(int i = 0; i < board.length; i++) {
      for(int j = 0; j < board[i].length; j++) {
        visited = new HashSet<>();
        if(dfs(board, word, 0, i, j))
           return true;
      }
    }
    return false;
  }
  private boolean dfs(char[][] board, String word, int index, int row, int col) {
    if(word.length() == index) {
      return true;
    }
    if((row < 0 || row == board.length || col < 0 || col == board[0].length) || word.charAt(index) != board[row][col])
      return false;
   
    visited.add(row*board[0].length + col);//10
    //board[row][col] = '!';
    int[] rowmask = new int[] {0, 1, 0, -1};
    int[] colmask = new int[] {1, 0, -1, 0};
    for(int d = 0; d < 4; d++) {
      int i = row + rowmask[d];
      int j = col + colmask[d];
      if(!visited.contains(i*board[0].length + j)) {
        if(dfs(board, word, index + 1, i, j))
        return true;
      }
    }
    visited.remove(row*board[0].length + col);//unmark
    //board[row][col] = word.charAt(index);
    return false;
  }
  public static void main(String[] args) {
    char[][] board = new char[][]{
      {'A','B','E','D'},
      {'E','F','E','H'},
      {'I','J','K','L'}
    };
    printBoard(board);
    Solution sol = new Solution();
    System.out.println(sol.found(board, "BEE"));
    System.out.println(sol.found(board, "SEE"));
    System.out.println(sol.found(board, "ABFE"));
    System.out.println(sol.found(board, "KEHD"));
    System.out.println(sol.found(board, "KLHEK"));
    System.out.println(sol.found(board, "A"));
   
    printBoard(board);
  }
  private static void printBoard(char[][] board) {
    for(int i = 0; i < board.length; i++) {
      for(int j = 0; j < board[i].length; j++) {
        System.out.print(String.format("%3s", board[i][j]));
      }
      System.out.println();
    }
  }
}

The time complexity is O(N*(4^L)), where N is the total number of elements in the array and L is the word length. In the worst case, we do the dfs traversal for all the N cells. During each dfs traversal, we could find mismatch at the last word character, at each step we need to check 4 neighbors, so the cost is 4^L. The space complexity is O(L) which is the max depth of the dfs calling stack.

Number of Islands

Problem

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:

11110

11010

11000

00000

Output: 1

Example 2:

Input:

11000

11000

00100

00011

Output: 3

Solution

We need to check each grid, otherwise we might miss an island, the time cost at least should be O(MN). 

This problem is a standard undirected graph connected component problem. We can model each grid as a graph node, then each node has four edges connected to the neighboring node, then we iterate the nodes and use either dfs or bfs to count the connected components. With a large number of edges, the space complexity will be big, besides, we need to remember the visited edges with a HashSet.

With the following simplify, we can keep the space complexity under O(MN). 

• This is a grid not a random graph, so we don't need explicit edge, the four neighbors are always located at grid[r-1][c], grid[r+1][c], grid[r][c-1], grid[r][c+1].
• We don't need to remember which node has been visited. We just set the value to 0, that means we don't run dfs or bfs on the grid again.

So our algorithm is: we iterate the grid nodes, whenever we meet a 1, we increase the number of islands, then we do a dfs to erase the discovered island from the map. Finally, after we checked all the MN grid, we find the number of islands.

class Solution {

  int[][] grid = new int[][]{

      {1,1,0,0,0},

      {1,1,0,0,0},

      {0,0,1,0,0},

      {0,0,0,1,1}

  };

  int nr = grid.length;    //4

  int nc = grid[0].length; //5

  int count = 0;

  public static void main(String[] args) {

    Solution sol = new Solution();

    System.out.println(sol.count());

  }

  

  private int count() {

    for(int r = 0; r < nr; r++) {

      for(int c = 0; c < nc; c++) {

        if(grid[r][c] == 1) {

          count++;   //3

          dfs(r, c);

        }

      }

    }

    return count;

  }

  private void dfs(int r, int c) {

    if(r < 0 || r >= nr || c < 0 || c >= nc) {

        return;

    } 

    if(grid[r][c] == 0) {

      return;

    } else {

      grid[r][c] = 0;

      dfs(r - 1, c);

      dfs(r + 1, c);

      dfs(r, c - 1);

      dfs(r, c + 1);

    }

  }

}

Alternatively, we can iterate the grid, instead use dfs or bfs to erase islands, we use an union find data structure to keep track of how many islands we found, the union operation (with path compression) takes extra time cost O(1) and union find array takes extra space cost O(NxM). This approach doesn't modify the original grid values.

public class CountIslands {
  private static class UnionFind {
    private int[] connect;
    private int[] sz;
    private int count;
    public UnionFind(int N) {
      count = N;
      connect = new int[N];
      sz = new int[N];
      for(int i = 0; i < N; i++) {
        connect[i] = i;
        sz[i] = 0;
      }
    }
    public int getCount() {
      return count;
    }
    public int find(int p) {
      while(connect[p] != p) {
        p = connect[p];
      }
      return p;
    }
    public void union(int p, int q) {
      int root1 = find(p);
      int root2 = find(q);
      if(root1 == root2) return;
      if(sz[root1] > sz[root2]) {
        connect[root2] = root1;
        sz[root1] += sz[root2];
      } else {
        connect[root1] = root2;
        sz[root2] += sz[root1];
      }
      count--;
    }
    public void decreaseCount() {
      count--;
    }
  }
  public static int countIsland(int[][] map, UnionFind uf) {
/*
11000
11000
00100
00011
*/
    int N = map.length;//4
    int M = map[0].length;//5
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {
        if(map[i][j] == 0) uf.decreaseCount();
        else {
          if(i == 0) {
            if(j > 0 && map[0][j-1] == 1) {
              uf.union(j-1, j);
            }
          } else {
            if(j == 0 && map[i-1][0] == 1) {
              uf.union(i*M, (i-1)*M);
            } else if(j > 0) {
              if(map[i-1][j] == 1) {
                uf.union(i*M + j, (i-1)*M + j);
              }
              if(map[i][j-1] == 1) {
                uf.union(i*M + j, i*M + j - 1);
              }
            }
          }
        }
      }
    }
    return uf.getCount();
  }
  public static void main(String...args) {
    int[][] map = new int[][] {
      {1,1,0,0,0},
      {1,1,0,0,0},
      {0,0,1,0,0},
      {0,0,0,1,1}
    };
    UnionFind uf = new UnionFind(map.length * map[0].length);
    System.out.println(countIsland(map, uf));
  }
}

Time complexity O(MN), space complexity O(MN).

number permutations with restrictions

Problem

number permutations with restrictions

Given the following 6 numbers 1, 2, 2, 3, 4, 5, write a main function, print out all the permutations that satisfy the limitations.

1. number 4 can not be at the third position from left.

2. 3 and 5 can not be the neighbors.

For example 512234, 412345.

Solution

It is a permutation problem with twists. For permutation problem, backtracing strategy is to branch at each position, only print out at the last position. Here, the constraints need to be applied. 

• 3 and 5 can not be neighbors. We can modify the traceback routing by sending a flag to indicate a constraint is put by the previous position, so we have less choices for branching at current position.
• number 4 can not be at the third position from left. We can check it before printing the string.
• we have duplicate numbers, which can be removed by a Set datastructure.

import java.util.*;
public class PrintNumbers {
  private Set<String> result = new HashSet<>();
  //122345
  public void perm(String str, boolean has4Or5, String remains) {
    if(str.length() == 6) {
      if(str.charAt(2) != '4') {
        System.out.println(str);
        result.add(str);
      }
      return;
    }
 
    for(int i = 0; i < remains.length(); i++) {  //6
      char c = remains.charAt(i);  //1
      if(has4Or5 && (c == '3' || c == '5'))
        continue;
      perm(str + c, (c == '3' || c == '5'), remains.substring(0, i) + remains.substring(i + 1));
    }
  }

  public static void main(String...args) {
    PrintNumbers pn = new PrintNumbers();
    pn.perm("", false, "122345");
    for(String word : pn.result) {
      System.out.println(word);
    }
    System.out.println(pn.result.size());  //198
  }
}

We need to run the permutation, the cost is O(n!), the assumption is substring and string concatenation cost 1. The traceback need to hold the temporary strings in memory, the space cost has high bound O(n!), since java has a string pool, the cost in reality should be much lower.

Another approach is to view permutation problem as un-directed graph traversal. Each node is corresponding to a character. One node can lead to any other nodes except itself. Whenever there are constraints, we have to remove the corresponding edges. For example, remove edges between 3 and 5. The path during a dfs graph traversal for each node is the permutations. The constraints of number 4 can not be at the third position from left can be checked before printing. Duplicate can be removed with Set. The time cost and space cost is no better than the previous approach, but we listed here in order to give an alternative solution to make sure the answer is correct.

import java.util.*;
public class PrintNumbers {
  private Set<String> result2 = new HashSet<>();
  private Set<Integer> visited = new HashSet<>();

  private void graphTraversal() {
    char[] chars = "122345".toCharArray();
    int N = chars.length;
    boolean[][] connected = new boolean[N][N];
    //all connected
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j) {
          connected[i][j] = true;
        }
      }
    }
    //remove 3-5 edge
    connected[3][5] = false;
    connected[5][3] = false;
    for(int i = 0; i < N; i++) {
      visited = new HashSet<>();
      dfs(connected, i, "122345".substring(i, i+1));
    }
  }

  private void dfs(boolean[][] connected, int w, String path) {
    visited.add(w);
    if(path.length() == 6 && path.charAt(2) != '4') {
      result2.add(path);
    }
    for(int v = 0; v < connected[w].length; v++) {
      if(connected[w][v] && !visited.contains(v)) {
        dfs(connected, v, path + "122345".substring(v, v+1));
        visited.remove(v);
      }
    }
  }

  public static void main(String...args) {
    PrintNumbers pn = new PrintNumbers();
    pn.graphTraversal();
    for(String word : pn.result2) {
      System.out.println(word);
    }
    System.out.println(pn.result2.size());  //198
  }
}

Time cost O(n!), space cost O(n!) but because of java string pool, this is an over estimate.

Math

The number 198 is calculated this way:

a1 a2 a3 a4 a5 a6

3 constraints:

1. a5 can not be at position 3.
2. a4 and a6 can not be put together.
3. a2 = a3.

The possible states without any constraint: 6!

reason: there are 6 choices for position 1, then 5 choices for position 2, then 4...

Apply constraint 1, a5 can not be at position 3.

I(total) = I(a5 is at position 3) + I(a5 is not at position 3)

I(total) = 6!

I(a5 is at position 3) = 5! 

reason, a5 picked position 3, the rest of the 5 number chose 5 positions. The choices are 5!

As a result, after apply constraint 1, the total number of states that a5 can not be at position 3 is:

I(a5 is not at position 3) = 6! - 5! = 600.

Now additionally Apply constraint 2, a4 and a6 can not be put together.

We need to calculate number of states for (a5 is not at position 3) && (a4 a6 are not together).

I(a5 is not at position 3) = I(a5 is not at position 3 && a4 a6 are together) + I(a5 is not at position 3 && a4 a6 are not together)

I(a5 is not at position 3 && a4 a6 are together) is calculated this way:

We combine a4 a6 into one unit a46. Now the 6 elements permutation become 5 elements permutation. When we choose 5 of the possible start positions for combined element a46, there are 2 cases: 

1. the start position of a46 is 2 or 3
2. the start position of a46 is not 2 or 3

I(a5 is not at position 3 && a4 a6 are together && the start position of a46 is 2 or 3) = 2 x 2 x 4! 

reason: a4 and a6 are interchangeable, so we multiply 2, a45 can choose position 2 or 3, so we multiply another 2, finally, the since a4 or a6 hold the position 3, the rest of the 4 elements can chose any of the 4 positions left without any constraint, so we multiply 4!.

I(a5 is not at position 3 && a4 a6 are together && the start position of a46 is not 2 or 3) = 2 x 3 x 3 x 3!

reason: a4 and a6 are interchangeable, so we multiply 2, a45 can choose position 1, 4, 5, so we multiply 3. For the rest of the 4 elements choose the 4 positions left, a5 can not choose position 3, so it has 3 choices, so we multiply 3, for the rest of the 3 elements choose the rest of 3 positions left, there is no constraint, so we multiply 3!.

As a result, 

I(a5 is not at position 3 && a4 a6 are not together) = I(a5 is not at position 3) - I(a5 is not at position 3 && a4 a6 are together) = 600 - (2x2x4! + 2x3x3x3!) = 396

Finally, we apply the constraint 3, a2 = a3.

I(a5 is not at position 3 && a4 a6 are not together && a2 = a3) = 396/2! = 198

reason: n of the elements are interchangeable,  the n elements suppose to create n! different states, but now they only created 1 state, so we divide n! when apply the constraint.

Children Processes

Problem

A computer process has a process Id (PID) and a parent process Id (PPID). Only the root process has PPID 0. We use 2 arrays to match the PID to PPID:

PID         {6,      2,      8,       5,        3,      7,     1,   9,   4,  10}     

PPID       {9,      7,      4,       7,       10,     0,     2,   0,   9,    9}

Given a PID, find all process rooted at this process. 

For example, given PID 7, the output should be 7, 5, 2, 1

            7

         /      \

       5       2

               /  

             1

Solution

We can build an adjacency set from the PID and PPID arrays, then start at the given node PID, do a dfs or bfs traversal in order to find all the PIDs rooted at that node.

Build the adjacency list costs O(N), bfs or dfs cost O(V + E) is also O(N). We need extra space O(V+E) ~ O(N) to store the adjacency list and marked set.

import java.util.*;
class ChildrenProcess {
  public Map<Integer, Set<Integer>> buildDigraph(int[] pids, int[] ppids) {
    Map<Integer, Set<Integer>> adjs = new HashMap<>();
    for(int i = 0; i < pids.length; i++) {
      int parent = ppids[i];  //7
      int child = pids[i];     //5
      Set<Integer> adj = adjs.get(parent);
      if(adj == null) {
        adj = new HashSet<>();
        adj.add(child);   //{6}
        adjs.put(parent, adj);  //{9, {6}}, {7, {2, 5}},...
      } else {
        adj.add(child);
      }
    }
    return adjs;
  }
  public Set<Integer> getChildren(int[] pids, int[] ppids, int root) {
    return bfs(buildDigraph(pids, ppids), root);
  }
  public static void main(String...args) {
    ChildrenProcess cp = new ChildrenProcess();
    int[] pids = new int[] {6,      2,      8,       5,        3,      7,     1,   9,   4,  10};
    int[] ppids = new int[] {9,      7,      4,       7,       10,     0,     2,   0,   9,    9};
    Set<Integer> childrens = cp.bfs(cp.buildDigraph(pids, ppids), 7);
    childrens.stream().forEach(System.out::println);
  }

  //7
  private Set<Integer> bfs(Map<Integer, Set<Integer>> adjs, int s) {
    Set<Integer> marked = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    marked.add(s);
    queue.add(s);
    while(!queue.isEmpty()) {
      Integer v = queue.poll();
      if(adjs.get(v) == null)
        continue;
      for(int w : adjs.get(v)) {
        if(!marked.contains(w)) {
          marked.add(w);
          queue.add(w);
        }
      }
    }
    return marked;
  }
}

Time cost O(N) and space cost O(N).