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 5Use 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:
- Parse the number at the current position (handle negative numbers too)
- Create a node with that value
- Check for '(' - if found, recursively build the left subtree
- Check for '(' again - if found, recursively build the right subtree
- Skip ')' when returning from recursion
- 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 nodeNumber of Provinces
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:
Output: 2
Example 2:
Input:
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 provincesTime Complexity: where is the number of cities, is the number of vertices, and is the number of edges.
- for the loop through all cities/nodes.
- for the DFS traversal. Space Complexity: 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 islandsTime Complexity: — Each cell is visited at most once. The outer double loop runs in , 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: — The BFS queue holds the current “frontier” of the exploration. On an grid, the maximum queue size is (e.g., a diagonal layer). No extra visited structure is used since the grid is mutated in place.
Generate Parentheses
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 resTarget Sum
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:
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:
Output: 1
Constraints:
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
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:
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 = $2, which covered day 1.
On day 3, you bought a 7-day pass for = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.
Example 2:
Input:
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 = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.
Constraints:
Days are in strictly increasing order.
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
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:
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 resPartition Equal Subset Sum
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:
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
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:
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 ansBFS 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
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:
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 resLetter Combinations of a Phone Number
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:
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 resultFlood Fill
Flood Fill
You are given an image represented by an 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:
, , ,
Output:
Explanation:
From the center of the image with position (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:
, , ,
Output:
Explanation:
The starting pixel is already the target color, so no changes are made.
Constraints
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 imageTime Complexity: Space Complexity:
Detect a Cycle in an Undirected Graph
Given an undirected graph, determine whether the graph contains a cycle/loop or not.
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 FalseTime Complexity: Space Complexity:
