{C++} Simple DFS+BFS, Clean Code, From Brute to Optimized with Intuition.
Intuition⚡

Initially we can easily think of bruteforce, i.e we can take all the zeros in the grid and run DFS for each of them.


But it's clear that this will
## Intuition⚡
- Initially we can easily think of **bruteforce**, i.e we can take all the zeros in the grid and run **DFS** for each of them.

- But it's clear that this will take a lot of memory  as well as time and hence will result either in **MLE** or **TLE**.

Here’s an example of a submission using this approach:

![image.png](https://assets.leetcode.com/users/images/69c25997-ae2b-422b-b82e-a9af10963fb9_1738299475.7820482.png)

---
<br>

We can see that we got **MLE** which was expected, so now how can we **optimize** it?

What if we knew the **size** of each island **neighbouring** every 0 and then we simply checked **4-directionaly** across every 0 and added up the **unique islands?**


## Approach ✅

#### Pre-computation :

- We store all the zeros inside a queue. If the queue is **empty** means **all cells are 1**, i.e the entire grid is an island, so we return `n*n`.

- We mark the cells of each island with a unique index.

- Store the size of these islands in a map with the island index as the key.

#### Processing the Zeros :

- For each zero, we check its **neighboring cells** $$(4-directionally)$$.

- Using the island index map, we add all the neighboring islands keys to an **unordered set** to get the **unique islands**.

- Finally we sum all the sizes of **unique neighboring islands** and store the maximum size.

- If the maximum turns out to be zero means there was **no cell** containing 1 in the grid, so we `return 1` else we return the **`ans`**.

<br>

```cpp []
class Solution {
private:
    void dfs(int row, int col, vector<vector<int>>& vis, vector<vector<int>>& grid, int &temp, int &idx){
        int n = grid.size();
        if(row<0 || col<0 || row>=n || col>=n || grid[row][col]==0 || vis[row][col]) return;

        vis[row][col] = 1;
        temp++;
        grid[row][col] = idx;

        int dx[] = {0,0,-1,1};
        int dy[] = {-1,1,0,0};

        for(int i=0;i<4;i++){
            int nrow = dx[i]+row;
            int ncol = dy[i]+col;
            dfs(nrow,ncol,vis,grid,temp,idx);            
        }
    }


public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();

        ios::sync_with_stdio(0);
        cin.tie(0);

        queue<pair<int,int>> q;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0) q.push({i,j}); 
            }
        }

        if(q.empty()) return n*n;

        vector<vector<int>> vis(n,vector<int>(n));
        unordered_map<int,int> mp;
        int idx = -1;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int temp = 0;
                if(!vis[i][j] && grid[i][j]!=0){
                    dfs(i,j,vis,grid,temp,idx);
                    mp[idx] = temp;
                    idx--;
                }
            }
        }

        int ans = 0;

        while(!q.empty()){
            auto[row,col] = q.front();
            q.pop();

            int dx[] = {0,0,-1,1};
            int dy[] = {-1,1,0,0};

            int temp = 1;
            unordered_set<int> st;

            for(int i=0;i<4;i++){
                int nrow = dx[i]+row;
                int ncol = dy[i]+col;

                if(nrow>=0 && ncol>=0 && nrow<n && ncol<n && grid[nrow][ncol]!=0){
                    st.insert(grid[nrow][ncol]);
                }
            }

            for(auto &i : st) temp+=mp[i];            
            ans = max(ans,temp);
        }

        return  (ans==0)? 1 : ans;
    }
};
```

### Complexity ⭐
- Time complexity:  $$O(n^2)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:  $$O(n^2)$$

>## *~ Please upvote if you found it helpful❤️*

<br>

![image.png](https://assets.leetcode.com/users/images/560b3839-75d7-44ad-b522-eeb56e6ed352_1738299779.1540604.png)


---
['Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Queue', 'Matrix', 'Hash Function', 'Ordered Set', 'C++']