algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit aa9836e493b47a23f983d1473d0336d265e34d42
parent c7b06157212b8e55516781c63de1fad71287456d
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 21 Oct 2026 17:35:06 -0500

Slight tweaks

Diffstat:
Aleetcode/making-a-large-island/making-a-large-island-v2.cpp | 88+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 88 insertions(+), 0 deletions(-)

diff --git a/leetcode/making-a-large-island/making-a-large-island-v2.cpp b/leetcode/making-a-large-island/making-a-large-island-v2.cpp @@ -0,0 +1,88 @@ +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(vector<int>(grid[x].size(),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; + } +};