Problems Logs

Boundary Traversal of a Binary Tree

Boundary Traversal of a Binary Tree is the traversal of the tree that visits the left boundary, the leaves, and the right boundary of the tree.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.data = val
#         self.left = left
#         self.right = right
 
class Solution:
    # Function to check if a node is a leaf
    def isLeaf(self, root):
        return not root.left and not root.right
 
    # Function to add the left boundary of the tree
    def addLeftBoundary(self, root, res):
        curr = root.left
        while curr:
            if not self.isLeaf(curr):
                res.append(curr.data)
            if curr.left:
                curr = curr.left
            else:
                curr = curr.right
 
    # Function to add the right boundary of the tree
    def addRightBoundary(self, root, res):
        curr = root.right
        temp = []
        while curr:
            if not self.isLeaf(curr):
                temp.append(curr.data)
            if curr.right:
                curr = curr.right
            else:
                curr = curr.left
        res.extend(temp[::-1])
 
    # Function to add the leaves of the tree
    def addLeaves(self, root, res):
        if self.isLeaf(root):
            res.append(root.data)
            return
        if root.left:
            self.addLeaves(root.left, res)
        if root.right:
            self.addLeaves(root.right, res)
 
    # Main function to perform the boundary traversal of the binary tree
    def boundary(self, root):
        res = []
        if not root:
            return res
        if not self.isLeaf(root):
            res.append(root.data)
 
        self.addLeftBoundary(root, res)
        self.addLeaves(root, res)
        self.addRightBoundary(root, res)
 
        return res
 
# Helper function to print the result
def printResult(result):
    for val in result:
        print(val, end=" ")
    print()
 
# Creating a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
 
solution = Solution()
 
# Get the boundary traversal
result = solution.boundary(root)
 
# Print the result
print("Boundary Traversal: ", end="")
printResult(result)
 

Construct Binary Tree from String with Bracket Representation

4(2(3)(1))(6(5))
│ └──┬──┘ └─┬─┘
│    │      └── Right child of 4: node 6 with left child 5
│    └── Left child of 4: node 2 with children 3 and 1
└── Root value: 4
 
Tree Structure:
           4
         /   \
        2     6
       / \   / 
      3   1 5

Use Recursion with Index Tracking Since the string has a recursive structure, we can use recursion to parse it. The tricky part is keeping track of our position in the string as we parse.

Algorithm Steps:

1. Parse the number at the current position (handle negative numbers too)
2. Create a node with that value
3. Check for '(' - if found, recursively build the left subtree
4. Check for '(' again - if found, recursively build the right subtree
5. Skip ')' when returning from recursion
6. Return the node

class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None
 
class Solution:
    def treeFromString(self, s):
        if not s:
            return None
        
        self.index = 0  # Track current position in string
        return self.buildTree(s)
    
    def buildTree(self, s):
        if self.index >= len(s):
            return None
        
        # Step 1: Parse the number (could be negative or multi-digit)
        num = 0
        negative = False
        
        if s[self.index] == '-':
            negative = True
            self.index += 1
        
        while self.index < len(s) and s[self.index].isdigit():
            num = num * 10 + int(s[self.index])
            self.index += 1
        
        if negative:
            num = -num
        
        # Step 2: Create node with parsed value
        node = Node(num)
        
        # Step 3: Check for left child (first parenthesis pair)
        if self.index < len(s) and s[self.index] == '(':
            self.index += 1  # Skip '('
            node.left = self.buildTree(s)
            self.index += 1  # Skip ')'
        
        # Step 4: Check for right child (second parenthesis pair)
        if self.index < len(s) and s[self.index] == '(':
            self.index += 1  # Skip '('
            node.right = self.buildTree(s)
            self.index += 1  # Skip ')'
        
        return node

Find Minimum in Rotated Sorted Array

LeetCode 153

Find Minimum in Rotated Sorted Array

LeetCode 153

You are given an array nums of length n sorted in ascending order and rotated between 1 and n times. The array contains unique elements. Your task is to find the minimum element. The algorithm should run in $O(\log n)$ time.

Example: Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] rotated 4 times.

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] rotated 4 times.

Constraints:

• $n = \text{len(nums)}$
• $1 \leq n \leq 5000$
• $-5000 \leq \text{nums}[i] \leq 5000$
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        res = nums[0]
        left, right = 0, len(nums) - 1
        ans = float('inf')
        while left <= right:
            mid = (left + right) // 2
            if nums[left] <= nums[mid]:  # if the left side is sorted, then the minimum can be on the left side
                ans  = min(ans, nums[left])
                left = mid + 1
            else: # if the right side is sorted, then the minimum can be on the right side
                right = mid - 1
                ans = min(ans, nums[mid])
        return ans 

Minor Optimizations:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        res = nums[0]
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[left] < nums[right]:
                res = min(res, nums[left])
                break
            mid = (left + right) // 2
            res = min(res, nums[mid])
            if nums[mid] >= nums[left]:
                left = mid + 1
            else:
                right = mid - 1
        return res
        

Number of Provinces

LeetCode 547

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2

Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

class Solution:
    def dfs(self, isConnected: List[List[int]], i: int, visited: set):
        visited.add(i)
        for j in range(len(isConnected)):
            if isConnected[i][j] == 1 and j not in visited:
                self.dfs(isConnected, j, visited)
    
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = set()
        provinces = 0
        for i in range(n):
            if i not in visited:
                self.dfs(isConnected, i, visited)
                provinces += 1
        return provinces

Time Complexity: $O(N) + O(V + 2E)$ where $N$ is the number of cities, $V$ is the number of vertices, and $E$ is the number of edges.

• $O(N)$ for the loop through all cities/nodes.
• $O(V + 2E)$ for the DFS traversal. Space Complexity: $O(n) + O(n)$ for the visited set and the stack respectively.

Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        ROWS, COLS = len(grid), len(grid[0])
        islands = 0
 
        def bfs(r, c):
            q = deque()
            grid[r][c] = "0"
            q.append((r, c))
 
            while q:
                row, col = q.popleft()
                for dr, dc in directions:
                    nr, nc = dr + row, dc + col
                    if (nr < 0 or nc < 0 or nr >= ROWS or
                        nc >= COLS or grid[nr][nc] == "0"
                    ):
                        continue
                    q.append((nr, nc))
                    grid[nr][nc] = "0"
 
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1":
                    bfs(r, c)
                    islands += 1
 
        return islands

Time Complexity: $O(m \times n)$ — Each cell is visited at most once. The outer double loop runs in $O(m \times n)$, and each BFS only processes cells with value "1", marking them as "0" so they are never enqueued again. Across all islands, every cell is touched at most once.

Space Complexity: $O(\min(m, n))$ — The BFS queue holds the current “frontier” of the exploration. On an $m \times n$ grid, the maximum queue size is $O(\min(m, n))$ (e.g., a diagonal layer). No extra visited structure is used since the grid is mutated in place.

Generate Parentheses

LeetCode 22

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        stack = []
        res = []
        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return
            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()
        backtrack(0, 0)
        return res

Target Sum

LeetCode 494

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1". Return the number of different expressions that you can build, which evaluates to target.

Example 1:
Input: $nums = [1,1,1,1,1], target = 3$
Output: 5

Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

Example 2:
Input: $nums = [1], target = 1$
Output: 1

Constraints:
$1 \leq nums.length \leq 20$
$0 \leq nums[i] \leq 1000$
$0 \leq sum(nums[i]) \leq 1000$
$-1000 \leq target \leq 1000$

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {}     # (index, total) -> # of ways
        def backtrack(index, total):
            if index == len(nums):
                return 1 if total == target else 0
            if (index, total) in dp:
                return dp[(index, total)]
 
            dp[(index, total)] = backtrack(index + 1, total + nums[index])
            dp[(index, total)] += backtrack(index + 1, total - nums[index])
 
            return dp[(index, total)]
 
        return backtrack(0, 0)

Minimum Cost for Tickets

LeetCode 1209

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

a 1-day pass is sold for costs[0] dollars, a 7-day pass is sold for costs[1] dollars, and a 30-day pass is sold for costs[2] dollars. The passes allow that many days of consecutive travel.

For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8. Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 1-day pass for $costs[0]$ = $2, which covered day 1. On day 3, you bought a 7-day pass for $costs[1]$ = $7, which covered days 3, 4, ..., 9. On day 20, you bought a 1-day pass for $costs[0]$ = $2, which covered day 20. In total, you spent $11 and covered all the days of your travel.

Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 30-day pass for $costs[2]$ = $15 which covered days 1, 2, ..., 30. On day 31, you bought a 1-day pass for $costs[0]$ = $2 which covered day 31. In total, you spent $17 and covered all the days of your travel.

Constraints:
$1 \leq days.length \leq 365$
$1 \leq days[i] \leq 365$
Days are in strictly increasing order.
$costs.length == 3$
$1 \leq costs[i] \leq 1000$

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = {}
        def DFS(idx):
            if idx == len(days):
                return 0
            if idx in dp:
                return dp[idx]
                
            dp[idx] = float("inf")
            for d, c in zip([1, 7, 30], costs):
                next_day_idx = idx
                while next_day_idx < len(days) and days[next_day_idx] < days[idx] + d:
                    next_day_idx += 1
                dp[idx] = min(dp[idx], c + DFS(next_day_idx))
            return dp[idx]
 
        return DFS(0)
 
    # DP solution
    def mincostTickets_DP(self, days: List[int], costs: List[int]) -> int:
        dp = {}
        for i in range(len(days) - 1, -1, -1):
            dp[i] = float("inf")
            for d, c in zip([1, 7, 30], costs):
                j = i
                while j < len(days) and days[j] < days[i] + d:
                    j += 1
                dp[i] = min(dp[i], c + dp.get(j, 0))
        return dp[0]

Longest Palindromic Substring

LeetCode 5

Given a string s, return the longest palindromic substring in s.

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Constraints:
$1 \leq s.length \leq 1000$
$s$ consist of only digits and English letters.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        resLen = 0
        for i in range(len(s)):
            # odd length
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l : r + 1]
                    resLen = r - l + 1
                l -= 1
                r += 1
            # even length
            l, r = i, i + 1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l : r + 1]
                    resLen = r - l + 1
                l -= 1
                r += 1
        return res

Partition Equal Subset Sum

LeetCode 416

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:
$1 \leq nums.length \leq 200$
$1 \leq nums[i] \leq 100$

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2
        dp = set()
        dp.add(0)
        for num in nums:
            new_dp = set()
            for t in dp:
                new_dp.add(t + num)
                new_dp.add(t)
            dp = new_dp
        return target in dp
 
    # DP solution
    def canPartition_DP(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            for t in range(target, num - 1, -1):
                dp[t] = dp[t] or dp[t - num]
        return dp[target]

Maximum Product Subarray

LeetCode 152

Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. Note that the product of an array with a single element is the value of that element.

Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:
$1 \leq nums.length \leq 2 * 10^4$
$-10 \leq nums[i] \leq 10$
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        pre, suff = 1, 1
        ans = float('-inf')
 
        for i in range(n):
            if pre == 0:
                pre = 1
            if suff == 0:
                suff = 1
 
            pre *= nums[i]
            suff *= nums[n - i - 1]
            ans = max(ans, pre, suff)
 
        return ans

BFS of a 2d matrix

def BFS(matrix, visited, i, j):
    queue = deque([(i, j)])
    visited.add((i, j))
    while queue:
        cell = queue.popleft()
        x, y = cell
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and (nx, ny) not in visited:
                queue.append((nx, ny))
                visited.add((nx, ny))
 

Trapping Rain Water

LeetCode 42

NeetCode Solution

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:
$n == height.length$
$1 \leq n \leq 2 * 10^4$
$0 \leq height[i] \leq 10^5$

Intuition: We can use two pointers to find the maximum height of the left and right sides of the current index. We can then use the minimum of the two to find the amount of water that can be trapped at the current index.

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
 
        leftMax = [0] * n
        rightMax = [0] * n
 
        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])
 
        rightMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
 
        res = 0
        for i in range(n):
            res += min(leftMax[i], rightMax[i]) - height[i]
        return res

Letter Combinations of a Phone Number

LeetCode 17

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:
Input: digits = "2"
Output: ["a","b","c"]

Constraints:
$1 \leq digits.length \leq 4$
$digits[i]$ is a digit in the range ['2', '9'].

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }
 
        def backtrack(index, curStr):
            if len(curStr) == len(digits):
                result.append(curStr)
                return
            
            for c in digitToChar[digits[index]]:
                backtrack(index + 1, curStr + c)
        
        if digits:
            backtrack(0, "")
        return result

Flood Fill

LeetCode 733

You are given an image represented by an $m \times n$ grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill:

• Begin with the starting pixel and change its color to the new color.
• Recursively, for each pixel directly adjacent (horizontally or vertically) to the starting pixel and sharing the same color, change its color to the new one.
• Continue this process until no more adjacent pixels of the original color remain.
• Return the modified image.

Example 1
Input:
image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output:
[[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image with position $(sr, sc) = (1, 1)$ (the red pixel), all pixels connected by a path of the same color are filled. Note that the bottom corner is not colored 2, as it is not horizontally or vertically connected.

Example 2:
Input:
image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation:
The starting pixel is already the target color, so no changes are made.

Constraints:

• $m == image.length$
• $n == image[i].length$
• $1 \leq m, n \leq 50$
• $0 \leq image[i][j], color < 216$
• $0 \leq sr < m$
• $0 \leq sc < n$

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        curr_color = image[sr][sc]
        n, m = len(image), len(image[0])
        if curr_color == color:
            return image
 
        queue = [[sr, sc]]
        image[sr][sc] = color
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
 
        while queue:
            new_queue = []
            for r, c in queue:
                for dr, dc in directions:
                    nr, nc = (r + dr), (c + dc)
                    if nr >= 0 and nc >= 0 and nr < n and nc < m and image[nr][nc] == curr_color:
                        image[nr][nc] = color
                        new_queue.append([nr, nc])
            queue = new_queue
        return image

Time Complexity: $O(m \times n)$ Space Complexity: $O(m \times n)$

Detect a Cycle in an Undirected Graph

Given an undirected graph, determine whether the graph contains a cycle/loop or not.

Using BFS to detect a cycle in an undirected graph.

def check_for_cycle(src: int, v: int, adj: list[list[int]], vis: list[bool]) -> bool:
    """BFS from src; if we see a visited neighbor that isn't the parent, there's a cycle."""
    vis[src] = True
    q: deque[tuple[int, int]] = deque()
    q.append((src, -1))
 
    while q:
        node, parent = q.popleft()
        for adjacent_node in adj[node]:
            if not vis[adjacent_node]:
                vis[adjacent_node] = True
                q.append((adjacent_node, node))
            elif parent != adjacent_node:
                return True
    return False
 
 
def is_cycle(v: int, adj: list[list[int]]) -> bool:
    """Check for cycle in undirected graph (all connected components)."""
    vis = [False] * v
    for i in range(v):
        if not vis[i]:
            if check_for_cycle(i, v, adj, vis):
                return True
    return False

Time Complexity: $O(V + 2E) + O(V)$ Space Complexity: $O(V)$

Using DFS to detect a cycle in an undirected graph.

def check_for_cycle(node: int, parent: int, adj: list[list[int]], vis: list[bool]) -> bool:
    vis[node] = True
    for adjacent_node in adj[node]:
        if not vis[adjacent_node]:
            if check_for_cycle(adjacent_node, node, adj, vis):
                return True
        elif parent != adjacent_node:
            return True
    return False
 
def is_cycle(v: int, adj: list[list[int]]) -> bool:
    vis = [False] * v
    for i in range(v):
        if not vis[i]:
            if check_for_cycle(i, -1, adj, vis):
                return True
    return False

01 Matrix

LeetCode 542

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two cells sharing a common edge is 1.

Example 1:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:
$m == mat.length$
$n == mat[i].length$
$1 \leq m, n \leq 10^4$
$1 \leq m \times n \leq 10^4$
$mat[i][j]$ is either 0 or 1.
There is at least one 0 in mat.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        n, m = len(mat) ,len(mat[0])
        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
 
        queue = deque([])
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 0:
                    queue.append((i, j))
                else:
                    mat[i][j] = -1
        
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if nr >= 0 and nc >= 0 and nr < n and nc < m and mat[nr][nc] == -1:
                    mat[nr][nc] = mat[r][c] + 1
                    queue.append((nr, nc))
        return mat

Time Complexity: $O(m \times n)$ Space Complexity: $O(m \times n)$

Surrounded Regions

LeetCode 130

Given an $m \times n$ matrix board containing letters 'X' and 'O', capture all regions that are surrounded by 'X'.

• Connect: Two cells are connected if they are adjacent horizontally or vertically.
• Region: A region is formed by connecting every 'O' cell.
• Surround: A region is surrounded if none of its 'O' cells are on the edge of the board. Such regions are completely enclosed by 'X' cells.

To capture all surrounded regions, replace all 'O's in such regions with 'X' in-place within the original board. It is not necessary to return anything from the function.

Example 1:
Input:
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] Output:
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:
Input:
board = [["X"]]

Output:
[["X"]]

Constraints

• $m == board.length$
• $n == board[i].length$
• $1 \leq m, n \leq 200$
• board[i][j] is 'X' or 'O'.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        n, m = len(board), len(board[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        vis = [[False] * m for _ in range(n)]
 
        def dfs(r, c):
            if (
                r < 0 or c < 0 or r >= n or c >= m
                or board[r][c] != 'O'
                or vis[r][c]
            ):
                return
            vis[r][c] = True
            for dr, dc in directions:
                dfs(r + dr, c + dc)
 
        # Left and right borders: iterate over rows
        for r in range(n):
            if board[r][0] == 'O' and not vis[r][0]:
                dfs(r, 0)
            if board[r][m - 1] == 'O' and not vis[r][m - 1]:
                dfs(r, m - 1)
 
        # Top and bottom borders: iterate over columns
        for c in range(m):
            if board[0][c] == 'O' and not vis[0][c]:
                dfs(0, c)
            if board[n - 1][c] == 'O' and not vis[n - 1][c]:
                dfs(n - 1, c)
 
        # Flip all non-visited 'O's
        for r in range(n):
            for c in range(m):
                if board[r][c] == 'O' and not vis[r][c]:
                    board[r][c] = 'X'  

Number of Enclaves

LeetCode 1020 NeetCode Solution

You are given an $m \times n$ binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

Example 1:
Input:
grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because it's on the boundary.

Example 2:
Input:
grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

Constraints:

• $m == grid.length$
• $n == grid[i].length$
• $1 \leq m, n \leq 500$
• grid[i][j] is either 0 or 1.

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
        def dfs(r, c):
            if (r < 0 or c < 0 or
                r == ROWS or c == COLS or
                not grid[r][c] or (r, c) in visited):
                return 0
            visited.add((r, c))
            res = 1
            for dr, dc in directions:
                res += dfs(r + dr, c + dc)
            return res
             
 
        land, borderLand = 0, 0
        visited = set()
 
        for r in range(ROWS):
            for c in range(COLS):
                land += grid[r][c]
                if (grid[r][c] and (r, c) not in visited and 
                    (c in [0, COLS - 1] or r in [0, ROWS - 1])):
                    borderLand += dfs(r, c)
 
        return land - borderLand

Minimum Number of Vertices to Reach All Nodes

LeetCode 1557

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Example 1:
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3] Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Example 2:
Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] Output: [0,2,3] Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

Constraints:

• $2 \leq n \leq 10^5$
• $1 \leq edges.length \leq min(10^5, n \times (n - 1) / 2)$
• edges[i][0] != edges[i][1]
• There are no repeated edges.

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        incoming = defaultdict(list)
        for src, dst in edges:
            incoming[dst].append(src)
        
        result = []
        for node in range(n):
            if node not in incoming:
                result.append(node)
        return result
 

Is Graph Bipartite?

LeetCode 785

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).
• There are no parallel edges (graph[u] does not contain duplicate values).
• If v is in graph[u], then u is in graph[v] (the graph is undirected). The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them. A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Example 1:
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] Output: false Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:
Input: graph = [[1,3],[0,2],[1,3],[0,2]] Output: true Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints:

• $graph.length == n$
• $1 \leq n \leq 100$
• $0 \leq graph[u].length < n$
• $0 \leq graph[u][i] \leq n - 1$
• graph[u] does not contain u.
• All the values of graph[u] are unique.
• If graph[u] contains v, then graph[v] contains u.

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        odd = [0] * len(graph) # map for node `i` -> `odd=1`, `even=-1`
 
        def BFS(node):
            if odd[node]:
                return True
            
            q = deque([node])
            odd[node] = -1
            while q:
                node = q.popleft()
                for nei in graph[node]:
                    if odd[nei] and odd[nei] == odd[node]:
                        return False
                    elif not odd[nei]:
                        q.append(nei)
                        odd[nei] = -1 * odd[node]
            return True
                
        for node in range(len(graph)):
            if not BFS(node):
                return False
            
        return True

Detonate the Maximum Bombs

LeetCode 2101

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:
Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:
Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:
Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:

• Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
• Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
• Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3. Thus all 5 bombs are detonated.

Constraints:

• $1 \leq bombs.length \leq 100$
• $bombs[i].length == 3$
• $1 \leq xi, yi, ri \leq 10^5$

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        adj = defaultdict(list) # bomb -> [list of bombs]
 
        # graph builder
        for i in range(len(bombs)):
            for j in range(i + 1, len(bombs)):
                x1, y1, r1 = bombs[i]
                x2, y2, r2 = bombs[j]
                dist = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                
                if dist <= r1:
                    adj[i].append(j)
                if dist <= r2:
                    adj[j].append(i)
        
        def DFS(idx, visit):
            if idx in visit:
                return 0
            visit.add(idx)
            for nei in adj[idx]:
                DFS(nei, visit)
            return len(visit)
            
 
        res = 0
        for i in range(len(bombs)):
            res = max(res, DFS(i, set()))
        return res

Time Complexity: $O(n^3)$ - $n^2$ graph build + $n$ DFS passes each doing $O(n^2)$ work

• DFS from each bomb: $O(n) * O(n^2) = O(n^3)$
• Run DFS from each of the $n$ bombs.
• Each DFS visits each node at most once and traverses each edge at most once, so $O(V + E)$ per DFS. With $V = n$ and at most $O(n^2)$ edges, one DFS is $O(n^2)$.
• Total over $n$ starting bombs: $O(n^3)$.

Space Complexity: Adjacency list can hold $O(n^2)$ edges

Find Eventual Safe States

LeetCode 802

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Example 1:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.

• Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
• Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Example 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] Output: [4] Explanation:

• Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

Constraints:

• $n == graph.length$
• $1 \leq n \leq 10^4$
• $0 \leq graph[i].length \leq n$
• $0 \leq graph[i][j] \leq n - 1$
• graph[i] is sorted in a strictly increasing order.
• The graph may contain self-loops.
• The number of edges in the graph will be in the range $[1, 4 \times 10^4]$.

Intuition: A node is considered safe if every possible path from it ends at a terminal node (which has no outgoing edges). If a node can get stuck in a cycle, it is not safe. To find safe nodes, we can use DFS with memoization: as we explore a node, we temporarily mark it as unsafe to catch cycles. If all its neighbors are proven safe, we finally mark it as safe. If during our search we return to a node marked unsafe, that means there's a cycle.

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        safe = {}
        
        def DFS(node):
            if node in safe:
                return safe[node]
            safe[node] = False
            for nei in graph[node]:
                if not DFS(nei):
                    return safe[node]
            safe[node] = True
            return safe[node]
        
        res = []
        for node in range(n):
            if DFS(node):
                res.append(node)
        return res

Course Schedule

LeetCode 207

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• $1 \leq numCourses \leq 2000$
• $0 \leq prerequisites.length \leq 5000$
• prerequisites[i].length == 2
• $0 \leq ai, bi < numCourses$
• All the pairs prerequisites[i] are unique.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        preReqMap = {i : [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preReqMap[crs].append(pre)
        
        visited = set()
 
        def DFS(crs):
            if crs in visited:
                return False
            if preReqMap[crs] == []:
                return True
            visited.add(crs)
            for pre in preReqMap[crs]:
                if not DFS(pre): return False
            visited.remove(crs)
            preReqMap[crs] = []
            return True
        
        for crs in range(numCourses):
            if not DFS(crs): return False
        return True

Alien Dictionary

Given a sorted dictionary of an alien language having N words and K starting alphabets of a standard dictionary. Find the order of characters in the alien language.

There may be multiple valid orders for a particular test case, thus you may return any valid order as a string. The output will be True if the order returned by the function is correct, else False denoting an incorrect order. If the given arrangement of words is inconsistent with any possible letter ordering, return an empty string "".

Example 1:
Input: N = 5, K = 4, dict = ["baa","abcd","abca","cab","cad"] Output: "b d a c"

Explanation:

• We will analyze every consecutive pair to find out the order of the characters.
• The pair "baa" and "abcd" suggests 'b' appears before 'a' in the alien dictionary. The pair "baa" and "abcd" suggests 'b' appears before 'a' in the alien dictionary.
• The pair "abcd" and "abca" suggests 'd' appears before 'a' in the alien dictionary.
• The pair "abca" and "cab" suggests 'a' appears before 'c' in the alien dictionary.
• The pair "cab" and "cad" suggests 'b' appears before 'd' in the alien dictionary.
• So, ["b", "d", "a", "c"] is a valid ordering.

Example 2:
Input: N = 3, K = 3, dict = ["caa","aaa","aab"] Output: "c a b" Explanation: Similarly, if we analyze the consecutive pair

for this example, we will figure out ["c", "a", "b"] is a valid ordering.

Constraints:

• $1 \leq N \leq 300$
• $1 \leq K \leq 26$
• $1 \leq dict[i].length \leq 50$

from collections import defaultdict, deque
 
class Solution:
    def findOrder(self, dict, N, K):
        graph = defaultdict(set)
        in_degree = {chr(ord('a') + i): 0 for i in range(K)}
 
        for i in range(N - 1):
            word1, word2 = dict[i], dict[i + 1]
            found_diff = False
            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    u, v = word1[j], word2[j]
                    if v not in graph[u]:
                        graph[u].add(v)
                        in_degree[v] += 1
                    found_diff = True
                    break
            if not found_diff and len(word1) > len(word2):
                return ""
 
        queue = deque(c for c in in_degree if in_degree[c] == 0)
        result = []
 
        while queue:
            node = queue.popleft()
            result.append(node)
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
 
        if len(result) != K:
            return ""
 
        return " ".join(result)