💡 Greedy Expansion with DP 🚀
💡 Using Greedy Only [Gives TLE]
My approach was that whenever we encounter a 0 while checking for the largest area then we consider it as a 1 and continue searc
# 💡 Using Greedy Only [Gives TLE]

- My approach was that whenever we encounter a `0` while checking for the largest area then we consider it as a `1` and continue searching further.
- This greedy approach would go through all possible checks and eventually return me the correct position where `1` was supposed to be.

---

# 📊 Complexity
- **🕰️ Time Complexity:** This has a worst case Time Complexity of $$O(n^4)$$
- **📦 Space Complexity:** $$O(n^2)$$

```cpp []
class Solution {
public:
    int n;
    vector<int> moves = {-1, 0, 1, 0, -1}; 
    int bfs(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& visited) {
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = 1;
        int area = 0;

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            area++;

            for (int d = 0; d < 4; d++) {
                int dx = x + moves[d], dy = y + moves[d + 1];
                if (dx >= 0 && dy >= 0 && dx < n && dy < n && !visited[dx][dy] && grid[dx][dy] == 1) {
                    visited[dx][dy] = 1;
                    q.push({dx, dy});
                }
            }
        }
        return area;
    }

    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        vector<vector<int>> visited(n, vector<int>(n, 0)); 
        int maxi = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    // Compute island area for all 1s
                    maxi = max(maxi, bfs(i, j, grid, visited));
                } else if (grid[i][j] == 0) {
                    // Using Kadane's to explore by turning 0 to 1
                    grid[i][j] = 1;
                    fill(visited.begin(), visited.end(), vector<int>(n, 0));
                    maxi = max(maxi, bfs(i, j, grid, visited));
                    grid[i][j] = 0; // Revert the 0
                }
            }
        }
        return maxi;
    }
};

```

---

# 🚀 Using Greedy and Dynamic Programming

- I implemented this approach with the help of AI as i'm not the most fluent at dp currently.
- Here we basically first take all the island of `1's` and give them a unique id which is `k` here.
- We then use `bfs` to store the areas from the `dp` map.
- Lastly we try flipping each nearby `0's` to the island to `1` and check for the max area aquired.

---

# 📈 Complexity

- **⏰ Time Complexity:** This has a time complexity of $$O(n^2)$$ and therefore is optimal.
- **📝 Space Complexity:** $$O(n^2)$$


```cpp []
class Solution {
public:
    int n;
    vector<int> moves = {-1, 0, 1, 0, -1}; 
    unordered_map<int, int> dp; 

    int bfs(int i, int j, vector<vector<int>>& grid, int k, vector<vector<int>>& visited) {
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = 1;
        grid[i][j] = k; 
        int area = 0;

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            area++;

            for (int d = 0; d < 4; d++) {
                int dx = x + moves[d], dy = y + moves[d + 1];
                if (dx >= 0 && dy >= 0 && dx < n && dy < n && !visited[dx][dy] && grid[dx][dy] == 1) {
                    visited[dx][dy] = 1;
                    grid[dx][dy] = k; // mark cells by k
                    q.push({dx, dy});
                }
            }
        }
        return area;
    }

    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        vector<vector<int>> visited(n, vector<int>(n, 0)); 
        int k = 2, maxIsland = 0; 

        // Step 1: Storing current island sizes in dp
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    int islandSize = bfs(i, j, grid, k, visited);
                    dp[k] = islandSize;
                    maxIsland = max(maxIsland, islandSize);
                    k++;
                }
            }
        }

        // Step 2: Checking area after flipping adj 0's
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    unordered_set<int> uniqueIslands;

                    for (int d = 0; d < 4; d++) {
                        int dx = i + moves[d], dy = j + moves[d + 1];
                        if (dx >= 0 && dy >= 0 && dx < n && dy < n && grid[dx][dy] > 1) {
                            uniqueIslands.insert(grid[dx][dy]);
                        }
                    }

                    int NewSize = 1;
                    for (int k_of_island : uniqueIslands) {
                        NewSize += dp[k_of_island];
                    }
                    maxIsland = max(maxIsland, NewSize);
                }
            }
        }

        return maxIsland;
    }
};

```

['Dynamic Programming', 'Greedy', 'Breadth-First Search', 'C++']