N-IO-all Flashcards
Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
# 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]:
dp = {} #(left, right) -> the list of trees in left -> right
def generate(left, right):
res = []
if left == right:
return [TreeNode(left)]
if left > right:
#Needs to be [None], because for [1, 2, 3] and at 1, left should be None. But iterating [] in the for loop will cause nothing to happen!
return [None]
if (left, right) in dp:
return dp[(left, right)]
for val in range(left, right + 1):
for leftTree in generate(left, val - 1):
for rightTree in generate(val + 1, right):
root = TreeNode(val, leftTree, rightTree)
res.append(root)
dp[(left, right)] = res
return res
return generate(1, n)
#Runtime: O(4^n/ sqrt n). Nth Catalan Number, also say exponential
#Space: O(4^n/ sqrt n)Minimize the Maximum Difference of Pairs
You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.
Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.
Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5.
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
def isValid(threshold):
#count # of pairs that fall <= threshold
i, count = 0, 0
while i < len(nums) - 1:
if nums[i + 1] - nums[i] <= threshold:
count += 1
i += 2
else:
i += 1
if count == p:
return True
return False
if p == 0:
return 0
nums.sort()
#Look at problem constraints
l, r = 0, 10 ** 9
res = 10 ** 9 #the difference is at least 10 ** 9
while l <= r:
m = l + (r - l) // 2
if isValid(m):
res = min(m, res)
r = m - 1
else:
l = m + 1
return res
#O(n log n + n * log 10 ** 9)
#O(1)Search in Rotated Sorted Array (Revamped)
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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 possible 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.
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = l + (r - l) // 2
if nums[m] == target:
return m
#in left partition
elif nums[m] >= nums[l]:
#Go left
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
else: #In right partition
#Go right
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
return -1
#O(log n)
#O(1)
Search in Rotated Sorted Array II
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
class Solution:
def search(self, nums: List[int], target: int) -> bool:
l, r = 0, len(nums) - 1
while l <= r:
m = l + (r - l) // 2
if nums[m] == target:
return True
#in left partition
if nums[l] < nums[m]:
#Go left
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
#in right partition
elif nums[m] < nums[l]:
#Go right
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
#unclear. this is because nums[m] is EQUAL to nums[l]
#But at this point, we know nums[l] isn't the target either! So l += 1
else:
l += 1
return False
#O(log n) or O(n) worst case if all values are equal
#O(1)Delete and Earn
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
counts = {}
for n in nums:
counts[n] = counts.get(n, 0) + 1
nums = sorted(list(set(nums)))
earn1, earn2 = 0, 0
for i in range(len(nums)):
curEarn = nums[i] * counts[nums[i]]
#If adjacent to elt nums[i - 1]
if i > 0 and nums[i] == nums[i - 1] + 1:
tmp = max(earn1 + curEarn, earn2)
earn1 = earn2
earn2 = tmp
#not adjacent, so feel free to just add to earn2
else:
tmp = earn2 + curEarn
earn1 = earn2
earn2 = tmp
return earn2
#O(n log n)
#O(1)Check if There is a Valid Partition For The Array
You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.
We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:
The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.
Return true if the array has at least one valid partition. Otherwise, return false.
Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.
class Solution:
def validPartition(self, nums: List[int]) -> bool:
dp = {}
def dfs(i):
if i == len(nums):
return True
if i in dp:
return dp[i]
res = False
if i + 1 <= len(nums) - 1 and nums[i] == nums[i + 1]:
res = dfs(i + 2)
if i + 2 <= len(nums) - 1:
if (nums[i] == nums[i + 1] == nums[i + 2]) or (nums[i] == nums[i + 1] - 1 == nums[i + 2] - 2):
res = res or dfs(i + 3)
dp[i] = res
return res
return dfs(0)
#O(n)
#O(n)Write a solution to find the second highest salary from the Employee table. If there is no second highest salary, return null (return None in Pandas).
The result format is in the following example.
Input:
Employee table:
+—-+——–+
| id | salary |
+—-+——–+
| 1 | 100 |
| 2 | 200 |
| 3 | 300 |
+—-+——–+
Output:
+———————+
| SecondHighestSalary |
+———————+
| 200 |
+———————+
Input:
Employee table:
+—-+——–+
| id | salary |
+—-+——–+
| 1 | 100 |
+—-+——–+
Output:
+———————+
| SecondHighestSalary |
+———————+
| null |
# Write your MySQL query statement below
SELECT
IFNULL(
(SELECT DISTINCT SALARY
FROM EMPLOYEE
ORDER BY SALARY DESC
LIMIT 1 OFFSET 1),
NULL
) AS SECONDHIGHESTSALARYRepeated Substring Pattern
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Input: s = “abab”
Output: true
Explanation: It is the substring “ab” twice.
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
#max it can be split up is halfway
for i in range(1, len(s) // 2 + 1):
if len(s) % i == 0:
copies = len(s) // i
subs = s[: i]
candidate = subs * copies
if candidate == s:
return True
return False
#O(n * n)) #O(n // 2 substrings, each costs O(n // 2) time ish to create substring and checking.
#O(n) candidate is built upExcel Sheet Column Title
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
…
Input: columnNumber = 28
Output: “AB”
Input: columnNumber = 701
Output: “ZY”
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
res = []
#The minus ones are due to "1" indexing
#Example: 27.
#offset is 26 % 26 -> 0, which is A+0 -> A
#next digit is (27/26 - 1) % 26 in second run of loop, which is 0. A + 0 -> A
while columnNumber > 0:
offset = (columnNumber - 1) % 26
res.append(chr(ord('A') + offset))
columnNumber = (columnNumber - 1) // 26
return "".join(res[::-1])
#O(log_26 n)
#O(n) for resText Justification
Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
“This is an”,
“example of text”,
“justification. “
]
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res = []
line, length = [], 0
#each element of line is a word. so len(line) gives the number of words
#length: the number of characters in words.
i = 0
while i < len(words):
#If attempting to add a space after the prev word, and the new word to this line exceeds the max width, meaning line is complete.
if length + len(line) + len(words[i]) > maxWidth:
#total number of extra spaces that should exist in this line
extraSpaces = maxWidth - length
#Spaces that should go in between. If 1 word, then we div we avoid div by 0
spaces = extraSpaces // max(1, (len(line) - 1))
#Total number of spaces that should greedily be distributed. 1 space distributed after each word.
remainder = extraSpaces % max(1, (len(line) - 1))
#Add spaces after each word, except final word.
#If single word, we need to make sure we add spaces at the end ALSO (edge case). Hence max(1, len(line) - 1).
for j in range(max(1, len(line) - 1)):
line[j] += " " * spaces
if remainder:
line[j] += " "
remainder -= 1
res.append("".join(line))
#Reset the current line and length
line, length = [], 0
#Line is incomplete, so we just add a word to it.
line.append(words[i])
length += len(words[i])
i += 1
#add the last line to res
lastLine = " ".join(line) #get the line, with the spaces inserted in between already
trailingSpaces = maxWidth - len(lastLine)
res.append(lastLine + " " * trailingSpaces)
return res
#O(n)
#O(n)
Maximum Length of Pair Chain
You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.
A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.
Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key = lambda p: p[1]) #sort by end time since that's the limiting factor
res = 1
prevEnd = pairs[0][1]
for start, end in pairs[1:]:
if start > prevEnd:
res += 1
prevEnd = end
return res
#O(n log n)
#O(1)Minimum Penalty for a Shop
You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters ‘N’ and ‘Y’:
if the ith character is ‘Y’, it means that customers come at the ith hour
whereas ‘N’ indicates that no customers come at the ith hour.
If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows:
For every hour when the shop is open and no customers come, the penalty increases by 1.
For every hour when the shop is closed and customers come, the penalty increases by 1.
Return the earliest hour at which the shop must be closed to incur a minimum penalty.
Note that if a shop closes at the jth hour, it means the shop is closed at the hour j
Input: customers = “YYNY”
Output: 2
Explanation:
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.
class Solution:
def bestClosingTime(self, customers: str) -> int:
n = len(customers)
prefixes = [0] * (n + 1) #number of "N" before this point
suffixes = [0] * (n + 1) #number of "Y" after and including this point
#The n + 1, as well as the weird n + 1 and n - 1, is due to
#penalty for a shop that is out of bounds is included!
#So after the array.
for i in range(1, n + 1):
prefixes[i] = prefixes[i - 1]
if customers[i - 1] == "N":
prefixes[i] += 1
for i in range(n - 1, -1, -1):
suffixes[i] = suffixes[i + 1]
if customers[i] == "Y":
suffixes[i] += 1
res = 0
minPenalty = float('inf')
for i in range(n + 1):
penalty = prefixes[i] + suffixes[i]
if penalty < minPenalty:
minPenalty = penalty
res = i
return res
#O(n)
#O(n)Given n orders, each order consist in pickup and delivery services.
Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).
Since the answer may be too large, return it modulo 10^9 + 7.
Input: n = 2
Output: 6
Explanation: All possible orders:
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.
class Solution:
def countOrders(self, n: int) -> int:
slots = 2 * n
res = 1
while slots > 0:
#Consider one pair P1 D1, and X slots
#There are X choices for P, then X - 1 for D
#But half of these will place D before P
#So we divide by 2
count = slots * (slots - 1) // 2
res *= count
slots -= 2 #we used up two slots
#Now let while loop iterate and do the rest of the packages
return res % (10 ** 9 + 7)
#O(n) #basically O(X), which is 2 * n
#O(1)Minimum Deletions to Make Character Frequencies Unique
A string s is called good if there are no two different characters in s that have the same frequency.
Given a string s, return the minimum number of characters you need to delete to make s good.
The frequency of a character in a string is the number of times it appears in the string. For example, in the string “aab”, the frequency of ‘a’ is 2, while the frequency of ‘b’ is 1.
Input: s = “aaabbbcc”
Output: 2
Explanation: You can delete two ‘b’s resulting in the good string “aaabcc”.
Another way it to delete one ‘b’ and one ‘c’ resulting in the good string “aaabbc”.
class Solution:
def minDeletions(self, s: str) -> int:
counts = {}
for c in s:
counts[c] = counts.get(c, 0) + 1
usedFreqs = set()
res = 0
for c in counts:
freq = counts[c]
while freq > 0 and freq in usedFreqs:
freq -= 1
res += 1
usedFreqs.add(freq)
#We don't care if freq is zero, so if it is zero, we don't increment res
return res
#O(n)
#O(1)There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
class Solution:
def candy(self, ratings: List[int]) -> int:
res = [1] * len(ratings)
#Figure out increasing cases' candies. [1 2 3 4]....
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
res[i] = res[i - 1] + 1
#Figure out decreasing cases' candies [5 4 3 2], iterating from back to front
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
#Max because if the first increasing case necesitated some value,
#we CANNOT have 1 + res[i + 1] be less than the value.
res[i] = max(res[i], 1 + res[i + 1])
return sum(res)
#O(n)
#O(n) Path With Minimum Effort
You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
ROWS, COLS = len(heights), len(heights[0])
#0 effort to reach topleft
minHeap = [(0, 0, 0)] #(effort so far to reach this cell, r, c)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visit = set()
#Dijkstra's
while minHeap:
effort, r, c = heapq.heappop(minHeap)
if r == ROWS - 1 and c == COLS - 1:
return effort
if (r, c) in visit:
continue
visit.add((r, c))
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if neiR < 0 or neiR == ROWS or neiC < 0 or neiC == COLS or (neiR, neiC) in visit:
continue
difference = abs(heights[neiR][neiC] - heights[r][c])
newEffort = max(effort, difference)
heapq.heappush(minHeap, (newEffort, neiR, neiC))
#O(V ^ 2 log V)
#O(V + E) Minimum Operations to Reduce X to Zero
You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
target = sum(nums) - x
l = 0
maxWindow = -1
curSum = 0
for r in range(len(nums)):
curSum += nums[r] #always add to start
while l <= r and curSum > target:
curSum -= nums[l]
l += 1
if curSum == target:
maxWindow = max(maxWindow, r - l + 1)
return -1 if maxWindow == -1 else len(nums) - maxWindow
#O(n)
#O(1)Implement Dijkstra’s shortest path algorithm.
Given a weighted, directed graph, and a starting vertex, return the shortest distance from the starting vertex to every vertex in the graph.
Input:
n - the number of vertices in the graph, where (2 <= n <= 100). Each vertex is labeled from 0 to n - 1.
edges - a list of tuples, each representing a directed edge in the form (u, v, w), where u is the source vertex, v is the destination vertex, and w is the weight of the edge, where (1 <= w <= 10).
src - the source vertex from which to start the algorithm, where (0 <= src < n).
Note: If a vertex is unreachable from the source vertex, the shortest path distance for the unreachable vertex should be -1.
Input:
n = 5
edges = [[0,1,10], [0,2,3], [1,3,2], [2,1,4], [2,3,8], [2,4,2], [3,4,5]]
src = 0
Output:
{{0:0}, {1:7}, {2:3}, {3:9}, {4:5}}
import collections
class Solution:
def shortestPath(self, n: int, edges: List[List[int]], src: int) -> Dict[int, int]:
adj = collections.defaultdict(list)
for u, v, w in edges:
adj[u].append((v, w))
res = {}
minHeap = [(0, src)] #0 cost to reach src, and start at src
while minHeap:
w1, n1 = heapq.heappop(minHeap)
if n1 in res:
continue
res[n1] = w1
for neiNode, neiW in adj[n1]:
if neiNode not in res:
heapq.heappush(minHeap, (w1 + neiW, neiNode))
for i in range(n):
if i not in res:
res[i] = -1
return res
#O(V ^ 2 log V) -> O(E log V)
#O(V + E) -> O(E)Longest String Chain
You are given an array of words where each word consists of lowercase English letters.
wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.
For example, “abc” is a predecessor of “abac”, while “cba” is not a predecessor of “bcad”.
A word chain is a sequence of words [word1, word2, …, wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.
Return the length of the longest possible word chain with words chosen from the given list of words.
Input: words = [“a”,”b”,”ba”,”bca”,”bda”,”bdca”]
Output: 4
Explanation: One of the longest word chains is [“a”,”ba”,”bda”,”bdca”].
Example 2:
class Solution:
def longestStrChain(self, words: List[str]) -> int:
dp = {} #index of the word: max length of chain starting from that as the LONGEST word of that chain
#reverse thinking: we start with longest word then shrink it down.
wordMap = {} #map each word to the index of that word in words
words.sort(key = lambda x: -len(x)) #sort by length of longest word
for i, w in enumerate(words):
wordMap[w] = i
#index of the word
def dfs(i):
#this base case isn't needed since the conditional in for loop
#will filter out, but sure have this here it's ok.
if i >= len(words):
return 0
if i in dp:
return dp[i]
res = 1
#try deleting a word anywhere in the current word and see what happens
word = words[i]
for j in range(len(word)):
newWord = word[:j] + word[j + 1:]
if newWord in wordMap:
res = max(res, 1 + dfs(wordMap[newWord]))
dp[i] = res
return res
for i in range(len(words)):
dfs(i)
return max(dp.values())
#O(n log n + n * l ^ 2)
#O(n)
Find the Difference
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
Input: s = “abcd”, t = “abcde”
Output: “e”
Explanation: ‘e’ is the letter that was added.
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
countS = {}
countT = {}
for c in s:
countS[c] = countS.get(c, 0) + 1
for c in t:
countT[c] = countT.get(c, 0) + 1
for c in t:
if c not in countS or countS[c] < countT[c]:
return c
#O(n)
#O(1)Champagne Tower
We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup of champagne.
Then, some champagne is poured into the first glass at the top. When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has its excess champagne fall on the floor.)
For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.
Input: poured = 2, query_row = 1, query_glass = 1
Output: 0.50000
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.
class Solution:
def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
flow = [poured]
for row in range(1, query_row + 1):
curFlow = [0] * (row + 1)
for i in range(len(flow)):
extra = flow[i] - 1
if extra > 0:
curFlow[i] += extra / 2
curFlow[i + 1] += extra / 2
flow = curFlow
#If the flow is > 1, then we take 1 as the amount in this glass
#If the flow is < 1, then the flow is the amount of liquid in this glass.
return min(1, flow[query_glass])
#O(n ^ 2) where n is the size of the query row
#O(n)Sort Array By Parity
Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
l = 0
for r in range(len(nums)):
if nums[r] % 2 == 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
return nums
#O(n)
#O(1)
