commit c7b06157212b8e55516781c63de1fad71287456d
parent ee35c25236c5051aab17d773ceae598763bc9367
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 21 Oct 2026 17:26:04 -0500
Back to the lc roots w/ a hard
Diffstat:
1 file changed, 91 insertions(+), 0 deletions(-)
diff --git a/leetcode/making-a-large-island/making-a-large-island.cpp b/leetcode/making-a-large-island/making-a-large-island.cpp
@@ -0,0 +1,91 @@
+class Solution {
+public:
+
+ int sizeAtIfUnvisited(vector<vector<int>>& markedIslands,unordered_map<int,int>& componentSizes, int y, int x, std::vector<int>& visitedComps) {
+ if(y < markedIslands.size() && y >= 0 && x < markedIslands[0].size() && x >= 0) {
+ int islandNum = markedIslands[y][x];
+ // find here with vector is faster than hashset.
+ if(std::find(visitedComps.begin(), visitedComps.end(), islandNum) == visitedComps.end()) {
+ visitedComps.push_back(islandNum);
+ return componentSizes[islandNum];
+ } else {
+ return 0;
+ }
+ } else {
+ return 0;
+ }
+ }
+
+ int score(vector<vector<int>>& grid,vector<vector<int>>& markedIslands,unordered_map<int,int>& componentSizes,int y,int x) {
+
+ int sc = 0;
+
+ if(!grid[y][x]) {
+ sc += 1;
+ }
+
+ std::vector<int> visitedComps {};
+
+ sc += sizeAtIfUnvisited(markedIslands, componentSizes, y, x, visitedComps);
+ sc += sizeAtIfUnvisited(markedIslands, componentSizes, y-1, x, visitedComps);
+ sc += sizeAtIfUnvisited(markedIslands, componentSizes, y+1, x, visitedComps);
+ sc += sizeAtIfUnvisited(markedIslands, componentSizes, y, x-1, visitedComps);
+ sc += sizeAtIfUnvisited(markedIslands, componentSizes, y, x+1, visitedComps);
+
+ return sc;
+ }
+
+ int dfs(vector<vector<int>>& grid, vector<vector<int>>& markedIslands, int mark, int x, int y) {
+ if( !(y < grid.size() && y >= 0 && x < grid[0].size() && x >= 0)) {
+ return 0;
+ }
+ if(markedIslands[y][x] != 0 || grid[y][x] == 0) {
+ return 0;
+ }
+
+ markedIslands[y][x] = mark;
+ int size = 1;
+
+ size += dfs(grid,markedIslands, mark, x + 1, y);
+ size += dfs(grid,markedIslands, mark, x - 1, y);
+ size += dfs(grid,markedIslands, mark, x, y + 1);
+ size += dfs(grid,markedIslands, mark, x, y - 1);
+
+ return size;
+
+ }
+ int largestIsland(vector<vector<int>>& grid) {
+ vector<vector<int>> markedIslands{};
+
+ for(int x = 0; x < grid.size(); ++x) {
+ markedIslands.push_back({});
+ for(int y = 0; y < grid[x].size(); ++y) {
+ markedIslands[x].push_back(0);
+ }
+ }
+
+ int components = 0;
+ unordered_map<int,int> componentSizes {};
+
+ for(int y = 0; y < grid.size(); ++y) {
+ for(int x = 0; x < grid[y].size(); ++x) {
+ int sz = dfs(grid,markedIslands, components + 1, x, y);
+ if(sz > 0) {
+ componentSizes[components + 1] = sz;
+ components += 1;
+ }
+ }
+ }
+
+ int bestScore = 1;
+
+ for(int y = 0; y < grid.size(); ++y) {
+ for(int x = 0; x < grid[y].size(); ++x) {
+ int currentScore = score(grid,markedIslands,componentSizes,y,x);
+ bestScore = max(bestScore, currentScore);
+ }
+ }
+
+ return bestScore;
+ }
+};