2025 August 2 Problems

87 views
Skip to first unread message

daryl...@gmail.com

unread,
Aug 2, 2025, 12:47:07 PMAug 2
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

463. Island Perimeter Easy 73.7%

814. Binary Tree Pruning Medium 72.4%



Please download and import the following iCalendar (.ics) files to your calendar system.

Anuj Patnaik

unread,
Aug 2, 2025, 1:31:12 PMAug 2
to leetcode-meetup
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
r = len(grid)
c = len(grid[0])
perimeter = 0
for i in range(r):
for j in range(c):
if grid[i][j] == 1:
perimeter += 4
if i < r - 1 and grid[i + 1][j] == 1:
perimeter -= 1
if j < c - 1 and grid[i][j + 1] == 1:
perimeter -= 1
if i > 0 and grid[i-1][j] == 1:
perimeter -= 1
if j > 0 and grid[i][j-1] == 1:
perimeter -= 1
return perimeter




FloM

unread,
Aug 2, 2025, 1:51:14 PMAug 2
to leetcode-meetup

463. Island Perimeter Easy 
DFS approach, Time: O(n), Mem: O(n)
class Solution {
public:

int getNumOfSides(int rr, int cc, vector<vector<int>>& grid, vector<vector<int>>& seen)
{
seen[rr][cc] = 1;

int numOfSides = 0;

// left
if (rr-1 < 0)
{
++numOfSides;
}
else
{
if (grid[rr-1][cc] == 0)
{
++numOfSides;
}
else
{
if (!seen[rr-1][cc])
{
numOfSides += getNumOfSides(rr-1, cc, grid, seen);
}
}
}

// right
if (rr+1 >= grid.size())
{
++numOfSides;
}
else
{
if (grid[rr+1][cc] == 0)
{
++numOfSides;
}
else
{
if (!seen[rr+1][cc])
{
numOfSides += getNumOfSides(rr+1, cc, grid, seen);
}
}
}

// up
if (cc - 1 < 0)
{
++numOfSides;
}
else
{
if (grid[rr][cc-1] == 0)
{
++numOfSides;
}
else
{
if (!seen[rr][cc-1])
{
numOfSides += getNumOfSides(rr, cc-1, grid, seen);
}
}
}

// down
if (cc+1 >= grid[0].size())
{
++numOfSides;
}
else
{
if (grid[rr][cc+1] == 0)
{
++numOfSides;
}
else
{
if (!seen[rr][cc+1])
{
numOfSides += getNumOfSides(rr, cc+1, grid, seen);
}
}
}

return numOfSides;
}

int islandPerimeter(vector<vector<int>>& grid) {

vector<vector<int>> seen(grid.size(), vector<int>(grid[0].size(), 0));

for(int rr=0; rr<grid.size();++rr)
{
for(int cc=0; cc<grid[0].size(); ++cc)
{
if (grid[rr][cc] == 1)
{
return getNumOfSides(rr, cc, grid, seen);
}
}
}

return 0;
}
};

Kevin Burleigh

unread,
Aug 2, 2025, 1:51:42 PMAug 2
to leetcode-meetup
## Strategy:
## Use union-find to group similar strings
## Count number of distinct groups
## Time: O(L_str*N_strs^2)
## Space: O(N_strs)
## where:
## N_strs is the number of strings
## L_str is the length of a string

class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
N_strs = len(strs)
uf_parents = [x for x in range(N_strs)]

def uf_get_parent(idx):
if idx == uf_parents[idx]:
return idx
p = uf_get_parent(uf_parents[idx])
uf_parents[idx] = p
return p
def uf_union(idx_1, idx_2):
p_1 = uf_get_parent(idx_1)
p_2 = uf_get_parent(idx_2)
uf_parents[p_1] = p_2

def uf_flatten ():
for idx in range(N_strs):
uf_parents[idx] = uf_get_parent(idx)

def are_similar (s_1, s_2):
result = True
swap_made = None
prev_mismatch = None
for idx in range(len(s_1)):
if s_1[idx] != s_2[idx]:
if swap_made:
result = False
break
elif prev_mismatch is None:
prev_mismatch = (s_1[idx],s_2[idx])
result = False
else:
if (s_2[idx],s_1[idx]) == prev_mismatch:
swap_made = True
result = True
else:
result = False
break
return result

for idx_1 in range(N_strs):
for idx_2 in range(idx_1+1,N_strs):
if are_similar(strs[idx_1], strs[idx_2]):
uf_union(idx_1, idx_2)
uf_flatten()

return len(set(uf_parents))

Kevin Burleigh

unread,
Aug 2, 2025, 1:55:07 PMAug 2
to leetcode-meetup
463. Island Perimeter Easy 73.7%

## Time: O(Nrows*Ncols)
## Space: O(1)
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
perim = 0
Nrows = len(grid)
Ncols = len(grid[0]) ## valid because grid is non-empty

for ridx in range(Nrows):
for cidx in range(Ncols):
if grid[ridx][cidx] == 1:
if (ridx == 0) or (grid[ridx-1][cidx] == 0):
perim += 1
if (ridx == Nrows-1) or (grid[ridx+1][cidx] == 0):
perim += 1
if (cidx == 0) or (grid[ridx][cidx-1] == 0):
perim += 1
if (cidx == Ncols-1) or (grid[ridx][cidx+1] == 0):
perim += 1
return perim

Kevin Burleigh

unread,
Aug 2, 2025, 1:59:51 PMAug 2
to leetcode-meetup
814. Binary Tree Pruning Medium 72.4%

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
## Time: O(N_nodes)
## Space: O(N_nodes)
class Solution:
def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def recur (node):
if node is None:
return None
node.left = recur(node.left)
node.right = recur(node.right)
if (node.val == 1) or node.left or node.right:
return node
return None
return recur(root)

Sourabh Majumdar

unread,
Aug 2, 2025, 2:01:27 PMAug 2
to leetcode-meetup
814: Binary Tree Pruning.

Basic Idea:
Do a depth first search and attempt to return the number of ones in the tree.
This way, at each node, we get the information of how many ones are in the left and right subtree respectively.

If any of the left/ right subtree happens to have "zero" nodes, then we prune that subtree.

Time Complexity is around O(n) : i.e the number of nodes.
Space complexity is also O(n) : The space occupied by the recursion stack.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
struct NodeStruct{
TreeNode* node;
int num_ones;
};
int Prune(TreeNode*& root) {
if (root == nullptr) {
return 0;
}

int num_ones_left = Prune(root->left);

if (num_ones_left == 0) {
root->left = nullptr;
}

int num_ones_right = Prune(root->right);
if (num_ones_right == 0) {
root->right = nullptr;
}

return (
num_ones_left +
num_ones_right +
root->val
);

}
TreeNode* pruneTree(TreeNode* root) {
int num_ones = Prune(root);

if (num_ones == 0) {
return nullptr;
}

return root;
}
};

On Saturday, August 2, 2025 at 9:47:07 AM UTC-7 daryl...@gmail.com wrote:

FloM

unread,
Aug 2, 2025, 2:11:54 PMAug 2
to leetcode-meetup
814. Binary Tree Pruning Medium
Time: O(num of nodes) Mem: O(1)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

bool hasOne(TreeNode* node)
{
// is leaf node
if (node->left == nullptr && node->right == nullptr)
{
return node->val == 1;
}

bool leftHasOne = false;
if (node->left != nullptr)
{
if (hasOne(node->left))
{
leftHasOne = true;
}
else
{
node->left = nullptr;
}
}

bool rightHasOne = false;
if (node->right != nullptr)
{
if (hasOne(node->right))
{
leftHasOne = true;
}
else
{
node->right = nullptr;
}
}

return (rightHasOne || leftHasOne || node->val == 1);

}

TreeNode* pruneTree(TreeNode* root) {

if (hasOne(root))
{
return root;
}

return nullptr;
}
};

Kevin Burleigh

unread,
Aug 2, 2025, 3:12:30 PMAug 2
to leetcode-meetup
The discussion for the hard problem for this week referenced this previous problem:

FloM

unread,
Aug 2, 2025, 6:04:59 PMAug 2
to leetcode-meetup
839. Similar String Groups Hard
class Solution {
public:

int getPid(int id, const vector<int>& pids)
{
while(pids[id] != id)
{
id = pids[id];
}

return id;
}

void connect(int p, int q, vector<int>& pids, vector<int>& sizes, int& count)
{
int pid = getPid(p, pids);
int qid = getPid(q, pids);

if (pid == qid)
{
return;
}
else
{
if (sizes[pid] > sizes[qid])
{
pids[qid] = pid;
sizes[pid] += sizes[qid];
}
else
{
pids[pid] = qid;
sizes[qid] += sizes[pid];
}
}

--count;

}

int numSimilarGroups(vector<string>& strs) {

vector<int> pids(strs.size(), 0);
iota(pids.begin(), pids.end(), 0);

vector<int> sizes(strs.size(), 1);

int count = strs.size();

int sSize = strs[0].size();

for(int ii=0; ii<strs.size(); ++ii)
{
for(int jj=ii+1; jj<strs.size(); ++jj)
{
int diffCount = 0;
for(int kk=0; kk<sSize; ++kk)
{
if (strs[ii][kk] != strs[jj][kk])
{
++diffCount;
}
}

if ( (diffCount == 0) || (diffCount == 2))
{
connect(ii, jj, pids, sizes, count);
}
}
}

return count;
}
};

Allen S.

unread,
Aug 2, 2025, 6:07:40 PMAug 2
to leetcode-meetup
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pruneTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

root.Left = pruneTree(root.Left)
root.Right = pruneTree(root.Right)

if root.Left == nil && root.Right == nil && root.Val == 0 {
return nil
}
return root
}
Reply all
Reply to author
Forward
0 new messages