DEV Community: Md. Rishat Talukder

🧠 Solving LeetCode Until I Become Top 1% — Day `77`

Md. Rishat Talukder — Mon, 08 Sep 2025 09:30:39 +0000

🔹 Problem: 1317 Convert Integer to the Sum of Two No-Zero Integers

Difficulty: #Easy
Tags: #Math, #BruteForce

📝 Problem Summary

We are given an integer n. We need to split it into two positive integers A and B such that:

A + B = n
Neither A nor B contains the digit 0.

Return any valid pair [A, B].

🧠 My Thought Process

Brute Force Idea:
Iterate over all possible values of A from 1 to n-1. For each A, compute B = n - A.
Check if both numbers do not contain the digit 0.
Optimized Strategy:
Since the range is only 1 to n-1, the brute force is actually fine. The constraint is small enough that this simple approach passes.
Algorithm Used:
Simple brute force search with string conversion to detect 0.

⚙️ Code Implementation (Python)

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        for A in range(1, n):
            B = n - A
            if "0" not in str(A) + str(B):
                return [A, B]
        return []

⏱️ Time & Space Complexity

Time: O(n * log(n))
(We loop up to n, and string conversion/checking costs about O(log n) per number.)
Space: O(1)
(Only a few integers are stored at a time.)

🧩 Key Takeaways

✅ Checking digits via string conversion is often the simplest and fast enough for small constraints.
💡 Sometimes brute force is the intended solution when constraints are low.
💭 Always confirm input size before over-optimizing.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week?

🚀 Progress Tracker

Metric	Value
Day	`77`
Total Problems Solved	`441`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `76`

Md. Rishat Talukder — Mon, 08 Sep 2025 09:29:30 +0000

🔹 Problem: 1304 Find N Unique Integers Sum up to Zero

Difficulty: #Easy
Tags: #Math, #Constructive

📝 Problem Summary

Given an integer n, return an array of n unique integers such that they sum up to 0.

🧠 My Thought Process

Brute Force Idea:
Generate random numbers and try to adjust until their sum is zero. This would be messy and inefficient.
Optimized Strategy:
- Pair positive and negative integers: (1, -1), (2, -2), ...
- If n is even, the pairs are enough.
- If n is odd, just add 0 to balance everything out.
- This guarantees uniqueness and ensures the sum is always 0.
Algorithm Used:

Constructive Math (pairing positives and negatives).

⚙️ Code Implementation (Python)

class Solution:
    def sumZero(self, n: int) -> List[int]:
        ans = []
        for i in range(1, n // 2 + 1):
            ans.append(i)
            ans.append(-i)
        if n % 2 == 1:
            ans.append(0)
        return ans

⏱️ Time & Space Complexity

Time: O(n) — we generate n elements.
Space: O(n) — storing the result array.

🧩 Key Takeaways

✅ Learned how constructive math can directly give the answer without brute force.
💡 The “pairing” trick is a powerful way to balance sums.
💭 If a problem asks for sums = 0 (or balanced counts), think about symmetry.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week?

🚀 Progress Tracker

Metric	Value
Day	`76`
Total Problems Solved	`440`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `75`

Md. Rishat Talukder — Fri, 05 Sep 2025 10:54:26 +0000

🔹 Problem: 2749 Minimum Operations to Make the Integer Zero

Difficulty: #Medium
Tags: #Math, #BitManipulation, #Greedy

📝 Problem Summary

You’re given two integers num1 and num2. In one operation, you can subtract num2 * k from num1. The goal is to find the smallest integer k such that the result can be represented as the sum of exactly k powers of two (not necessarily distinct). If no such k exists, return -1.

🧠 My Thought Process

Brute Force Idea:
Try all possible k values, compute x = num1 - num2*k, then check if x can be broken into exactly k powers of two.
But checking this naively for large numbers would be too slow.
Optimized Strategy:
- After subtracting, we get x = num1 - num2*k.
- For x to work:

1. `x ≥ k` (since the smallest way to split is all ones, requiring at least `k`).
2. `k ≥ popcount(x)` (since we need at least one summand for each set bit in binary).

The smallest valid k is the answer.
- Algorithm Used: Math + Bit Manipulation (bit_count to check popcount condition).

⚙️ Code Implementation (Python)

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        k = 1
        while True:
            x = num1 - num2 * k
            if x < k:  # impossible since we can't split into k parts
                return -1
            if k >= x.bit_count():  # valid if k >= popcount(x)
                return k
            k += 1

⏱️ Time & Space Complexity

Time: O(num1 / num2) in worst case (looping k), but usually small because conditions fail quickly.
Space: O(1).

🧩 Key Takeaways

✅ Learned that popcount(x) gives the minimum number of summands (powers of two) needed to form x.
💡 The tricky part was realizing you also need x ≥ k to bound the maximum possible summands.
💭 Similar problems often combine math inequalities + binary representations.

🔁 Reflection (Self-Check)

[x] Could I solve this without help? (No, needed some guidance)
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week? (Need to revisit binary condition intuition)

📚 Related Problems

[[1658 Minimum Operations to Reduce X to Zero]]
[[991 Broken Calculator]]

🚀 Progress Tracker

Metric	Value
Day	`75`
Total Problems Solved	`438`
Confidence Today	😐
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `74`

Md. Rishat Talukder — Thu, 04 Sep 2025 05:52:44 +0000

🔹 Problem: 3516 Find Closest Person

Difficulty: #Easy
Tags: #Math, #Comparison

📝 Problem Summary

First of all, maybe the EASIEST PROBLEM IN LEETCODE HISTORY.

You are given three integers x, y, and z. The task is to determine which of x or y is closer to z.

If both are equally close → return 0.
If x is closer → return 1.
If y is closer → return 2.

🧠 My Thought Process

Brute Force Idea:
I think you can solve this eeeasily with simple math.
Optimized Strategy:
The brute force is optimal here — no loops, no data structures, just math.
- Compute |x - z| and |y - z|.
- Compare the two distances.
- Decide the answer based on which difference is smaller.
Algorithm Used:

Pure mathematical comparison using absolute difference.

⚙️ Code Implementation (Python)

class Solution:
    def findClosest(self, x: int, y: int, z: int) -> int:
        x_abs = abs(x - z)
        y_abs = abs(y - z)

        if x_abs == y_abs:
            return 0
        elif x_abs < y_abs:
            return 1
        else:
            return 2

⏱️ Time & Space Complexity

Time: O(1) → Only a few arithmetic operations.
Space: O(1) → No extra memory used.

🧩 Key Takeaways

✅ Learned how simple absolute difference comparisons solve closest-number problems.
💡 The trick is recognizing that absolute difference directly measures closeness.
💭 This technique can be reused in problems like “find closest element to a target in an array” (but with loops/binary search).

🔁 Reflection (Self-Check)

[x] Could I solve this without help? (Yes, straightforward math)
[x] Did I write code from scratch? (Yes)
[x] Did I understand why it works? (Yes, absolute difference logic)
[x] Will I be able to recall this in a week? (Yes, very simple pattern)

🚀 Progress Tracker

Metric	Value
Day	`74`
Total Problems Solved	`437`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `73`

Md. Rishat Talukder — Mon, 01 Sep 2025 05:18:57 +0000

🔹 Problem: 1792. Maximum Average Pass Ratio

Difficulty: #Medium
Tags: #Greedy, #Heap, #Math, #PriorityQueue

📝 Problem Summary

You are given n classes, each with passed students out of total students. You can add extraStudents students, one at a time, and for each added student you can choose which class they join. Each added student is guaranteed to pass.

Your goal: distribute the extra students to maximize the average pass ratio across all classes.

🧠 My Thought Process

Brute Force Idea:
Try distributing students in all possible ways and compute the final average. This is obviously infeasible because the number of ways grows exponentially (n^extraStudents).
Optimized Strategy:
Instead of brute force, notice that adding a student to different classes doesn’t give equal benefit. Adding a student to a class with a low pass ratio increases the average differently than adding to one with a higher pass ratio.

The trick is: at each step, add the student to the class where they will provide the maximum increase ("gain") in the overall average.

Algorithm Used:
- Greedy + Max Heap
- Precompute the gain function for each class.
- Always pick the class with the maximum marginal gain using a heap.
- After placing a student, update its new gain and push it back into the heap.

📐 Mathematics

The gain of adding one student to a class with p passes out of t total is:

gain(p,t) = (p+1)/(t+1) - p/t

Why?

Before adding: pass ratio = p/t.
After adding: pass ratio = (p+1)/(t+1).
The difference = (p+1)/(t+1) - p/t.

This gain tells us exactly how much the class's ratio improves if we assign the next student here.

Since we want to maximize the total average, we must always choose the class with the largest gain at each step → that’s why we use a max heap.
(We push negative values because Python’s heapq is a min-heap by default.)

⚙️ Code Implementation (Python)

import heapq
from typing import List

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        heap = []

        # Gain function = improvement in pass ratio by adding one student
        def gain(pas, total):
            return (pas + 1) / (total + 1) - pas / total

        # Build initial heap with all classes
        for pas, total in classes:
            g = gain(pas, total)
            heapq.heappush(heap, (-g, pas, total))  # store negative for max heap

        # Assign extra students greedily
        for _ in range(extraStudents):
            g, pas, total = heapq.heappop(heap)
            pas += 1
            total += 1
            g = gain(pas, total)
            heapq.heappush(heap, (-g, pas, total))

        # Compute final average
        total_avg = sum(pas / total for _, pas, total in heap)
        return total_avg / len(classes)

⏱️ Time & Space Complexity

Time: O((n + extraStudents) log n)
- Each heap push/pop costs log(n).
- We do this for n initializations + extraStudents assignments.
Space: O(n) for the heap.

🧩 Key Takeaways

✅ The gain function is the key insight — quantify the benefit of adding a student.
💡 Using a max heap makes greedy selection efficient.
💭 Many allocation/optimization problems reduce to "compute marginal gain → pick max → update."

🔁 Reflection (Self-Check)

[x] Could I solve this without help? (Partially — needed insight for gain function)
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week? (Yes, heap + marginal gain pattern is memorable)

🚀 Progress Tracker

Metric	Value
Day	`73`
Total Problems Solved	`434`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `72`

Md. Rishat Talukder — Sun, 31 Aug 2025 08:01:20 +0000

🔹 Problem: 37 Sudoku Solver

Difficulty: #Hard
Tags: #Backtracking, #Matrix, #Recursion

📝 Problem Summary

We are given a partially filled 9×9 Sudoku board. The task is to fill the empty cells (.) such that the Sudoku rules are satisfied:

Each row contains digits 1–9 without repetition

Each column contains digits 1–9 without repetition

Each of the nine 3×3 sub-boxes contains digits 1–9 without repetition

The solution must modify the board in-place.

🧠 My Thought Process

Brute Force Idea:
Try all numbers 1–9 in every empty cell and check if the board remains valid. This would be extremely slow because there are many possibilities.
Optimized Strategy:
Use backtracking with constraints tracking:
- Sudoku is already solved partially in programming, So, this problem is more like a algorithm memorization problem.
- Maintain three data structures (rows, cols, boxes) to quickly check if a number can be placed.
- Instead of recomputing validity each time, update these structures when placing/removing numbers.
- Recursively try to fill the board cell by cell.
- If a placement leads to a dead end, undo (backtrack) and try another number.
Algorithm Used:
Backtracking with pruning using helper functions:
- couldPlace(val, row, col) → checks if we can place a number.
- placeNumber(val, row, col) / removeNumber(...) → update board + tracking arrays.
- backtrack(row, col) → recursive filling with backtracking.

⚙️ Code Implementation (Python)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Modify the board in-place using backtracking.
        """
        n, N = 3, 9
        rows = [[0] * (N+1) for _ in range(N)]
        cols = [[0] * (N+1) for _ in range(N)]
        boxes = [[0] * (N+1) for _ in range(N)]
        solved = False

        def couldPlace(val, row, col):
            idx = (row // 3) * 3 + col // 3
            return rows[row][val] + cols[col][val] + boxes[idx][val] == 0

        def placeNumber(val, row, col):
            idx = (row // 3) * 3 + col // 3
            rows[row][val] += 1
            cols[col][val] += 1
            boxes[idx][val] += 1
            board[row][col] = str(val)

        def removeNumber(val, row, col):
            idx = (row // 3) * 3 + col // 3
            rows[row][val] -= 1
            cols[col][val] -= 1
            boxes[idx][val] -= 1
            board[row][col] = '.'

        def placeNext(row, col):
            nonlocal solved
            if row == N-1 and col == N-1:
                solved = True
            elif col == N-1:
                backtrack(row+1, 0)
            else:
                backtrack(row, col+1)

        def backtrack(row, col):
            nonlocal solved
            if board[row][col] == '.':
                for val in range(1, 10):
                    if couldPlace(val, row, col):
                        placeNumber(val, row, col)
                        placeNext(row, col)
                        if not solved:
                            removeNumber(val, row, col)
            else:
                placeNext(row, col)

        # Initialize constraints from given board
        for i in range(N):
            for j in range(N):
                if board[i][j] != '.':
                    placeNumber(int(board[i][j]), i, j)

        backtrack(0, 0)

⏱️ Time & Space Complexity

Time: O(9^m) worst case, where m is the number of empty cells. Pruning (checking validity with sets/arrays) makes it much faster in practice.
Space: O(81) = O(1) (fixed-size board + tracking arrays).

🧩 Key Takeaways

✅ Backtracking is powerful for constraint satisfaction problems like Sudoku.
💡 The row, col, box tracking arrays significantly reduce redundant checks.
💭 When faced with recursive filling problems, always think: “Can I prune invalid paths early with some data structure?”

🔁 Reflection (Self-Check)

[x] Could I solve this without help? (with some practice)
[x] Did I write code from scratch?
[x] Did I understand why it works?
[ ] Will I be able to recall this in a week? (I haven't memorized the exact code yet)

📚 Related Problems

[[notes/36 Valid Sudoku]]
[[notes/980 Unique Paths III]]

🚀 Progress Tracker

Metric	Value
Day	`72`
Total Problems Solved	`433`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `71`

Md. Rishat Talukder — Sat, 30 Aug 2025 05:05:46 +0000

🔹 Problem: 36 Valid Sudoku

Difficulty: #Medium
Tags: #Array, #HashTable, #Matrix

📝 Problem Summary

You are given a partially filled 9 x 9 Sudoku board. Each row, column, and 3x3 sub-box must not contain duplicate digits (from 1 to 9).
Return true if the board is valid according to Sudoku rules, otherwise return false.

Note: The board does not need to be solved, only validated.

🧠 My Thought Process

Brute Force Idea:
For every cell, scan the entire row, column, and subgrid to check for duplicates. This would be inefficient since it repeatedly checks the same values.
Optimized Strategy:
Use 3 hash sets per row, per column, and per subgrid to track existing values:
- One set for each row
- One set for each column
- One set for each 3x3 box
- While iterating, if a number already exists in the corresponding row, column, or box → invalid Sudoku.

⚙️ Code Implementation (Python)

from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for i in range(9):
            for j in range(9):
                val = board[i][j]

                if val == '.':
                    continue

                box_ind = (i // 3) * 3 + (j // 3)

                if (
                    val in rows[i] or
                    val in cols[j] or
                    val in boxes[box_ind]
                ):
                    return False

                rows[i].add(val)
                cols[j].add(val)
                boxes[box_ind].add(val)

        return True

⏱️ Time & Space Complexity

Time: O(81) → O(1) (since the board size is fixed 9x9).
Space: O(81) → O(1) (at most 9×3 sets storing digits 1–9).

🧩 Key Takeaways

✅ Learned how to validate Sudoku using 3 parallel data structures (row, col, box).
💡 The trick was mapping (i, j) to a 3x3 box index using (i//3)*3 + (j//3).
💭 Any problem involving checking constraints in multiple dimensions can often be solved with parallel hash sets.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week? (Need to reinforce the box index formula).

📚 Related Problems

[[37 Sudoku Solver]]
[[2133 Check if Every Row and Column Contains All Numbers]]

🚀 Progress Tracker

Metric	Value
Day	`71`
Total Problems Solved	`432`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `70`

Md. Rishat Talukder — Fri, 29 Aug 2025 10:52:39 +0000

🔹 Problem: 3021. Alice and Bob Playing Flower Game

Difficulty: #Medium
Tags: #Math, #Combinatorics

📝 Problem Summary

Alice and Bob play a game with n flowers and m flowers. Each chooses one flower. Alice wins if the total number of petals is odd.

You need to count the number of winning pairs (x, y) where 1 ≤ x ≤ n and 1 ≤ y ≤ m.

🧠 My Thought Process

Brute Force Idea:
Loop through all pairs (x, y) and check if x + y is odd. That would be O(n * m), which is too slow for large inputs.
Optimized Strategy:
- The solution was unexpectedly simple once I realized the parity logic:
- Alice wins only when one number is even and the other is odd.
- Count how many odds and evens are in 1..n and 1..m.
- odds_in_n = (n + 1) // 2
- evens_in_n = n // 2
- odds_in_m = (m + 1) // 2
- evens_in_m = m // 2
- Winning pairs = (odds_in_n * evens_in_m) + (evens_in_n * odds_in_m)
- Simplifies to (n * m) // 2.

⚙️ Code Implementation (Python)

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return (n * m) // 2

⏱️ Time & Space Complexity

Time: O(1)
Space: O(1)

🧩 Key Takeaways

✅ Learned how to reduce brute-force counting to simple parity logic.
💡 The trick is noticing that half of all pairs will have odd sums.
💭 In future, whenever I see problems about sums being odd/even, I’ll try counting odds and evens separately instead of brute force.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week? → Let’s see 😅

🚀 Progress Tracker

Metric	Value
Day	`70`
Total Problems Solved	`431`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `69`

Md. Rishat Talukder — Thu, 28 Aug 2025 06:32:11 +0000

🔹 Problem: 3446 Sort Matrix by Diagonals

Difficulty: #Medium
Tags: #Matrix, #HashMap, #Sorting

📝 Problem Summary

You are given a 2D grid. Each diagonal of the matrix (identified by the difference row - col) must be sorted independently.

Diagonals starting from the top-right should be sorted in descending order.

Diagonals starting from the top-left should be sorted in ascending order. Return the modified matrix after sorting each diagonal.

🧠 My Thought Process

Brute Force Idea:
Extract each diagonal separately into a list, sort it, and then put the sorted values back. But this requires a lot of manual tracking of diagonals.
Optimized Strategy:
Instead of treating diagonals manually, use the property that each diagonal is uniquely identified by row - col.
- Store elements of each diagonal in a hashmap where key = row - col.
- Sort diagonals:
- If key < 0 (upper diagonals), sort descending.
- If key >= 0 (lower diagonals), sort ascending.
- Refill the matrix by popping elements back in the correct order.
Algorithm Used:

HashMap for grouping + Sorting each diagonal independently.

⚙️ Code Implementation (Python)

from collections import defaultdict
from typing import List

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        hashmap = defaultdict(list)
        rows = len(grid)
        cols = len(grid[0])

        # Group elements by diagonal (key = row - col)
        for row in range(rows):
            for col in range(cols):
                key = row - col
                hashmap[key].append(grid[row][col])

        # Sort each diagonal
        for key in hashmap:
            if key < 0:
                hashmap[key].sort(reverse=True)
            else:
                hashmap[key].sort()

        # Refill the matrix with sorted diagonals
        for row in range(rows):
            for col in range(cols):
                key = row - col
                grid[row][col] = hashmap[key].pop()

        return grid

⏱️ Time & Space Complexity

Time: O(m × n × log(min(m, n))) — each diagonal is sorted individually.
Space: O(m × n) — hashmap storage for all diagonals.

🧩 Key Takeaways

✅ Learned the trick that diagonals in a matrix can be grouped using row - col.
💡 The twist was handling different sort orders (ascending vs descending) depending on diagonal position.
💭 For future diagonal problems, always check if row - col or row + col can uniquely represent them.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?

* [x] Will I be able to recall this in a week?

📚 Related Problems

[[1329 Sort the Matrix Diagonally]]

🚀 Progress Tracker

Metric	Value
Day	`69`
Total Problems Solved	`430`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `68`

Md. Rishat Talukder — Wed, 27 Aug 2025 05:35:39 +0000

🔹 Problem: 3459. Length of Longest V-Shaped Diagonal Segment

Difficulty: Hard
Tags: #DynamicProgramming #Grid #DFS

📝 Problem Summary

You are given a binary grid (0s and 1s).
A V-shaped diagonal segment is defined as a path that:

Starts at a cell with value 1.

Moves diagonally in one of the four directions (↘, ↙, ↖, ↗).

At some point, turns exactly once clockwise (90°).

Alternates values along the path (1 → 2 → 1 → 2 …).

The task is to find the maximum length of such a segment.

🧠 My Thought Process

Brute Force Idea:
- From every 1 cell, try walking diagonally in all directions.
- Keep track of visited cells and attempt to form a V-shape.
- This would be exponential because at each step, you can choose to continue straight or turn → too slow.
Optimized Strategy:
- Notice that the segment is strictly alternating (1-2-1-2…).
- We only need to know:
- Current position (x, y).
- Current direction (which diagonal we’re going).
- Whether we’ve already turned (boolean).
- What value we expect next (1 or 2).
- This screams DFS + Memoization (cache).
Key Insight:
- If we move straight → continue the same direction.
- If we haven’t turned yet → try turning clockwise and continue.
- Use @cache so we don’t recompute states.

⚙️ Algorithm (Step-by-Step)

Define 4 diagonal directions:

↘ (1,1), ↙ (1,-1), ↖ (-1,-1), ↗ (-1,1).

Write a recursive DFS function with memoization:

Input: (x, y, direction, can_turn, expected_value).
Compute next (nx, ny) in the same direction.
If out of bounds or value ≠ expected → stop.
Otherwise:
- Continue straight in same direction.
- If can_turn = True, try turning clockwise and recurse.

Add +1 at each successful step.
From every 1 in the grid, try all 4 directions with initial can_turn=True, expecting 2 next.
Keep global maximum.

⚙️ Code Implementation (Python)

from functools import cache
from typing import List

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        DIRS = [(1, 1), (1, -1), (-1, -1), (-1, 1)]  # diagonals
        m, n = len(grid), len(grid[0])

        @cache
        def dfs(x, y, d, can_turn, target):
            nx, ny = x + DIRS[d][0], y + DIRS[d][1]
            if nx < 0 or ny < 0 or nx >= m or ny >= n or grid[nx][ny] != target:
                return 0
            best = dfs(nx, ny, d, can_turn, 3 - target)  # continue straight
            if can_turn:
                best = max(best, dfs(nx, ny, (d + 1) % 4, False, 3 - target))  # turn
            return best + 1

        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:  # must start from 1
                    for d in range(4):
                        res = max(res, dfs(i, j, d, True, 2) + 1)
        return res

⏱️ Time & Space Complexity

Time:
Each state (x, y, direction, can_turn, target) is computed once →
O(m × n × 4 × 2 × 2) ≈ O(mn).
Space:
- Memoization cache → O(mn) states.
- DFS recursion stack depth at most O(m+n).

🧩 Key Takeaways

✅ Converted brute force into stateful DFS + memoization.
💡 Trick: No need to calculate actual diagonals → just use (dx,dy) pairs.
💭 Similar problems will involve grid + path + direction + turn state → DP over state space.

🔁 Reflection (Self-Check)

[ ] Could I solve this without help? -> This problem had a lot of moving parts for me to handle alone.
[x] Did I understand why memoization was necessary?
[x] Did I capture the turning logic correctly?
[ ] Can I implement this again tomorrow without notes?

🚀 Progress Tracker

Metric	Value
Day	`68`
Total Problems Solved	`430`
Confidence Today	😃
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `67`

Md. Rishat Talukder — Tue, 26 Aug 2025 05:03:08 +0000

🔹 Problem: 3000. Maximum Area of Longest Diagonal Rectangle

Difficulty: #Easy
Tags: #Array #Math

📝 Problem Summary

You are given a 2D integer array dimensions where dimensions[i] = [li, wi] indicates that the iᵗʰ rectangle has a length of li and a width of wi.

Return the area of the rectangle with the largest area among all rectangles that have the longest diagonal. If there are multiple rectangles with the longest diagonal, return the largest area among them.

🧠 My Thought Process

Optimized Strategy: It's just a simple conditional maximization problem. We need to calculate the diagonal and area for each rectangle and keep track of the maximum diagonal and corresponding maximum area.

⚙️ Code Implementation (Python)

# Brief comment about the approach
class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        mdiag = -1
        marea = -1

        for l, w in dimensions:
            diag = l**2 + w**2
            area = l*w

            if diag > mdiag or (mdiag == diag and area>marea):
                mdiag = diag
                marea = area

        return marea

⏱️ Time & Space Complexity

Time: O(n) where n is the number of rectangles in dimensions
Space: O(1) constant space

🧩 Key Takeaways

✅ What concept or trick did I learn?
- Simple iteration with conditional checks to maintain maximum values.
💡 What made this problem tricky?
- Ensuring to check both diagonal length and area correctly.
💭 How will I recognize a similar problem in the future?
- Look for problems that require maximizing or minimizing values based on multiple criteria.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week?

🚀 Progress Tracker

Metric	Value
Day	`67`
Total Problems Solved	`429`
Confidence Today	😃 / 😐 / 😣
Leetcode Rating	`1530`

🧠 Solving LeetCode Until I Become Top 1% — Day `66`

Md. Rishat Talukder — Mon, 25 Aug 2025 06:06:16 +0000

🔹 Problem: 498. Diagonal Traverse

Difficulty: #Medium
Tags: #Matrix

📝 Problem Summary

Given an m x n matrix, return all elements of the matrix in a diagonal order as shown in the below image.

🧠 My Thought Process

Brute Force Idea: This Problem is actually totally based on observation. And it's solution is also brute force. We just need to observe the pattern and implement it.

Algorithm (Step-by-Step with Explanations):

Initialize matrix dimensions

Let row = number of rows in matrix.
Let col = number of columns in matrix.
This tells us the boundaries so we don’t step outside the matrix.

Prepare storage for the result

Create an empty list res to store elements in the required diagonal order.

Track traversal direction (zig-zag)

Use a flag parity = True.
This means:
- True → traverse up-right (↗️).
- False → traverse down-left (↙️).
We flip this after finishing each diagonal.

Loop through diagonals

There are exactly row + col - 1 diagonals in total.
Each diagonal corresponds to elements where r + c = s (a fixed sum).
So we iterate s from 0 to row + col - 2.

Case 1: Traverse upward-right (↗️) when parity is True

Starting point:
- Row index r = min(s, row - 1) (either bottom-most or current diagonal’s row).
- Column index c = s - r (the complement so that r + c = s).
Keep moving:
- While r >= 0 and c < col:
  - Append mat[r][c] to result.
  - Move one step up-right: r -= 1, c += 1.

Case 2: Traverse downward-left (↙️) when parity is False

Starting point:
- Column index c = min(s, col - 1) (either right-most or diagonal’s column).
- Row index r = s - c (so that r + c = s).
Keep moving:
- While c >= 0 and r < row:
  - Append mat[r][c] to result.
  - Move one step down-left: r += 1, c -= 1.

Flip direction

After finishing one diagonal, set parity = not parity to switch between up-right and down-left.

Return result

After traversing all diagonals, return res.

⚙️ Code Implementation (Python)

# Brief comment about the approach

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        row = len(mat)
        col = len(mat[0])
        parity = True

        res = []

        for s in range(row + col - 1):
            if parity:
                r = min(s, row - 1)
                c = s - r
                while r >= 0 and c < col:
                    res.append(mat[r][c])
                    r -= 1
                    c += 1
            else:
                c = min(s, col - 1)
                r = s - c
                while c >= 0 and r < row:
                    res.append(mat[r][c])
                    r += 1
                    c -= 1
            parity = not parity

        return res

⏱️ Time & Space Complexity

Time: O(m * n) where m is number of rows and n is number of columns.
Space: O(m * n) for the result list storing all elements.

🧩 Key Takeaways

✅ What concept or trick did I learn?
- Observing patterns in matrix traversal and using a parity flag to alternate directions.
💡 What made this problem tricky?
- Understanding how to calculate starting points for each diagonal based on the sum of indices.
💭 How will I recognize a similar problem in the future?
- Look for problems involving matrix traversal with specific patterns or orders.

🔁 Reflection (Self-Check)

[x] Could I solve this without help?
[x] Did I write code from scratch?
[x] Did I understand why it works?
[x] Will I be able to recall this in a week?

📚 Related Problems

[[2075 Decode the Slanted Ciphertext]]

🚀 Progress Tracker

Metric	Value
Day	`66`
Total Problems Solved	`428`
Confidence Today	😃
Leetcode Rating	`1530`