LeetCode-Master Study Plan

Instead of using a separate visited array, you can optimize space by 'drowning' the island. When a cell with value 1 is encountered, perform a DFS and set the value of each visited cell in the grid to 0. This prevents the same island from being counted multiple times and eliminates the need for an auxiliary boolean array.

// DFS Optimization: Drowning the island
public int maxAreaOfIsland(int[][] grid) {
    int res = 0;
    for(int i = 0;i < grid.length;i++){
        for(int j = 0; j < grid[0].length;j++){
            if(grid[i][j] == 1){
                res = Math.max(res, dfs(grid, i, j));
            }
        }
    }
    return res;
}

public int dfs(int[][] grid, int i, int j){
    if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
    grid[i][j] = 0; // Drown the land
    return 1 + dfs(grid, i - 1, j) + 
               dfs(grid, i + 1, j) + 
               dfs(grid, i, j + 1) + 
               dfs(grid, i, j - 1);
}

To solve a Sudoku puzzle, use a 2D backtracking approach (also referred to as 2D recursion). Unlike standard 1D backtracking (like permutations or combinations), this method involves nested loops to traverse both rows and columns to find empty cells ('.') and then recursively attempting to place digits '1'-'9' in those cells.

Core Logic: The Backtracking Three-Step

1. Recursive Function and Parameters: The function should return a bool type. This allows the algorithm to immediately stop and return true once a valid complete solution is found at a leaf node of the recursion tree.
   • Signature: bool backtracking(vector<vector<char>>& board)
2. Termination Condition: This specific implementation does not use an explicit termination condition. Instead, it relies on the fact that as numbers are filled, the board eventually becomes full. If a cell is processed and all 9 digits fail the validity check, the function returns false to trigger backtracking.
3. Single-Layer Search Logic:
   • Iterate through rows using a for loop.
   • Iterate through columns using a for loop.
   • If a cell board[i][j] is not '.', skip it.
   • If it is '.', iterate through characters '1' to '9'.
   • Check if the digit is valid using isValid().
   • If valid, place the digit, recurse, and if the recursion returns true, propagate true upwards. If not, reset the cell to '.' (backtrack).

bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (board[i][j] == '.') {
                for (char k = '1'; k <= '9'; k++) {
                    if (isValid(i, j, k, board)) {
                        board[i][j] = k;
                        if (backtracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

To find the maximum area of an island in a binary matrix, you can use Depth First Search (DFS). The problem requires counting connected 1s (land) in four directions (horizontal and vertical).

There are two common patterns for implementing DFS in this context:

1. Pattern 1: DFS handles neighbors. The main loop identifies a land cell, increments the count to 1, and then calls DFS to process all subsequent adjacent land cells.
2. Pattern 2: DFS handles the current node. The main loop identifies a land cell but sets the initial count to 0. The DFS function is responsible for marking the current node as visited, incrementing the count, and then exploring neighbors.

// Pattern 1: DFS handles neighbors
// Main loop: count = 1; dfs(grid, visited, i, j);
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
        if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
            visited[nextx][nexty] = true;
            count++;
            dfs(grid, visited, nextx, nexty);
        }
    }
}

// Pattern 2: DFS handles current node
// Main loop: count = 0; dfs(grid, visited, i, j);
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    if (visited[x][y] || grid[x][y] == 0) return;
    visited[x][y] = true;
    count++;
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
        dfs(grid, visited, nextx, nexty);
    }
}

To find the minimum number of cuts required to partition a string s such that every substring is a palindrome, use a two-step Dynamic Programming approach.

1. Precompute Palindromes

Create a 2D boolean array isPalindromic[i][j] where isPalindromic[i][j] is true if the substring from index i to j is a palindrome.

• Base Case: If s[i] == s[j] and the distance between i and j is $\le 1$, it is a palindrome.
• Recursive Step: If s[i] == s[j] and isPalindromic[i+1][j-1] is true, it is a palindrome.

2. Compute Minimum Cuts

Use a 1D DP array dp[i] representing the minimum cuts for the substring s[0...i].

• Initialization: dp[0] = 0. For $i > 0$, initialize dp[i] to its maximum possible value (either i or INT_MAX).
• Transition: For each i from $1$ to $n-1$:
  • If isPalindromic[0][i] is true, dp[i] = 0.
  • Otherwise, iterate through all possible split points j from $0$ to $i-1$. If isPalindromic[j+1][i] is true, update dp[i] = min(dp[i], dp[j] + 1).

Complexity:

• Time: $O(n^2)$
• Space: $O(n^2)$ to store the isPalindromic table.

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPalindromic(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {
                    isPalindromic[i][j] = true;
                }
            }
        }

        vector<int> dp(n);
        for (int i = 0; i < n; i++) dp[i] = i;

        for (int i = 1; i < n; i++) {
            if (isPalindromic[0][i]) {
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (isPalindromic[j + 1][i]) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};