Week 1 of Blind 50 Flashcards
**1. Two Sum **
Given 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.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
time: 0(n) | space: 0(n)
def twoSum(nums, target):
dict = {}
for i in range(len(nums)):
comp = target - nums[i]
if comp in dict:
return [i, dict[comp]]
dict[nums[i]] = i
return -1
use a HM to find the compliment
2. Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
def containsDuplicate(nums):
dict = {}
for num in nums:
if num not in dict:
dict[num] = 1
else:
return True
return False
simple boolean manipulation, not keeping track of indicies
3. Best Time To Buy and Sell Stock
You 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.
We can’t sell before we buy, time: 0(n) | space: 0(1)
def maxProfit(prices):
left = 0 #Buy
right = 1 #Sell
max_profit = 0
while right < len(prices):
currentProfit = prices[right] - prices[left]
#our current Profit
if prices[left] < prices[right]:
max_profit =max(currentProfit,max_profit)
else:
left = right
right += 1
return max_profit
the trick is one after the other pointers, buy left sell right
4. Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
more than one way to solve, but this simple one liner is the easiest
**5. Valid Parenthesis **
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 3:
Input: s = “(]”
Output: false
def isValid(str):
stack = []
comp = {'}': '{', ')': '(', ']': '['}
for i in str:
if i in ['{', '[', '(']: # if we see an open bracket, add to the stack
stack.append(i)
else:
if stack:
if comp[i] == stack[-1]: # if curr element == open bracket, remove
stack.pop()
else:
return False
else:
return False
return True if len(stack) == 0 else False
save a copy of the valid parenthesis in a variable, utilize a stack
6. Maximum Sub Array
Given an integer array nums, find the subarray which has the largest sum and return its sum.
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.
def maxSubArray(nums):
max_sum = nums[0]
curr_sum = 0
if len(nums) < 0:
return 0
for win_end in nums:
if curr_sum < 0:
curr_sum = 0
curr_sum += win_end
max_sum = max(max_sum, curr_sum)
return max_sum
sliding window algorithm, dynamic window
7. Product of Array EXCEPT Self
Given 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]
def productExceptSelf(nums):
right = 1
output = [1] * (len(nums))
for i in range(0, len(nums)-1):
output[i+1] = output[i] * nums[i]
for i in range(len(nums)-1, -1, -1):
output[i] = output[i] * right
right = right * nums[i]
return output
double non-nested for loop
8. Three Sum
Given 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]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
def threeSum(nums):
res = []
nums.sort()
for i, a in enumerate(nums):
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res
Must sort the input array, skip dupes, look for 0, will have neg - #’s
9. Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
def merge(intervals):
merged = []
intervals.sort(key = lambda x : x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return merged
interval sort lambda func, merge the start of ‘l’ with end of ‘r’
10. Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Input: strs = [””]
Output: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
time: 0(n^2)
space: 0(n)
def groupAnagrams(strs):
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
ans[tuple(count)].append(s)
return ans.values()
requires a collections import of default dic, and ord func, tuple
** BONUS 1: 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.
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.
time: 0(n) | space: 0(1)
def maxProduct(nums):
global_max = prev_max = prev_min = nums[0]
for num in nums[1:]:
curr_min = min(prev_max*num, prev_min*num, num)
curr_max = max(prev_max*num, prev_min*num, num)
global_max= max(global_max, curr_max)
prev_max = curr_max
prev_min = curr_min
return global_maxBONUS 2: Search in Rotated Sorted Array
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.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
time: 0(logn) | space: 0(1)
def search(nums, target):
n = len(nums)
left, right = 0, n - 1
if n == 0: return -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target: return mid
# inflection point to the right. Left is strictly increasing
if nums[mid] >= nums[left]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# inflection point to the left of me. Right is strictly increasing
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
