N-IO-part2 Flashcards
Given n points on a 2D plane where points[i] = [xi, yi], Return the widest vertical area between two points such that no points are inside the area.
A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.
Note that points on the edge of a vertical area are not considered included in the area.
Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.
class Solution:
def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
res = 0
points.sort()
for i in range(len(points) - 1):
res = max(res, points[i + 1][0] - points[i][0])
return res
#O(n log n)
#O(1)
Buy Two Chocolates
You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.
You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.
Input: prices = [1,2,2], money = 3
Output: 0
Explanation: Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.
class Solution:
def buyChoco(self, prices: List[int], money: int) -> int:
min1, min2 = float('inf'), float('inf')
for p in prices:
if p < min2:
if p < min1:
min2 = min1
min1 = p
else:
min2 = p
remaining = money - (min1 + min2)
return remaining if remaining >= 0 else money
#O(n)
#O(1)Path Crossing
Given a string path, where path[i] = ‘N’, ‘S’, ‘E’ or ‘W’, each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.
Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.
Input: path = “NESWW”
Output: true
Explanation: Notice that the path visits the origin twice.
class Solution:
def isPathCrossing(self, path: str) -> bool:
directions = {"N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0)}
visit = set()
visit.add((0, 0))
x, y = 0, 0
for letter in path:
dx, dy = directions[letter]
x, y = x + dx, y + dy
if (x, y) in visit:
return True
visit.add((x, y))
return False
#O(n)
#O(n)Destination City
You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.
It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.
Input: paths = [[“London”,”New York”],[“New York”,”Lima”],[“Lima”,”Sao Paulo”]]
Output: “Sao Paulo”
Explanation: Starting at “London” city you will reach “Sao Paulo” city which is the destination city. Your trip consist of: “London” -> “New York” -> “Lima” -> “Sao Paulo”.
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
allCities = set([source for source, dest in paths])
for source, dest in paths:
if dest not in allCities:
return dest
#O(n)
#O(n)
#The idea is that collecting all the source nodes will give all cities that lead SOMEWHERE.
#Then check destination nodes. If a destination node is not in allCities, then it is a terminal.Minimum Changes To Make Alternating Binary String
You are given a string s consisting only of the characters ‘0’ and ‘1’. In one operation, you can change any ‘0’ to ‘1’ or vice versa.
The string is called alternating if no two adjacent characters are equal. For example, the string “010” is alternating, while the string “0100” is not.
Return the minimum number of operations needed to make s alternating.
Input: s = “0100”
Output: 1
Explanation: If you change the last character to ‘1’, s will be “0101”, which is alternating.
class Solution:
def minOperations(self, s: str) -> int:
res = 0 #number of changes needed assuming string starts at 0
for i in range(len(s)):
expected = str(i % 2)
if s[i] != expected:
res += 1
return min(res, len(s) - res)
#O(n)
#O(1)Largest Substring Between Two Equal Characters
Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.
A substring is a contiguous sequence of characters within a string.
Input: s = “abca”
Output: 2
Explanation: The optimal substring here is “bc”.
class Solution:
def maxLengthBetweenEqualCharacters(self, s: str) -> int:
firstIndex = {}
res = -1
for i, c in enumerate(s):
if c in firstIndex:
res = max(res, i - firstIndex[c] - 1)
else:
firstIndex[c] = i
return res
#O(n)
#O(26) -> O(1)Convert an Array Into a 2D Array With Conditions
You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:
The 2D array should contain only the elements of the array nums.
Each row in the 2D array contains distinct integers.
The number of rows in the 2D array should be minimal.
Return the resulting array. If there are multiple answers, return any of them.
Note that the 2D array can have a different number of elements on each row.
Input: nums = [1,3,4,1,2,3,1]
Output: [[1,3,4,2],[1,3],[1]]
Explanation: We can create a 2D array that contains the following rows:
- 1,3,4,2
- 1,3
- 1
All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer.
It can be shown that we cannot have less than 3 rows in a valid array.
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
counts = defaultdict(int)
res = []
for n in nums:
row = counts[n]
if row == len(res):
res.append([])
res[row].append(n)
counts[n] += 1
return res
#O(n)
#O(n)Number of Laser Beams in a Bank
Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the ith row, consisting of ‘0’s and ‘1’s. ‘0’ means the cell is empty, while’1’ means the cell has a security device.
There is one laser beam between any two security devices if both conditions are met:
The two devices are located on two different rows: r1 and r2, where r1 < r2.
For each row i where r1 < i < r2, there are no security devices in the ith row.
Laser beams are independent, i.e., one beam does not interfere nor join with another.
Return the total number of laser beams in the bank.
Input: bank = [“011001”,”000000”,”010100”,”001000”]
Output: 8
Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams:
* bank[0][1] – bank[2][1]
* bank[0][1] – bank[2][3]
* bank[0][2] – bank[2][1]
* bank[0][2] – bank[2][3]
* bank[0][5] – bank[2][1]
* bank[0][5] – bank[2][3]
* bank[2][1] – bank[3][2]
* bank[2][3] – bank[3][2]
Note that there is no beam between any device on the 0th row with any on the 3rd row.
This is because the 2nd row contains security devices, which breaks the second condition.
class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
prev = bank[0].count("1")
res = 0
for r in range(1, len(bank)):
cur = bank[r].count("1")
if cur:
res += (prev * cur)
prev = cur
return res
#O(mn)
#O(n)
#2 Rows. prev and current
Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
l, r = 0, 0
res = 0
while l < len(g) and r < len(s):
if g[l] <= s[r]:
res += 1
l += 1
r += 1
else:
r += 1
return res
#O(n log n + m log m + n + m)
#O(1)Minimum Number of Operations to Make Array Empty
You are given a 0-indexed array nums consisting of positive integers.
There are two types of operations that you can apply on the array any number of times:
Choose two elements with equal values and delete them from the array.
Choose three elements with equal values and delete them from the array.
Return the minimum number of operations required to make the array empty, or -1 if it is not possible.
Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: We can apply the following operations to make the array empty:
- Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4].
- Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4].
- Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4].
- Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = [].
It can be shown that we cannot make the array empty in less than 4 operations.
class Solution:
def minOperations(self, nums: List[int]) -> int:
"""
1: -1
2: 1
3: 1
4: 2 ops (2 + 2)
5: 2 ops (2 + 3)
6: 2 ops (3 + 3)
7; 3 ops (2 + 2 + 3)
8: 3 ops (3 + 3 + 2)
so the formula is simply ceil(n / 3)
"""
counts = Counter(nums)
res = 0
for n, c in counts.items():
if c == 1: #impossible if any are -1
return -1
res += ceil(c / 3)
return res
#O(n)
#O(n)Minimum Falling Path Sum
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.
A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
#We do top down since we have to start at the very top
#dp[c] is for some given row. It stores the min result so far
#We start at row #1. Row #0 is just the previous dp result (the first row of matrix)
#left is matrix[r-1][c]. This means... what is the minimum sum so far up until topleft cell?
#etc.
for r in range(1, ROWS):
for c in range(COLS):
left = matrix[r - 1][c - 1] if c - 1 >= 0 else float('inf')
mid = matrix[r - 1][c]
right = matrix[r - 1][c + 1] if c + 1 < COLS else float('inf')
matrix[r][c] += min(left, mid, right)
return min(matrix[-1])
#O(n ** 2)
#O(1) #since overwrite input. O(N) if dp array.Sum of Subarray Minimums
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.
Input: arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
MOD = 10 ** 9 + 7
stack = [] #(index, num)
res = 0
#EXAMPLE:
# s[-1][0] j i
# 1 2 3 4 1
# left is 3 - 2
# right is 4 - 3
# etc
for i, n in enumerate(arr):
while stack and n < stack[-1][1]:
j, m = stack.pop()
left = j - stack[-1][0] if stack else j + 1
right = i - j
res = (res + m * left * right) % MOD
stack.append((i, n))
#PHASE 2: stack is monotonically increasing
#[(1, 1), (2, 2), (3, 4)]
#In this case, go through the stack, then check the distance between
#current elt and previous elt on stack if present, Otherwise, goes all the way
#Until the front of array
for i in range(len(stack)):
j, n = stack[i]
left = j - stack[i - 1][0] if i > 0 else j + 1
right = len(arr) - j
res = (res + n * left * right) % MOD
return res
#O(N)
#O(N)Pseudo-Palindromic Paths in a Binary Tree
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
counts = defaultdict(int)
oddCount = 0
#Palindromes have at most one odd value.
#PREORDER TRAVERSAL.
def dfs(root):
nonlocal oddCount
if not root:
return 0
#What to do when hit a non-null value. PROCESS CURRENT
counts[root.val] += 1
change = 1 if counts[root.val] % 2 else -1
oddCount += change
res = 0
#if it's a leaf do this. This is part of "process current" - no need to go left and right.
if not root.left and not root.right:
res = 1 if oddCount <= 1 else 0
else: #RECURSE LEFT AND PROCESS RIGHT
res = dfs(root.left) + dfs(root.right)
#Once if we have computed the left and right children, let's clean up the current value before popping up to parent
#Backtrack furrent
counts[root.val] -= 1 #clean up counts hashmap
oddCount -= change #clean up parity
return res
return dfs(root)
#O(N)
#O(H)
There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.
Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
"""
# dp = [[-1] * n for r in range(m)] #(m, n): max number of ways to get outside from that location
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
dp = {}
def dfs(r, c, numMoves):
if r < 0 or r == m or c < 0 or c == n:
return 1
if numMoves == 0: #if 0 moves left and still not at boundary, return 0
return 0
if (r, c, numMoves) in dp:
return dp[(r, c, numMoves)]
res = 0
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
res = (res + dfs(neiR, neiC, numMoves - 1)) % (10 ** 9 + 7)
dp[(r, c, numMoves)] = res
return res
return dfs(startRow, startColumn, maxMove)
#O(mn*M) #max moves M, multiplied by dimensions of grid
#O(mn*M)
"""
ROWS, COLS = m, n
dp = [[0] * COLS for r in range(ROWS)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
MOD = 10 ** 9 + 7
for move in range(1, maxMove + 1):
tmp = [[0] * COLS for r in range(ROWS)]
for r in range(ROWS):
for c in range(COLS):
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if (0 <= neiR < ROWS and 0 <= neiC < COLS):
tmp[r][c] = (tmp[r][c] + dp[neiR][neiC]) % MOD
else:
tmp[r][c] = (tmp[r][c] + 1) % MOD
dp = tmp
return dp[startRow][startColumn]
#Runtime: O(mn*M)
#Space: O(mn) we only need the dp grid for previous move - 1, and current move.
Number of Submatrices That Sum to Target
Given a matrix and a target, return the number of non-empty submatrices that sum to target.
A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.
Two submatrices (x1, y1, x2, y2) and (x1’, y1’, x2’, y2’) are different if they have some coordinate that is different: for example, if x1 != x1’.
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
sub_sum = [[0] * COLS for r in range(ROWS)]
#Compute submatrix sums
for r in range(ROWS):
for c in range(COLS):
top = sub_sum[r - 1][c] if r > 0 else 0
left = sub_sum[r][c - 1] if c > 0 else 0
top_left = sub_sum[r - 1][c - 1] if min(r, c) > 0 else 0
sub_sum[r][c] = matrix[r][c] + top + left - top_left
res = 0
for r1 in range(ROWS):
for r2 in range(r1, ROWS):
count = defaultdict(int)
count[0] = 1
for c in range(COLS):
cur_sum = sub_sum[r2][c] - (
sub_sum[r1 - 1][c] if r1 > 0 else 0
)
diff = cur_sum - target
res += count[diff]
count[cur_sum] += 1
return res
#Similar to prefix sum equals K
#O(R ** 2 * C)
#O(RC)
