2D Array Problems

Valid Sudoku

• class Solution {
      public boolean isValidSudoku(char[][] board) {
          return isValidRows(board) && isValidColumns(board) && isValidCells(board);
      }
  
      private boolean isValidRows(char[][] board) {
          for (int i = 0; i < board.length; i++) {
              int[] seen = new int[9];
              for (int j = 0; j < board.length; j++) {
                  char c = board[i][j];
                  if (c == '.')
                      continue;
                  if (seen[c - '1'] == 0)
                      seen[c - '1'] = 1;
                  else
                      return false;
              }
          }
  
          return true;
      }
  
      private boolean isValidColumns(char[][] board) {
          for (int j = 0; j < board.length; j++) {
              int[] seen = new int[9];
              for (int i = 0; i < board.length; i++) {
                  char c = board[i][j];
                  if (c == '.')
                      continue;
                  if (seen[c - '1'] == 0)
                      seen[c - '1'] = 1;
                  else
                      return false;
              }
          }
  
          return true;
      }
  
      private boolean isValidCells(char[][] board) {
          for (int i = 0; i < board.length; i += 3)
              for (int j = 0; j < board.length; j+= 3) {
                  if (!isValidCell(board, i, j))
                      return false;
              }
  
          return true;
      }
  
      private boolean isValidCell(char[][] board, int a, int b) {
          int[] seen = new int[9];
          for (int i = a; i < a + 3; i++)
              for (int j = b; j < b + 3; j++) {
                  char c = board[i][j];
                  if (c == '.')
                      continue;
                  if (seen[c - '1'] == 0)
                      seen[c - '1'] = 1;
                  else
                      return false;
              }
  
          return true;
      }
  }

Rotate Image

• class Solution {
      public void rotate(int[][] matrix) {
          int n = matrix.length;
          // swap matrix by diagonal
          for (int i = 0; i < n - 1; i++)
              for (int j = 0; j < n - i - 1; j++) {
                  int tmp = matrix[i][j];
                  matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
                  matrix[n - 1 - j][n - 1 - i] = tmp;
              }
          // swap matrix by horizontal centerline
          for (int i = 0; i < n / 2; i++)
              for (int j = 0; j < n; j++) {
                  int tmp = matrix[i][j];
                  matrix[i][j] = matrix[n - 1 - i][j];
                  matrix[n - 1 - i][j] = tmp;
              }
      }
  }

Spiral Matrix

• class Solution {
      public List<Integer> spiralOrder(int[][] matrix) {
          List<Integer> result = new ArrayList<>();
          int a1 = 0, b1 = 0, a2 = matrix.length - 1, b2 = matrix[0].length - 1;
          while (a1 <= a2 && b1 <= b2) {
              addCircle(matrix, a1, b1, a2, b2, result);
              a1++;
              b1++;
              a2--;
              b2--;
          }
  
          return result;
      }
  
      private void addCircle(int[][] matrix, int a1, int b1, int a2, int b2,
                              List<Integer> result) {
          int i = a1, j = b1;
  
          // a horizontal line
          if (a1 == a2) {
              while (j <= b2)
                  result.add(matrix[i][j++]);
              return;
          }
  
          // a vertical line
          if (b1 == b2) {
              while (i <= a2)
                  result.add(matrix[i++][j]);
              return;
          }
  
          // a circle
          while (j < b2)
              result.add(matrix[i][j++]);
          while (i < a2)
              result.add(matrix[i++][j]);
          while (j > b1)
              result.add(matrix[i][j--]);
          while (i > a1)
              result.add(matrix[i--][j]);
          return;
      }
  }

Spiral Matrix II

• class Solution {
      public int[][] generateMatrix(int n) {
          int[][] matrix = new int[n][n];
          spiral(matrix, 1, 0, n - 1);
          return matrix;
      }
  
      private void spiral(int[][] matrix, int n, int r1, int r2) {
          if (r1 > r2)
              ;
          else if (r1 == r2)
              matrix[r1][r1] = n;
          else {
              for (int i = r1; i <= r2; i++)
                  matrix[r1][i] = n++;
              for (int i = r1 + 1; i < r2; i++)
                  matrix[i][r2] = n++;
              for (int i = r2; i >= r1; i--)
                  matrix[r2][i] = n++;
              for (int i = r2 - 1; i > r1; i--)
                  matrix[i][r1] = n++;
              spiral(matrix, n, r1 + 1, r2 - 1);
          }
      }
  }

Set Matrix Zeroes

• class Solution {
      public void setZeroes(int[][] matrix) {
          Set<Integer> rows = new HashSet<>();
          Set<Integer> cols = new HashSet<>();
  
          for (int i = 0; i < matrix.length; i++)
              for (int j = 0;j < matrix[0].length; j++) {
                  if (matrix[i][j] == 0) {
                      rows.add(i);
                      cols.add(j);
                  }
              }
  
          for (Integer r : rows)
              zeroRow(matrix, r);
          for (Integer c : cols)
              zeroCol(matrix, c);
      }
  
      private void zeroRow(int[][] matrix, int a) {
          for (int j = 0; j < matrix[0].length; j++)
              matrix[a][j] = 0;
      }
  
      private void zeroCol(int[][] matrix, int b) {
          for (int i = 0; i < matrix.length; i++)
              matrix[i][b] = 0;
      }
  }

Game of Life

• class Solution {
      public void gameOfLife(int[][] board) {
          for (int i = 0; i < board.length; i++)
              for (int j = 0; j < board[0].length; j++)
                  updateCell(board, i, j);
  
          updateBoard(board);
      }
  
      private void updateBoard(int[][] board) {
          for (int i = 0; i < board.length; i++)
              for (int j = 0; j < board[0].length; j++) {
                  int state = board[i][j];
                  if (state == 1 || state == 2)
                      board[i][j] = 1;
                  else
                      board[i][j] = 0;
              }
      }
  
      private void updateCell(int[][] board, int r, int c) {
          int live = 0, die = 0, state = board[r][c];
  
          int i = r - 1, j = c - 1;
          for (; j <= c; j++) {
              if (!isOutOfBound(board, i, j)) {
                  int s = board[i][j];
                  if (s == 1 || s == -2)
                      live++;
                  else
                      die++;
              }
          }
          for (; i <= r; i++) {
              if (!isOutOfBound(board, i, j)) {
                  int s = board[i][j];
                  if (s == 1 || s == -2)
                      live++;
                  else
                      die++;
              }
          }
          for (; j >= c; j--) {
              if (!isOutOfBound(board, i, j)) {
                  int s = board[i][j];
                  if (s == 1 || s == -2)
                      live++;
                  else
                      die++;
              }
          }
          for (; i >= r; i--) {
              if (!isOutOfBound(board, i, j)) {
                  int s = board[i][j];
                  if (s == 1 || s == -2)
                      live++;
                  else
                      die++;
              }
          }
  
          // -2 means 1 to 0, 2 means 0 to 1
          if (state == 1 && (live < 2 || live > 3))
              board[r][c] = -2;
  
          if (state == 0 && live == 3)
              board[r][c] = 2;
      }
  
      private boolean isOutOfBound(int[][] board, int i, int j) {
          return i < 0 || i >= board.length || j < 0 || j >= board[0].length;
      }
  }

Spiral Matrix III

• class Solution {
      private static int n = 0;
  
      public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
          int circles = Math.max(Math.max(Math.max(rStart + 1, cStart + 1), rows - rStart), cols - cStart);
          int[][] m = new int[rows * cols][2];
          for (int c = 0; c < circles; c++) {
              spiral(m, rStart - c, cStart - c, rStart + c, cStart + c, rows, cols);
          }
          return m;
      }
  
      private void spiral(int[][] m, int r1, int c1, int r2, int c2, int rows, int cols) {
          if (r1 == r2 && c1 == c2) {
              m[n++] = new int[] {r1, c1};
          }
          else {
              for (int i = r1 + 1; i <= r2; i++)
                  if (i >= 0 && i < rows && c2 >= 0 && c2 < cols)
                      m[n++] = new int[] {i, c2};
              for (int i = c2 - 1; i >= c1; i--)
                  if (r2 >= 0 && r2 < rows && i >= 0 && i < cols)
                      m[n++] = new int[] {r2, i};
              for (int i = r2 - 1; i >= r1; i--)
                  if (i >= 0 && i < rows && c1 >= 0 && c1 < cols)
                      m[n++] = new int[] {i, c1};
              for (int i = c1 + 1; i <= c2; i++)
                  if (r1 >= 0 && r1 < rows && i >= 0 && i < cols)
                      m[n++] = new int[] {r1, i};
          }
      }
  }

Spiral Matrix IV

• class Solution {
      public int[][] spiralMatrix(int m, int n, ListNode head) {
          int[][] matrix = new int[m][];
          for (int i = 0; i < m; i++) {
              matrix[i] = new int [n];
              Arrays.fill(matrix[i], -1);
          }
          int a = 0, b = 0, p = m - 1, q = n - 1;
          while (head != null) {
              if (a == p) {
                  for (; head != null && b <= q; b++) {
                      matrix[a][b] = head.val;
                      head = head.next;
                  }
              }
              else if (b == q) {
                  for (; head != null && a <= p; a++) {
                      matrix[a][b] = head.val;
                      head = head.next;
                  }
              }
              else {
                  int i = a, j = b;
                  for (; head != null && b < q; b++) {
                      matrix[a][b] = head.val;
                      head = head.next;
                  }
                  for (; head != null && a < p; a++) {
                      matrix[a][b] = head.val;
                      head = head.next;
                  }
                  for (; head != null && b > j; b--) {
                      matrix[a][b] = head.val;
                      head = head.next;
                  }
                  for (; head != null && a > i; a--) {
                      matrix[a][b] = head.val;
                      head = head.next;
                  }
                  a++;
                  b++;
                  p--;
                  q--;
              }
          }
          return matrix;
      }
  }