2D_Array.md

2D Array

• Basic operations
  • Traverse
  • Search
    • BFS
    • DFS
• Strategies
• Common Topics

Basic operations

Traverse

• By-row traversal

  void traverseByRow(int[][] grid) {
     for (int i = 0; i < grid.length; i++) {
          for (int j = 0; j < grid[0].length; i++) {
              visit(grid[i][j]);
          }
      }
  }
  

Search

• BFS: See here
• DFS: See here

Strategies

• Strategy 1
  • Idea
    • When you don't know where is the starting point to start a search algorithm, just traverse by rows. If the current cell satisfy the critiera, just start BFS or DFS algorithm.
  • Code example

    void traverseByRow(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; i++) {
                if (satisfy the criteria) {
                    BFS() or DFS()
                }
            }
        }
    }
    

  • Question examples
    • Number of Islands
    • Word Search

Common topics

back to Problem_Categories

• Path
  • Shortest Path in a Grid with Obstacles Elimination
  • Find All Paths in Grid
• Search
  • Word Search
• Traversal
  • Spiral Traversal
  • Generate 2D Array by Spiral Traversal
• Manipulation
  • Rotate 2D Array
  • Generate 2D Array by Spiral Traversal
• Calculation
  • Sum
    • Calculate Range Sum in 2D Array
• Island
  • Number of Islands
  • Get Size of Largest Island
  • 1254 Number of Closed Islands
  • 1905 Count Sub Islands
  • 694 Number of Distinct Islands
  • 695 Max Area of Island
• Other
  • Number of Ways of Cutting a Pizza
  • N-Queens
  • Maximal Square

back to Problem_Categories