2025 October 11 Problems

[daryl...@gmail.com]

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.

Maximum Area problems have been rolled over.

463. Island Perimeter Easy 73.9%

3380. Maximum Area Rectangle With Point Constraints I Medium 50.4%

3382. Maximum Area Rectangle With Point Constraints II Hard 21.2%

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

Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609

[Anuj Patnaik]

class Solution:

def maxRectangleArea(self, points: List[List[int]]) -> int:

max_area = -1

if len(points) < 4:

return -1

set_points = set()

for p in points:

set_points.add(tuple(p))

for i in range(len(points)):

for j in range(i+1, len(points)):

x1 = points[i][0]

y1 = points[i][1]

x2 = points[j][0]

y2 = points[j][1]

if x1 != x2 and y1 != y2:

x_min = min(x1,x2)

x_max = max(x1,x2)

y_min = min(y1,y2)

y_max = max(y1, y2)

if (x1, y2) in set_points and (x2, y1) in set_points:

has_point_inside = False

corners = {(x1, y1), (x2, y2), (x1, y2), (x2, y1)}

for k in set_points:

x = k[0]

y = k[1]

if x_min <= x <= x_max and y_min <= y <= y_max and (x, y) not in corners:

has_point_inside = True

break

if not has_point_inside:

area = abs(x2 - x1) * abs(y2 - y1)

max_area = max(max_area, area)

return max_area

[Anuj Patnaik]

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

[Ashish Lakhani]

class Solution:

def islandPerimeter(self, grid: List[List[int]]) -> int:

#How many neigbors in left , right , top and bottom

def isValid(i,j):

if i >= 0 and i < len(grid) and j >= 0 and j < len(grid[0]):

return True

return False

def checkSharedBorders(i,j):

count = 0

if isValid(i-1,j) and grid[i-1][j] == 1:

count+=1

if isValid(i+1,j) and grid[i+1][j] == 1:

count+=1

if isValid(i,j-1) and grid[i][j-1] == 1:

count+=1

if isValid(i,j+1) and grid[i][j+1] == 1:

count+=1

return 4-count

perimeter=0

for i in range(len(grid)):

for j in range(len(grid[0])):

if grid[i][j] == 1:

perimeter+=checkSharedBorders(i,j)

return perimeter

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/leetcode-meetup/05312b8e-eeef-49b9-8b3f-bbb2035b3583n%40googlegroups.com.

[Wang Lijun]

[Wang Lijun]

class Solution:

def islandPerimeter(self, grid: List[List[int]]) -> int:

ROW, COL = len(grid), len(grid[0])

visiting = set()

def dfs(r, c):

if (r < 0 or r >= ROW or c < 0 or c >= COL or grid[r][c] == 0):

return 1

if (r, c) in visiting:

return 0

visiting.add((r, c))

sides = 0

sides += dfs(r+1, c)

sides += dfs(r-1, c)

sides += dfs(r, c+1)

sides += dfs(r, c-1)

return sides

for r in range(ROW):

for c in range(COL):

if grid[r][c] == 1:

return dfs(r, c)

[Sourabh Majumdar]

Island perimeter.

The general gist of the solution is that, when we peform a dfs, and we are unable to "explore" a neighboring cell, we increment the perimeter (because we treat the neighboring cell as a boundary). The only exception happens, when we attempt to visit an "already explored cell", in that case, we do not increment the island perimeter.

class Solution {

public:

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

int total_rows = grid.size();

int total_cols = grid[0].size();

int perimeter = 0;

auto cell_value = [&](int row, int col) -> int {

if (row < 0 || row >= total_rows) {

return 0;

}

if (col < 0 || col >= total_cols) {

return 0;

}

return grid[row][col];

};

// The dfs will increment the perimeter

// if the neighboring cell is a water/ out of bounds

// (both represented by the value 0, see the lambda above).

std::function<void(int, int)> dfs = [&](int row, int col) {

grid[row][col] = 2; // 2 marks the cell as visited

{

int top_row = row - 1;

int top_col = col;

if (cell_value(top_row, top_col) == 0) {

perimeter += 1;

}

if (cell_value(top_row, top_col) == 1) {

dfs(top_row, top_col);

}

}

{

int bottom_row = row + 1;

int bottom_col = col;

if (cell_value(bottom_row, bottom_col) == 0) {

perimeter += 1;

}

if (cell_value(bottom_row, bottom_col) == 1) {

dfs(bottom_row, bottom_col);

}

}

{

int left_row = row;

int left_col = col - 1;

if (cell_value(left_row, left_col) == 0) {

perimeter += 1;

}

if (cell_value(left_row, left_col) == 1) {

dfs(left_row, left_col);

}

}

{

int right_row = row;

int right_col = col + 1;

if (cell_value(right_row, right_col) == 0) {

perimeter += 1;

}

if (cell_value(right_row, right_col) == 1) {

dfs(right_row, right_col);

}

}

};

for(int row = 0; row < total_rows; row++) {

for(int col = 0; col < total_cols; col++) {

if(grid[row][col] == 1) {

dfs(row, col);

break;

}

}

}

return perimeter;

}

};

[Carrie Lastname]

3382. Maximum Area Rectangle With Point Constraints II Hard

class Solution:
    def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:
        ys = {}
        for x,y in zip(xCoord, yCoord):
            if y not in ys:
                ys[y] = []
            ys[y].append(x)
        prevys = {}
        allxs = sorted(set(xCoord))
        st = SegmentTree(len(allxs))
        maxArea = -1
        xToI = {}
        for i,x in enumerate(allxs):
            xToI[x] = i
        for y in sorted(ys.keys()):
            xs = sorted(ys[y])
            for x1,x2 in zip(xs, xs[1:]):
                if x1 in prevys and x2 in prevys:
                    prevy1 = prevys[x1]
                    if prevy1 == prevys[x2]:
                        i1,i2 = xToI[x1], xToI[x2]
                        maxy = st.get(i1+1,i2-1)
                        if maxy < prevy1:
                            maxArea = max(maxArea, (y-prevy1) * (x2-x1))
           
            for x in xs:
                st.update(xToI[x], y)
                prevys[x] = y
        return maxArea

class SegmentTree:

    def __init__(self, n):
        self.t = [-1] * 4*n
        self.n = n

    def get(self, l, r):
        def getRec(treeIndex, tl,tr, l,r):
            if l>r:
                return -1
            if tl==l and tr==r:
                return self.t[treeIndex]
            m = (tl+tr)//2
            childl = 2*treeIndex+1
            childr = 2*treeIndex+2
            q1 = getRec(childl, tl, m, l, min(r,m))
            q2 = getRec(childr, m+1, tr, max(l,m+1), r)
            return max(q1,q2)
        return getRec(0, 0, self.n-1, l, r)

    def update(self, index, num):
        def updateRec(treeIndex, l,r):
            if l==r:
                self.t[treeIndex] = num
            else:
                m = (l+r)//2
                childl = 2*treeIndex+1
                childr = 2*treeIndex+2
                if index <=m:
                    updateRec(childl, l, m)
                else:
                    updateRec(childr, m+1, r)
                self.t[treeIndex] = max(self.t[childl], self.t[childr])

        updateRec(0, 0, self.n-1)

On Saturday, October 11, 2025 at 9:46:54 AM UTC-7 daryl...@gmail.com wrote:

[Eli Manzo]

DIR = [

(0, 1),

(0, -1),

(-1, 0),

(1, 0)

]

class Solution:

def islandPerimeter(self, grid: List[List[int]]) -> int:

r = len(grid)

c = len(grid[0])

res = 0

for i in range(r):

for j in range(c):

if grid[i][j] == 0:

continue

q = deque()

q.append((i, j))

grid[i][j] = 0

vis = {(i, j)}

while q:

ci, cj = q.popleft()

for di, dj in DIR:

ni, nj = di + ci, dj + cj

if ni < 0 or ni >= r or nj < 0 or nj >= c or grid[ni][nj] == 0:

continue

q.append((ni, nj))

vis.add((ni, nj))

grid[ni][nj] = 0

for (qi, qj) in vis:

res += self.getPerimeter(qi, qj, vis)

return res

def getPerimeter(self, qi, qj, setQ):

res = 4

for di, dj in DIR:

ni, nj = qi + di, qj + dj

if (ni, nj) in setQ:

res -= 1

return res