lc Flashcards
121: Max profix in an array
Input: prices = [7,1,5,3,6,4]
Output: 5
think of 2 ways
SOLUTION 1:
left and right pointers
if A[i] > A[j]:
i = j, j += 1
else:
record max
j += 1
SOLUTION 2:
if num < min: reset min and max
if num > max: update max, record res
- Contains Duplicate
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
set,
sort
- Product of Array Except Self
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]
count the 0’s
multiply everything
if zeros_count >= 2: return all 0’s
if no zeros:
if 1 zero at index i:
res = product
else:
res[i] = product / nums[i]
- Maximum Subarray
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Key Idea:
ensure that the running sum is (+)
Solution: write this without i and k
for i in nums length:
if nums[k..i] < 0:
res = max nums[k..i], res
k = i // running_sum starts at k
else:
running_sum = nums[k..i] // running_sum += nums[i]
res = max(running_sum, res)
CODE:
running_sum = 0
res = nums[0]
for num in nums:
running_sum += num
if running_sum < 0:
res = max(res, running_sum)
running_sum = 0
else:
res = max(res, running_sum)
return res
- Find Minimum in Rotated Sorted Array
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Note:
if nums[l] >= nums[r], we have to check for condition nums[mid] > nums[r]
MIN = nums[0]
while l <= r:
mid = (l + r) // 2
if nums[l] >= nums[r]:
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid - 1
else:
r = mid
MIN = min(MIN, nums[mid])
- Search in Rotated Sorted Array
Note:
if we use while l <=r, we must update l and r points as += 1, -= 1 respectively,
we can also return mid from this
while l <= r:
if nums[mid] == target: return mid
# do normal binary search if Nl < Nr
if nums[l] < nums[r]:
if nums[mid] < target: l = mid + 1
else: r = mid - 1
# at this point, nums[mid] could be either >= nums[l]
# or < nums[l]
# for each case, check which side target should be in
else:
if nums[mid] >= nums[l]:
if target >= nums[l] and target <= nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if target >= nums[mid] and target <= nums[r]:
l = mid + 1
else:
r = mid - 1
if nums[mid] == target: return mid
return -1
- 3Sum
sort nums
for i in nums length:
if nums[i] == previous number: continue
use left and right pointer method and to find pairs that equal to current number.
while l < r:
sum = nums[i] + nums[l] + nums[r]
if sum < 0:
l += 1
elif sum > 0:
r -= 1
else:
we've found a target, however, we want to move left and right pointers inward to avoid duplicates
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l - 1]: l += 1
while l < r and nums[r] == nums[r + 1]: r -= 1
return res
- Container With Most Water
UNDESTAND why it works:
while l < r:
res = max(res, area(height,l,r))
if height[l] > height[r]:
r -= 1
else:
l += 1
return res
- Climbing Stairs
”””
dp[i] = dp[i-1] + dp[i-2]
“””
if n <= 3:
return n
one, two = 1, 2
three = 3
for i in range(3,n+1):
tmp = one + two # three
one = two
two = tmp
three = tmp
return three
- Coin Change.
review: bottom up and top down approach (skipped top down approach)
BOTTOM
for i in range(amount + 1):
for coin in coins:
if i- coin == 0:
dp[i] = 1
elif i - coin > 0:
dp[i] = min(dp[i-coin] + 1, dp[i])
can be simplified to:
for i in range(amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i-coin] + 1, dp[i])
- Longest Increasing Subsequence
REVIEW:
dp[i] = max(dp[i],1 + dp[k]) if nums[i] > nums[k]
dp[i] = 1 if nums[i] <= nums[k]
where:
k = is the range form 0..i-1
for i in range(len(nums)):
max_i = 0
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], 1 + dp[j])
- Longest Common Subsequence
TOP DOWN:
try t1[0] and t2[0]
if match:
res += 1
advance
else try:
t1[0] and t2[1] +
t1[1] and t2[0]
base case:
if indices are out of range
then add cache to it
BOTTOM UP:
dp = initialize 2d array of size (M+1)*(N+1)
iterate from bottom right to top left
if characters match:
dp[i][j] = 1 + dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j] , dp[i][j+1])
return dp[0][0]
CODE:
for i in range(len(s1)-1, -1,-1):
for j in range(len(s2)-1, -1, -1):
if s1[i] == s2[j]:
dp[i][j] = 1+ dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j] , dp[i][j+1])
- Word Break
REVIEW neetcode solution
TOP DOWN RECURSIVE:
add memoization to the following code:
def bfs(cur_s):
if cur_s in wordDict: return True
if cur_s in seen: seen[cur_s]
for i in range(len(cur_s),-1,-1):
if cur_s[i:] in wordDict:
if bfs(cur_s[:i]):
return True
return False
BOTTOM UP:
- j represents the end of the prefix of the string.
- dp[i] represents whether the substring up to index s[0..i-1]
- if dp[j] is true, and dp[j..i-1] is also true, then the entire substring dp[i] is True
- since j represents every possible prefix, the prefix of “” must also exists, thus we set dp[0] to True,
wordSet = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1,len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[-1]
- Combination Sum IV
answer at i = sum of (
if rem == 0, then theres only 1 way = 1
if rem != 0, then the number of count is dp[rem]
)
BOTTOM UP APPROACH:
dp = [0] * (target+1)
dp[0] = 1
for i in range(target+1):
for num in nums:
if num > i: break
dp[i] += dp[i-num]
return dp[target]
- House Robber
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
- House Robber II
return max(
nums[0],
house_robber1(nums[1:]),
house_robber1(nums[:-1])
)
- Decode Ways
Conceptualize, Know how to write in bottom up way
TOP DOWN:
def dfs(cur_nums):
if str(cur_nums) in dp: return dp[str(cur_nums)]
if not cur_nums: return 1
if cur_nums[0] == ‘0’: return 0
res = dfs(cur_nums[1:])
if len(cur_nums) >= 2 and int(cur_nums[:2]) <= 26:
res += dfs(cur_nums[2:])
dp[str(cur_nums)] = res
return res
BOTTOM UP:
if s[0] == “0”:
return 0
two_back = 1
one_back = 1
for i in range(1, len(s)):
current = 0
if s[i] != “0”:
current = one_back
two_digit = int(s[i - 1: i + 1])
if two_digit >= 10 and two_digit <= 26:
current += two_back
two_back = one_back
one_back = current
- Unique Paths
dp[i][j] = dp[i+1][j] + dp[i][j+1]
STRINGS:
- Jump Game
iterate backwards
if cur_jump + cur_index >= last_successful_index
then last_successful_index = current_index
True if last_successful_index == 0
- Longest Substring Without Repeating Characters
- use a set and add/remove from left and right pointers
- before loop starts, make sure that set is unique by updating left pointer
- Longest Repeating Character Replacement
- length - highest unique char <= # of allowed replacements
- at every iteration, compare the highest with the count of the current character in the substring
- update l while it is not valid
- record result
- Minimum Window Substring
review optimal
BRUTE FORCE:
create a dictionary of both s1 and s2
iterate s1:
while map1 satisfies map2:
record min res
remove char at indexL from map
increment indexL
- Valid Anagram
solution 1:
- compare sorted values
solution 2:
- create a map from the first string
- iterate the second string and decrement the map
- return length of map == 0
- Group Anagrams
Idea:
group the words by their sorted order
implementation
create a dictionary
for every word:
sort it
use the sorted version as the key
append the current word to the dictionary using the sorted key
- Valid Parentheses
if matches open breaces, append
if closed braces, compare
if stack empty early, return False
return arry has 0 length
