Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

leetcodeday22

🏝️ Daily Leetcode Challenge Day 22: 827. Making A Large Island – Biến Đổi 1 Ô Nhỏ, Đảo Cả Thế Giới! 🌊

Xin chào các bạn yêu quý của Learning AI With Losers! Mình là Loser1 đây!

Ngày mùng 3 Tết Ất Tỵ 2025, chúng ta lại cùng nhau chinh phục một bài toán Hard cực kỳ thú vị – Making A Large Island! Hãy tưởng tượng bạn là một “kiến trúc sư đảo” với khả năng biến nước thành đất! Cùng bắt đầu hành trình khám phá nhé! 🚀

827. Making A Large Island

Hard
Đã giải

Bạn được cung cấp một ma trận nhị phân grid có kích thước n x n. Bạn được phép thay đổi tối đa một giá trị từ 0 thành 1.

Trả về kích thước của hòn đảo lớn nhất trong grid sau khi thực hiện thao tác này.

Một “hòn đảo” là một nhóm các số 1 liên kết với nhau theo 4 hướng (trên, dưới, trái, phải).

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Thay đổi một số 0 thành 1 và kết nối hai số 1, sau đó ta sẽ có một hòn đảo với diện tích = 3.

Example 2:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Thay đổi số 0 thành 1 và làm cho hòn đảo lớn hơn, chỉ còn một hòn đảo với diện tích = 4.

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Không thể thay đổi bất kỳ số 0 nào thành 1, chỉ có một hòn đảo với diện tích = 4.

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] chỉ có giá trị là 0 hoặc 1.

📝 Problem Description

Bạn được cho một ma trận nhị phân n x n (grid). Nhiệm vụ của bạn là:

  • Được phép biến đổi tối đa một ô có giá trị 0 thành 1
  • Tìm kích thước lớn nhất của hòn đảo sau khi biến đổi
  • Một hòn đảo được định nghĩa là tập hợp các ô số 1 kề nhau theo 4 hướng (trên, dưới, trái, phải)

🔥 First Thoughts & Intuition

Khi nhìn vào bài toán này, chúng ta có thể thấy một số pattern thú vị:

Trường hợp 1: Các đảo riêng lẻ

🌳🌳🌊
🌊🌊🌳
🌳🌳🌊

Nhận xét: Hai đảo riêng biệt đang chờ được kết nối! Chúng ta cần tìm điểm kết nối tối ưu để tạo ra đảo lớn nhất.

Trường hợp 2: Đảo đã kết nối một phần

🌳🌳🌊
🌳🌊🌳
🌊🌊🌳

Nhận xét: Một đảo lớn và một đảo nhỏ – cần một cây cầu kết nối thông minh!

💡 Approach

1. Island Identification System 🏷️

Trước tiên, chúng ta cần một hệ thống để nhận diện và đánh dấu các đảo riêng biệt:

Bước 1: Đánh dấu các đảo
Before: Ma trận ban đầu
🌳🌳🌊
🌊🌊🌳
🌳🌳🌊

After: Sau khi đánh dấu
2️⃣2️⃣🌊
🌊🌊3️⃣
4️⃣4️⃣🌊

Mỗi đảo được đánh dấu bằng một ID riêng (2, 3, 4…) để dễ dàng theo dõi và tính toán.

2. Size Tracking System 📊

Chúng ta cần một hệ thống theo dõi kích thước của từng đảo:

Island Registry 📋:

  • Island #2: 2 ô đất (màu xanh lá)
  • Island #3: 1 ô đất (màu xanh dương)
  • Island #4: 2 ô đất (màu vàng)

3. The Magic Transform ✨

Khi xem xét một ô nước (0), chúng ta cần:

Direction Check:
⬆️ Phía Trên: Kiểm tra Island ID
⬅️ Bên Trái: Kiểm tra Island ID
➡️ Bên Phải: Kiểm tra Island ID
⬇️ Phía Dưới: Kiểm tra Island ID

Size Calculation:
Kích thước mới = 1 (ô được biến đổi) + Tổng kích thước các đảo xung quanh

🚀 Implementation

C++
class Solution { 
public:
    // Possible directions for movement: right, left, down, and up
    vector<pair<int,int>> direct = {{0,1},{0,-1},{1,0},{-1,0}};

    // Function to check if a given position (i, j) is within grid bounds
    bool is_valid(int i, int j, vector<vector<int>>& grid) {
        return (i >= 0) && (j >= 0) && (i < grid.size()) && (j < grid[0].size());
    }

    // Depth-First Search (DFS) to mark and count the size of an island
    void dfs(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& visited, int &curk, int &cnt) {
        visited[i][j] = true;  // Mark the cell as visited
        grid[i][j] = curk;     // Assign a unique island identifier
        cnt += 1;              // Increase the island size counter

        // Explore all four possible directions
        for(auto it : direct) {
            int newdx = i + it.first;
            int newdy = j + it.second;

            // If the new position is valid, unvisited, and part of an island (grid value = 1), continue DFS
            if (is_valid(newdx, newdy, grid) && !visited[newdx][newdy] && grid[newdx][newdy] == 1) {
                dfs(newdx, newdy, grid, visited, curk, cnt);
            }
        }
    }

    int largestIsland(vector<vector<int>>& grid) {
        int curk = 2;  // Unique identifier for each island, starting from 2 (since 1 represents land)
        int cnt_max = 0;  // Variable to store the size of the largest island
        map<int, int> marked_cnt_each_island; // Stores the size of each uniquely marked island

        // Create a visited grid initialized to false
        vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), false));

        // Step 1: Identify and mark all islands with unique identifiers using DFS
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                int cnt = 0;  // Counter for the current island's size

                // If the current cell is land (1) and has not been visited, start DFS
                if (!visited[i][j] && grid[i][j] == 1) {
                    dfs(i, j, grid, visited, curk, cnt);
                    marked_cnt_each_island[curk] = cnt; // Store the size of this island
                    cnt_max = max(cnt_max, cnt); // Update the max island size
                    curk++; // Increment island identifier for the next island
                }
            }
        }

        // Edge case 1: If the entire grid is an island (no zeros), return its size
        if (cnt_max == grid.size() * grid[0].size()) {
            return cnt_max;
        }
        // Edge case 2: If there are no islands, flipping one cell to land gives size 1
        else if (cnt_max == 0) {
            return 1;
        }

        // Step 2: Try converting each water cell (0) into land (1) to form a larger island
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0) {
                    int cnt = 1; // Start with size 1 (this flipped cell)
                    set<int> unique_islands; // To avoid counting the same island twice

                    // Check all four directions to find adjacent islands
                    for (auto it : direct) {
                        int newdx = i + it.first;
                        int newdy = j + it.second;

                        // If valid, add the island identifier to the set
                        if (is_valid(newdx, newdy, grid)) {
                            unique_islands.insert(grid[newdx][newdy]);
                        }
                    }

                    // Sum the sizes of unique neighboring islands
                    for (auto it : unique_islands) {
                        cnt += marked_cnt_each_island[it];
                    }

                    // Update the maximum possible island size
                    cnt_max = max(cnt, cnt_max);
                }
            }
        }

        return cnt_max; // Return the largest possible island size
    }
};

🎯 Step-by-Step Example

Hãy phân tích một ví dụ cụ thể:

Input Grid:
🌳🌳🌊
🌳🌊🌳
🌊🌊🌳

Step 1: Label Islands
2️⃣2️⃣🌊
2️⃣🌊3️⃣
🌊🌊3️⃣

Step 2: Size Tracking

  • Island #2: 3 ô
  • Island #3: 2 ô

Step 3: Find Best Transform
Point (1,1) kết nối cả hai đảo:
2️⃣2️⃣🌊
2️⃣✨3️⃣
🌊🌊3️⃣

Final Result: 6 ô (3 + 2 + 1)

🎨 Visual Guide to Key Steps

Step 1: Mark Islands
⬛⬛⬜ Islands được mark với các ID khác nhau để dễ track!
⬛⬜🟦
⬜🟦🟦

Step 2: Find Bridges
⬛⬛❓ Các điểm có thể transform được đánh dấu bằng ❓
⬛❓🟦
❓🟦🟦

Step 3: Calculate
⬛⬛✨ Chọn điểm transform tối ưu nhất để maximize size!
⬛❓🟦
❓🟦🟦

💎 Key Insights & Tips

1. Pattern Recognition 🔍

Good Transform Points:
⬛❓🟦 → High impact! Connects many islands!
❓⬛🟦
🟦🟦⬛

Bad Transform Points:
⬛⬛❓ → Low impact! Only connects few cells!
⬛⬛⬛
❓⬛⬛

2. Optimization Tricks ⚡

Early Exit Cases:
🌳🌳🌳
🌳🌳🌳 → All land? Return n*n, no need to check!
🌳🌳🌳

🌊🌊🌊
🌊🌊🌊 → All water? Return 1, just one cell!
🌊🌊🌊

📊 Complexity Analysis

Time Complexity: O(N²)

  • N² cells → Each cell → 4 directions
  • ⬛⬛⬛ ⭐⬛⬛ ↑
  • ⬛⬛⬛ ⬛⬛⬛ ←⭐→
  • ⬛⬛⬛ ⬛⬛⬛ ↓

Space Complexity: O(N²)

  • 📝 Visited Array: N²
  • 🗺️ Grid Storage: N²
  • 📊 Island Sizes: O(K) where K < N²

🎉 Conclusion

Bài toán này là một ví dụ tuyệt vời về việc kết hợp:

  • DFS để explore và mark đảo
  • Pattern recognition để optimize
  • Greedy approach để chọn điểm transform
  • Graph theory để kết nối components

Chúc mừng năm mới 2025! Hãy follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 🎊

CODE EDITOR

#leetcode #dailycoding #graphs #dfs #LearningWithLosers #newyear2025 #tetholidaycoding

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Cdl scholarship logi transports fast & reliable heavy equipment transport & transport services.