75 Leetcode Questions on Array
- 1. Two Sum
- 121. Best Time to Buy and Sell Stock
- 217. Contains Duplicate
- 238. Product of Array Except Self
- 53. Maximum Subarray
- 152. Maximum Product Subarray
- 153. Find Minimum in Rotated Sorted Array
- 33. Search in Rotated Sorted Array
- 15. 3Sum
- 11. Container With Most Water
- 70. Climbing Stairs
- 322. Coin Change
- 300. Longest Increasing Subsequence
- 139. Word Break
- 377. Combination Sum IV
- 198. House Robber
- 213. House Robber II
- 62. Unique Paths
- 55. Jump Game
- 133. Clone Graph
- 207. Course Schedule
- 417. Pacific Atlantic Water Flow
- 200. Number of Islands
- 212. Word Search II
- 73. Set Matrix Zeroes
- 54. Spiral Matrix
In this project, I will try to solve 75 Leetcode questions as listed in this link.
1. Two Sum
DescriptionGiven an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i, num in enumerate(nums):
if num in dic:
return [dic[num], i]
else:
dic[target - num] = i
121. Best Time to Buy and Sell Stock
DescriptionYou are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Two pointers starting from both ends (i.e., move left or right pointer based on which side has a better profit)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, len(prices)-1
minL = prices[l]
maxR = prices[r]
while l<r:
if prices[l] < minL:
minL = prices[l]
if prices[r] > maxR:
maxR = prices[r]
if prices[r-1] - minL > maxR - prices[l+1]:
r -= 1
else:
l += 1
return maxR - minL if maxR >= minL else 0
Two pointers starting from right (i.e., find highest price and then find the lowest price before it, fastest solution)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
max_price = 0
for i in range(len(prices)-1, -1, -1):
if prices[i] > max_price:
max_price = prices[i]
else:
max_profit = max(max_profit, max_price - prices[i])
return max_profit
Two pointers starting from left (i.e., find lowest price and then find the highest price after it)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
max_profit = 0
for i in range(len(prices)):
if prices[i] < min_price:
min_price = prices[i]
else:
max_profit = max(max_profit, prices[i] - min_price)
return max_profit
217. Contains Duplicate
DescriptionGiven an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
dic = {}
for num in nums:
if num in dic:
return True
else:
dic[num] = 1
238. Product of Array Except Self
DescriptionGiven an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
We will use two arrays to store the product of all elements to the left and right of each element. Then, we will multiply the two arrays to get the final result.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
left = [1] * len(nums)
right = [1] * len(nums)
for i in range(1, len(nums)):
left[i] = left[i-1] * nums[i-1]
right[len(nums)-1-i] = right[len(nums)-i] * nums[len(nums)-i]
return [left[i] * right[i] for i in range(len(nums))]
53. Maximum Subarray
DescriptionGiven an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Use Kadane’s algorithm to find the maximum subarray sum. The idea is to keep track of the maximum sum of subarrays ending at each index. If the sum is negative, we reset it to 0. Refer to this video and https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ article for more details.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
accsum = nums[0]
for n in nums[1:]:
accsum += n
if accsum <= n:
accsum = n
if accsum >= res:
res = accsum
return res
Dynamic programming solution (from greeksforgeeks)
Observation: DP[i] = max(DP[i-1] + nums[i], nums[i])
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
DP = [0] * len(nums)
DP[0] = nums[0]
for i in range(1, len(nums)):
DP[i] = max(DP[i-1] + nums[i], nums[i])
return max(DP)
152. Maximum Product Subarray
DescriptionGiven an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
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.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = max(nums)
cumMax = 1
cumMin = 1
for n in nums:
if n == 0:
cumMax = 1
cumMin = 1
continue
temp = max(cumMax * n, cumMin * n, n)
cumMin = min(cumMax * n, cumMin * n, n)
cumMax = temp
res = max(res, cumMax)
return res
153. Find Minimum in Rotated Sorted Array
DescriptionSuppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
-
[4,5,6,7,0,1,2]if it was rotated4times. -
[0,1,2,4,5,6,7]if it was rotated7times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums)-1
if nums[left] < nums[right]:
return nums[left]
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
33. Search in Rotated Sorted Array
DescriptionThere is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] >= nums[left]:
if nums[left] <= target < nums[mid]:
right = mid -1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
15. 3Sum
DescriptionGiven an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [0,1,1]
Output: []
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 3:
return [nums] if sum(nums) == 0 else []
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i+1, n-1
while left < right:
sum3 = nums[i] + nums[left] + nums[right]
if sum3 == 0:
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif sum3 < 0:
left += 1
else:
right -= 1
return res
11. Container With Most Water
DescriptionGiven n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height)-1
res = 0
while left < right:
res = max(res, min(height[left], height[right]) * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
70. Climbing Stairs
DescriptionYou are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Key Observation: DP[i] = DP[i-1] + DP[i-2] which means the number of ways to reach the i-th step is the sum of the number of ways to reach the (i-1)-th step and the number of ways to reach the (i-2)-th step.
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
a, b = 1, 2
for _ in range(2, n):
a, b = b, a+b
return b
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
322. Coin Change
DescriptionYou are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Key Observation: DP[i] = min(DP[i-c1], DP[i-c2], ...) + 1 which means the minimum number of coins to make up the amount i is the minimum number of coins to make up the amount i-c1, i-c2, … plus 1.
This problem can be visualized as a tree with the root node as the amount and the children nodes as the amount - coin values. The problem is to find the shortest path from the root to the target amount.
def coinChange(self, coins: List[int], amount: int) -> int:
BIG_NUM = amount + 1
dp = [BIG_NUM] * (amount+1)
if amount == 0:
return 0
dp[0] = 0
for i in range(0,amount+1):
for c in coins:
if i + c <= amount:
dp[i+c] = min(dp[i] + 1,dp[i+c])
if dp[amount] == BIG_NUM:
return -1
else:
return dp[amount]
300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Key Observation:
- When considering the i-th element, we need to find the longest increasing subsequence that ends with
nums[i]. - Straightforward case is when nums[i] is the largest element, then the longest `dp[i] = dp[i-1] + 1
- The addition of nums[i] to the subsequence causes the change of all previous
dp[j]wherenums[j] < nums[i].
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(n-2,-1,-1):
for j in range(i+1,n,1):
if nums[i] < nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
139. Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
def _valid(s, wordDict):
is_detect = False
for word in wordDict:
if len(word) > len(s):
continue
elif len(word) == len(s):
if word == s:
is_detect = True
else:
# if word appear in the top of the string s
if word == s[:len(word)]:
return _valid(s[len(word):], wordDict)
return is_detect
return _valid(s, wordDict)
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[-1] = True
for i in range(n-1, -1, -1):
for w in wordDict:
# check whether the word w in the head of the sub string s
if len(w) <= len(s[i:]):
if w == s[i:i+len(w)]:
dp[i] = any([dp[i+len(w)], dp[i]])
return dp[0]
377. Combination Sum IV
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The test cases are generated so that the answer can fit in a 32-bit integer.
Example 1:
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3, 1)
(2, 1, 1)
(2, 2, 1)
(3, 1, 1)
Example 2:
Input: nums = [9], target = 3
Output: 0
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(target+1):
for num in nums:
if i + num <= target:
dp[i+num] = dp[i+num] + dp[i]
return dp[-1]
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
def rob(self, nums: List[int]) -> int:
cur, pre = 0, 0
# [pre, cur, n, n+1, ...]
for n in nums:
temp = max(pre + n, cur)
pre = cur
cur = temp
return cur
213. House Robber II
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
def rob(self, nums: List[int]) -> int:
def _rob(nums):
cur, pre = 0, 0
# [pre, cur, n, n+1, ...]
for n in nums:
temp = max(pre + n, cur)
pre = cur
cur = temp
return cur
if len(nums)== 1:
return nums[0]
return max(_rob(nums[:-1]), _rob(nums[1:]))
62. Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Example 1:
Input: m = 3, n = 7
Output: 28
def uniquePaths(self, m: int, n: int) -> int:
grid = [[0 for _ in range(n)] for _ in range(m)]
# set the last row and last col to be 1
for i in range(n):
grid[m-1][i] = 1
for i in range(m):
grid[i][n-1] = 1
for row in range(m-2, -1, -1):
for col in range(n-2, -1, -1):
grid[row][col] = grid[row][col+1] + grid[row+1][col]
return grid[0][0]
55. Jump Game
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
def canJump(self, nums: List[int]) -> bool:
dp = [False] * len(nums)
dp[-1] = True
for i in range(len(nums)-2,-1,-1): # start at len(nums)-2, stop at 0
# any(dp[i + 0], dp[i + 1], ..., dp[i + nums[i]])
furthest = min(i + nums[i], len(nums)) + 1
dp[i] = any(dp[i:furthest])
return dp[0]
133. Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case:
- An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
207. Course Schedule
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.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
mapPre = {c:[] for c in range(numCourses)}
for c, p in prerequisites:
mapPre[c].append(p)
visited = {}
def dfs(c):
res = []
if mapPre[c] == []:
return True
visited[c] = True
for p in mapPre[c]:
if p in visited:
return False
else:
res.append(dfs(p))
mapPre[c] = []
del visited[c]
return all(res)
res = [dfs(c) for c,p in prerequisites]
return all(res)
417. Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m = len(heights)
n = len(heights[0])
po_map = [[0 for _ in range(n)] for _ in range(m)]
ao_map = [[0 for _ in range(n)] for _ in range(m)]
po_map[0] = [1 for _ in range(n)]
ao_map[-1] = [1 for _ in range(n)]
for i in range(m):
po_map[i][0] = 1
ao_map[i][-1] = 1
def valid(r, c):
if r < 0 or r >= m:
return False
if c < 0 or c >= n:
return False
return True
def reverse_flow(r,c, flow_map):
# going reverse flow
# if lower --> stop
# if higher --> mark as 1, mark as visited
# directions [up, down, left, right]
ds = [[-1,0], [1,0], [0,-1], [0,1]]
for d in ds:
r_, c_ = r + d[0], c + d[1]
if not valid(r_, c_):
continue
if flow_map[r_][c_] == 1:
continue
if heights[r_][c_] >= heights[r][c]:
flow_map[r_][c_] = 1
flow_map = reverse_flow(r_, c_, flow_map)
return flow_map
for i in range(n):
po_map = reverse_flow(0, i, po_map)
ao_map = reverse_flow(m-1,i, ao_map)
for i in range(m):
po_map = reverse_flow(i, 0, po_map)
ao_map = reverse_flow(i, n-1, ao_map)
# merge two map
res = []
for r in range(m):
for c in range(n):
if po_map[r][c] == 1 and ao_map[r][c] == 1:
res.append([r,c])
return res
200. 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:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
visited = [[0 for _ in range(n)] for _ in range(m)]
def valid(r, c):
if r < 0 or r >= m:
return False
if c < 0 or c >= n:
return False
return True
def dfs(r,c,ni):
# directions [up, down, left, right]
ds = [[-1,0], [1,0], [0,-1], [0,1]]
if grid[r][c] == "0":
return 0
if visited[r][c] == 1:
return 0
visited[r][c] = 1
ni += 1
for d in ds:
r_, c_ = r + d[0], c + d[1]
if not valid(r_, c_):
continue
if grid[r_][c_] == "0":
continue
if visited[r_][c_] == 1:
continue
# grid[r_][c_] == "1" and not visited
# print(r, c, r_, c_, ni, visited)
ni = dfs(r_, c_, ni)
return ni
num_islands = 0
for r in range(m):
for c in range(n):
num_islands += 1 if dfs(r,c,0) > 0 else 0
return num_islands
212. Word Search II
Given an m x n board of characters board and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
def valid(r, c):
m, n = len(board), len(board[0])
if r < 0 or r >= m:
return False
if c < 0 or c >= n:
return False
return True
def dfs(r, c, word, cur_i, found_next_word, visited):
directions = [[-1,0], [1,0], [0,-1], [0,1]]
# reach the last character
if cur_i == len(word):
return found_next_word, visited
found_cur_word = False
for d in directions:
r_, c_ = r + d[0], c + d[1]
if not valid(r_, c_):
continue
if (board[r_][c_] == word[cur_i]) and (not visited[r_][c_]):
found_cur_word = True
visited[r_][c_] = True
temp, visited = dfs(r_, c_, word, cur_i + 1, True, visited)
found_next_word = all([temp, found_next_word])
if found_cur_word:
return found_next_word, visited
else:
return False, visited
def findWord(board, word):
m, n = len(board), len(board[0])
visited = [[False for _ in range(n)] for _ in range(m)]
for r in range(m):
for c in range(n):
if board[r][c] == word[0]:
copy_visited = visited
copy_visited[r][c] = True
found, copy_visited = dfs(r,c,word,1,True,copy_visited)
if found:
return True
return False
output = []
for word in words:
if findWord(board, word):
output.append(word)
return output
73. Set Matrix Zeroes
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Key idea is to use the first row and first column as the marker to indicate if the row or column should be set to 0. However, we need to be careful when the first row itself contains a 0.
- To handle this case, we need a flag
rowZEROto indicate if the first row itself contains a 0. - We iterate columns from right to left to avoid overwriting the marker.
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
ROWS = len(matrix)
COLS = len(matrix[0])
rowZERO = False
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
if r > 0:
matrix[0][c] = 0
matrix[r][0] = 0
else:
rowZERO = True
matrix[0][c] = 0
for r in range(1,ROWS):
for c in range(COLS-1,-1,-1):
if matrix[0][c] == 0:
matrix[r][c] = 0
if matrix[r][0] == 0:
matrix[r][c] = 0
if rowZERO:
for c in range(COLS):
matrix[0][c] = 0
54. Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
def move_right(r, c):
return r, c+1
def move_left(r, c):
return r, c-1
def move_up(r, c):
return r-1, c
def move_down(r, c):
return r+1, c
def move(r, c, direction):
if direction == 'move_right':
return move_right(r, c)
elif direction == 'move_down':
return move_down(r, c)
elif direction == 'move_up':
return move_up(r, c)
elif direction == 'move_left':
return move_left(r, c)
else:
raise ValueError
def valid(r, c, left_col, right_col, top_row, bot_row):
if r < top_row or r > bot_row:
return False
if c < left_col or c > right_col:
return False
return True
def change_direction(direction, left_col, right_col, top_row, bot_row):
if direction == 'move_right':
return 'move_down', left_col, right_col, top_row + 1, bot_row
elif direction == 'move_down':
return 'move_left', left_col, right_col - 1, top_row, bot_row
elif direction == 'move_left':
return 'move_up', left_col, right_col, top_row, bot_row - 1
elif direction == 'move_up':
return 'move_right', left_col + 1, right_col, top_row, bot_row
else:
raise ValueError
def next_move(r, c, direction, left_col, right_col, top_row, bot_row):
temp_r, temp_c = move(r, c, direction)
if valid(temp_r, temp_c, left_col, right_col, top_row, bot_row):
return direction, left_col, right_col, top_row, bot_row
else:
return change_direction(direction, left_col, right_col, top_row, bot_row)
output = []
direction = 'move_right'
r, c = 0, 0
ROWS = len(matrix)
COLS = len(matrix[0])
left_col = 0
right_col = COLS - 1
top_row = 0
bot_row = ROWS - 1
while len(output) < ROWS * COLS:
output.append(matrix[r][c])
direction, left_col, right_col, top_row, bot_row = next_move(r, c, direction, left_col, right_col, top_row, bot_row)
r, c = move(r, c, direction)
return output
Enjoy Reading This Article?
Here are some more articles you might like to read next: