Week 2 of Blind 50 Flashcards
1. Reverse A Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
time: 0(n) | space: 0(1)
def reverseList(head):
prev = None
curr = head
while(curr is not None):
next = curr.next
curr.next = prev
prev = curr
curr = next
head = prev
return head
must start at head, prev pointer starts at None, while curr not None
2. Detect A Cycle In A Linked List
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
time: 0(n) | space: 0(1)
def hasCycle(self, head):
fast, slow = head, head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
fast & slow pointers, check to be sure can move fast pointer, s == f: T
if our slow ever catches our fast we have found a cycle, else return False
3. Container With The Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
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.
def maxArea(height):
l, r = 0, len(height) - 1
res = 0
while l < r:
res = max(res, min(height[l], height[r]) * (r - l))
if height[l] < height[r]:
l += 1
elif height[r] <= height[l]:
r -= 1
return res
kind of needs to be approached like a Matrix conceptually, for results
4. Find Minimum in Rotated Sorted Array
Suppose 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 rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
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.
time: 0(log n) | space:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
def findMin(nums):
if len(nums) == 1:
return nums[0]
left = 0
right = len(nums) -1
if nums[right] > nums[0]:
return nums[0]
while right >= left:
mid = left + (right - left) // 2
if nums[mid] > nums[mid +1]:
return nums[mid +1]
if nums[mid - 1] > nums[mid]:
return nums[mid]
if nums[mid] > nums[0]:
left = mid + 1
else:
right = mid - 1
modified binary search,
Be careful with this problem, indention matters, we are basically using binary search and clever math. All the elements to the left of inflection point > first element of the array. All the elements to the right of inflection point < first element of the array.
5. Longest Repeating W/ Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations
time: 0(n) | space: 0(26) //or 0(1)
def characterReplacement(s, k):
count = {}
res = 0
win_start = 0 # left pointer
max_freq = 0 # keeping track of the max freq count
for win_end in range(len(s)):
count[s[win_end]] = 1 + count.get(s[win_end], 0)
max_freq = max(max_freq, count[s[win_end]])
while(win_end - win_start +1) - max_freq >k:
count[s[win_start]] -= 1
win_start += 1
res = max(res, win_end - win_start +1)
return res 6. Longest Substring Without Repeating Characters
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.
time: 0(
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
islands = 0
visit = set()
def bfs(r,c):
q = collections.deque()
q.append((r, c))
visit.add((r, c))
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while q:
row, col = q.popleft()
for dr, dc in direction:
r = row + dr
c = col + dc
if (r in range(rows) and c in range(cols) and grid[r][c] == "1" and (r, c) not in visit):
q.append((r,c))
visit.add((r,c))
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r,c) not in visit:
bfs(r,c)
islands += 1
return islands7. Remove Nth Node From End Of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
def removeNthFromEnd(head, n):
fast, slow = head, head
for i in range(n):
fast=fast.next
if not fast:return head.next
while fast.next:
slow=slow.next
fast=fast.next
slow.next=slow.next.next
return head8. Palindromic Substrings
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
def countSubstrings(self, s):
count = 0
def pal(s,l,r):
count = 0
while l>=0 and r<len(s) and s[l] == s[r]:
count +=1
l -=1
r +=1
return count
for i in range(len(s)):
count += pal(s,i,i) # for odd palindroms
count += pal(s,i,i+1) #for even palindroms
return count9. 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.
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prevHeight):
if (
(r, c) in visit
or r < 0
or c < 0
or r == ROWS
or c == COLS
or heights[r][c] < prevHeight
):
return
visit.add((r, c))
dfs(r + 1, c, visit, heights[r][c])
dfs(r - 1, c, visit, heights[r][c])
dfs(r, c + 1, visit, heights[r][c])
dfs(r, c - 1, visit, heights[r][c])
for c in range(COLS):
dfs(0, c, pac, heights[0][c])
dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
for r in range(ROWS):
dfs(r, 0, pac, heights[r][0])
dfs(r, COLS - 1, atl, heights[r][COLS - 1])
res = []
for r in range(ROWS):
for c in range(COLS):
if (r, c) in pac and (r, c) in atl:
res.append([r, c])
return res10. Medium Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window
substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
Example 2:
Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.
def minWindow(self, s, t):
if t == "":
return ""
countT, window = {}, {}
for c in t:
countT[c] = 1 + countT.get(c, 0)
have, need = 0, len(countT)
res, resLen = [-1, -1], float("infinity")
l = 0
for r in range(len(s)):
c = s[r]
window[c] = 1 + window.get(c, 0)
if c in countT and window[c] == countT[c]:
have += 1
while have == need:
# update our result
if (r - l + 1) < resLen:
res = [l, r]
resLen = r - l + 1
# pop from the left of our window
window[s[l]] -= 1
if s[l] in countT and window[s[l]] < countT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l : r + 1] if resLen != float("infinity") else ""
