matrix_patterns.cpp

/*
Matrix & 2D Array Patterns
Mathematical Foundation: Row-major access O(1), traversal patterns
Spiral: 4-direction state machine, Rotate: transpose + reverse
Search: Binary search on sorted matrix O(log mn)
Applications: Image processing, pathfinding, dynamic programming
*/

#include <bits/stdc++.h>
using namespace std;

// Spiral Matrix
// LeetCode: 54. Spiral Matrix
// https://leetcode.com/problems/spiral-matrix/
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    
    while (top <= bottom && left <= right) {
        for (int col = left; col <= right; col++) res.push_back(matrix[top][col]);
        top++;
        for (int row = top; row <= bottom; row++) res.push_back(matrix[row][right]);
        right--;
        if (top <= bottom) {
            for (int col = right; col >= left; col--) res.push_back(matrix[bottom][col]);
            bottom--;
        }
        if (left <= right) {
            for (int row = bottom; row >= top; row--) res.push_back(matrix[row][left]);
            left++;
        }
    }
    return res;
}

// Rotate Image 90 degrees
// LeetCode: 48. Rotate Image
// https://leetcode.com/problems/rotate-image/
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) swap(matrix[i][j], matrix[j][i]);
    }
    // Reverse each row
    for (auto& row : matrix) reverse(row.begin(), row.end());
}

// Set Matrix Zeroes
// LeetCode: 73. Set Matrix Zeroes
// https://leetcode.com/problems/set-matrix-zeroes/
void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRow = false, firstCol = false;
    
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        }
    }
    
    if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

// Search 2D Matrix
// LeetCode: 74. Search a 2D Matrix
// https://leetcode.com/problems/search-a-2d-matrix/
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int l = 0, r = m * n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        if (val < target) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}

// Search 2D Matrix II (Sorted rows and columns)
// LeetCode: 240. Search a 2D Matrix II
// https://leetcode.com/problems/search-a-2d-matrix-ii/
bool searchMatrix2(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int r = 0, c = n - 1;
    while (r < m && c >= 0) {
        if (matrix[r][c] == target) return true;
        if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
}

// Word Search II
// LeetCode: 212. Word Search II
// https://leetcode.com/problems/word-search-ii/
struct TrieNode {
    TrieNode* children[26] = {};
    string word;
};

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    TrieNode* root = new TrieNode();
    for (string& w : words) {
        TrieNode* node = root;
        for (char c : w) {
            if (!node->children[c - 'a']) node->children[c - 'a'] = new TrieNode();
            node = node->children[c - 'a'];
        }
        node->word = w;
    }
    
    vector<string> res;
    int m = board.size(), n = board[0].size();
    
    function<void(int, int, TrieNode*)> dfs = [&](int r, int c, TrieNode* node) {
        if (r < 0 || r >= m || c < 0 || c >= n || !node->children[board[r][c] - 'a']) return;
        
        char ch = board[r][c];
        node = node->children[ch - 'a'];
        if (!node->word.empty()) {
            res.push_back(node->word);
            node->word.clear(); // Avoid duplicates
        }
        
        board[r][c] = '#';
        dfs(r+1, c, node); dfs(r-1, c, node); dfs(r, c+1, node); dfs(r, c-1, node);
        board[r][c] = ch;
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            dfs(r, c, root);
        }
    }
    return res;
}

// Number of Islands
// LeetCode: 200. Number of Islands
// https://leetcode.com/problems/number-of-islands/
int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size(), count = 0;
    
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
        grid[r][c] = '0';
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                dfs(r, c);
                count++;
            }
        }
    }
    return count;
}

// Max Area of Island
// LeetCode: 695. Max Area of Island
// https://leetcode.com/problems/max-area-of-island/
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size(), maxArea = 0;
    
    function<int(int, int)> dfs = [&](int r, int c) -> int {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) return 0;
        grid[r][c] = 0;
        return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1);
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) maxArea = max(maxArea, dfs(r, c));
        }
    }
    return maxArea;
}

// Surrounded Regions
// LeetCode: 130. Surrounded Regions
// https://leetcode.com/problems/surrounded-regions/
void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();
    
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
        board[r][c] = '#';
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
    };
    
    // Mark border-connected 'O's
    for (int r = 0; r < m; r++) {
        dfs(r, 0); dfs(r, n - 1);
    }
    for (int c = 0; c < n; c++) {
        dfs(0, c); dfs(m - 1, c);
    }
    
    // Flip remaining 'O's to 'X' and restore '#' to 'O'
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'O') board[r][c] = 'X';
            else if (board[r][c] == '#') board[r][c] = 'O';
        }
    }
}

// Pacific Atlantic Water Flow
// LeetCode: 417. Pacific Atlantic Water Flow
// https://leetcode.com/problems/pacific-atlantic-water-flow/
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<bool>> pacific(m, vector<bool>(n)), atlantic(m, vector<bool>(n));
    
    function<void(int, int, vector<vector<bool>>&)> dfs = [&](int r, int c, vector<vector<bool>>& ocean) {
        ocean[r][c] = true;
        for (auto [dr, dc] : vector<pair<int,int>>{{0,1},{1,0},{0,-1},{-1,0}}) {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && 
                !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, ocean);
            }
        }
    };
    
    for (int r = 0; r < m; r++) {
        dfs(r, 0, pacific);
        dfs(r, n - 1, atlantic);
    }
    for (int c = 0; c < n; c++) {
        dfs(0, c, pacific);
        dfs(m - 1, c, atlantic);
    }
    
    vector<vector<int>> res;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (pacific[r][c] && atlantic[r][c]) res.push_back({r, c});
        }
    }
    return res;
}

// Game of Life
// LeetCode: 289. Game of Life
// https://leetcode.com/problems/game-of-life/
void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    
    auto countLive = [&](int r, int c) {
        int cnt = 0;
        for (int i = max(0, r-1); i <= min(m-1, r+1); i++) {
            for (int j = max(0, c-1); j <= min(n-1, c+1); j++) {
                if ((i != r || j != c) && (board[i][j] & 1)) cnt++;
            }
        }
        return cnt;
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int live = countLive(r, c);
            if (board[r][c] && (live == 2 || live == 3)) board[r][c] |= 2;
            else if (!board[r][c] && live == 3) board[r][c] |= 2;
        }
    }
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) board[r][c] >>= 1;
    }
}