class Solution(object):

# python_1_to_1000/001_Two_Sum.py def lengthOfLongestSubstring(self, s):

"""
_author_ = 'jake' :type s: str
_project_ = 'leetcode' :rtype: int
"""
# https://leetcode.com/problems/two-sum/ last_seen = {} # mapping from character to its last seen index in s
# Given an array of integers, return indices of the two numbers start = 0 # start index of current substring
# such that they add up to a specific target. longest = 0
# You may assume that each input would have exactly one solution.
for i, c in enumerate(s):
# Maintain a mapping from each number to its index.
# Check if target - num has already been found. if c in last_seen and last_seen[c] >= start:
# Time - O(n) # start a new substring after the previous sighting of c
# Space - O(n) for the dictionary start = last_seen[c] + 1
else:
class Solution(object): longest = max(longest, i - start + 1)
def twoSum(self, nums, target):
""" last_seen[c] = i # update the last sighting index
:type nums: List[int]
:type target: int return longest
:rtype: List[int]
"""

num_to_index = {} # key is number, value is index in nums # python_1_to_1000/004_Median_of_Two_Sorted_Arrays.py - h

for i, num in enumerate(nums): _author_ = 'jake'

_project_ = 'leetcode'
if target - num in num_to_index:
return [num_to_index[target - num], i] # https://leetcode.com/problems/median-of-two-sorted-arrays/
# There are two sorted arrays nums1 and nums2 of size m and n respectively.
num_to_index[num] = i # Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

return [] # no sum # Find the middle element if sum of input list lengths is odd, or else the average of the middle pair.
# get_kth_smallest recusively removes k//2 elements from one list.
# Time - O(log(m+n)), half of the elements smaller than median are removed each recursive call.
# Space - O(log(m+n)) for the recursive call stack.
# python_1_to_1000/002_Add_Two_Numbers.py - m
class Solution(object):
_author_ = 'jake' def findMedianSortedArrays(self, A, B):
_project_ = 'leetcode' """
:type A: List[int]
# https://leetcode.com/problems/add-two-numbers/ :type B: List[int]
# You are given two linked lists representing two non-negative numbers. :rtype: float
# The digits are stored in reverse order and each of their nodes contain a single digit. """
# Add the two numbers and return it as a linked list. def get_kth_smallest(a_start, b_start, k):

# Iterate over lists. Add to result a node with the the sum of input nodes plus carry, mod 10. if k <= 0 or k > len(A) - a_start + len(B) - b_start:
# Time - O(max(m,n)) where m and n are input list lengths. raise ValueError('k is out of the bounds of the input lists')
# Space - O(max(m,n)), output will be at most one digit more than longest input.
# base cases
# Definition for singly-linked list. if a_start >= len(A):
class ListNode(object): return B[b_start + k - 1]
def __init__(self, x): if b_start >= len(B):
self.val = x return A[a_start + k - 1]
self.next = None if k == 1:
return min(A[a_start], B[b_start])
class Solution(object):
def addTwoNumbers(self, l1, l2): # remove k//2 elements from one list
""" # find the smallest of the k//2 - 1th element from both lists and recurse having reduced that list.
:type l1: ListNode # k//2 - 1th element must exist in at least 1 list
:type l2: ListNode mid_A, mid_B = float('inf'), float('inf')
:rtype: ListNode if k // 2 - 1 < len(A) - a_start:
""" mid_A = A[a_start + k // 2 - 1]
prev = result = ListNode(None) # dummy head if k // 2 - 1 < len(B) - b_start:
carry = 0 mid_B = B[b_start + k // 2 - 1]

while l1 or l2 or carry: if mid_A < mid_B:

if l1: return get_kth_smallest(a_start + k // 2, b_start, k - k // 2)
carry += l1.val return get_kth_smallest(a_start, b_start + k // 2, k - k // 2)
l1 = l1.next
if l2: right = get_kth_smallest(0, 0, 1 + (len(A) + len(B)) // 2)
carry += l2.val if (len(A) + len(B)) % 2 == 1: # odd total length
l2 = l2.next return right
prev.next = ListNode(carry % 10)
prev = prev.next left = get_kth_smallest(0, 0, (len(A) + len(B)) // 2)
carry //= 10 return (left + right) / 2.0

return result.next

# python_1_to_1000/005_Longest_Palindromic_Substring.py - m
# python_1_to_1000/003_Longest_Substring_Without_Repeating_Characters.py - m
_author_ = 'jake'
_author_ = 'jake' _project_ = 'leetcode'
_project_ = 'leetcode'
# https://leetcode.com/problems/longest-palindromic-substring/
# https://leetcode.com/problems/longest-substring-without-repeating-characters/ # Given a string S, find the longest palindromic substring in S.
# Given a string, find the length of the longest substring without repeating characters. # You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

# Maintain a sliding window, updating the start whenever we see a character repeated. # For each centre point of a character or between 2 characters,
# Time - O(n) # expand the palindrome if the end characters are the same.
# Space - O(1), dictionary is limited by fixed size alphabet # Return early by starting with the middle centre and ruling out later centres that could not have longer
# substring than the palindrome already found.

# Time - O(n^2), 2n centres, each expanded upto n times # Example2: x = -123, return -321
# Space - O(n) to store the result
# Repeatedly multiply previous result by 10 and add last digit.
# Note that Manacher's algorithm provides a O(n) time solution. # Time - O(n) where n is the number of digits.
# Space - O(n), same number of digits in output as input.
class Solution(object):
def longestPalindrome(self, s): class Solution(object):
""" def reverse(self, x):
:type s: str """
:rtype: str :type x: int
""" :rtype: int
longest = "" """
negative = x < 0 # record if negative and change to positive
# create list of 2n-1 possible centres, each letter and between each pair x = abs(x)
# even indices represent letters, odd represent between letters reversed = 0
# start with middle index that potentially creates longest palindrome
centres = [len(s) - 1] while x != 0:
for diff in range(1, len(s)): # build list of indices from long to short reversed = reversed * 10 + x % 10
centres.append(centres[0] + diff) x //= 10
centres.append(centres[0] - diff)
if reversed > 2**31 - 1: # required to pass leetcode test cases, not applicable for python
for centre in centres: return 0
return reversed if not negative else -reversed
if (min(centre + 1, 2 * len(s) - 1 - centre) <= len(longest)):
break # return if cannot make a longer palindrome

if centre % 2 == 0:
left, right = (centre // 2) - 1, (centre // 2) + 1
else: # python_1_to_1000/008_String_to_Integer_(atoi).py - m
left, right = centre // 2, (centre // 2) + 1
_author_ = 'jake'
while left >= 0 and right < len(s) and s[left] == s[right]: _project_ = 'leetcode'
left -= 1
right += 1 # https://leetcode.com/problems/string-to-integer-atoi/
# left and right are now beyond the ends of the substring # Implement atoi to convert a string to an integer.
# Notes: It is intended for this problem to be specified vaguely (ie, no given input specs).
if right - left - 1 > len(longest): # You are responsible to gather all the input requirements up front.
longest = s[left + 1:right]
# Return the integer upto any non-digit.
return longest # Time - O(n)
# Space - O(n), new str created by strip()

# python_1_to_1000/006_ZigZag_Conversion.py - m class Solution(object):

def myAtoi(self, str):
_author_ = 'jake' """
_project_ = 'leetcode' :type str: str
:rtype: int
# https://leetcode.com/problems/zigzag-conversion/ """
# The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: str = str.strip() # remove padding spaces
# P A H N
# A P L S I I G negative = False # remove leading + or -
# Y I R if str and str[0] == '-':
# And then read line by line: "PAHNAPLSIIGYIR" negative = True
# Write the code that will take a string and make this conversion given a number of rows. if str and (str[0] == '+' or str[0] == '-'):
str = str[1:]
# Build a list of chars for each row by tracking the direction of movement up or down and if not str:
# reversing direction at end rows. return 0
# Time - O(n), use a list of chars and join instead of adding to immutable strings.
# Space - O(n) digits = {i for i in '0123456789'}
result = 0
class Solution(object): for c in str: # record integer upto first non-digit
def convert(self, s, numRows): if c not in digits:
""" break
:type s: str result = result * 10 + int(c)
:type numRows: int
:rtype: str if negative:
""" result = -result
if numRows == 1:
return s result = max(min(result, 2**31 - 1), -2**31) # keep within 4 byte signed integer bounds
return result
zigzag = [[] for _ in range(numRows)]
row = 0
direction = -1 # -1 for up, +1 for down
# python_1_to_1000/009_Palindrome_Number.py
for c in s:
zigzag[row].append(c) _author_ = 'jake'
if row == 0 or row == numRows-1: # change direction _project_ = 'leetcode'
direction = -direction
row += direction # https://leetcode.com/problems/palindrome-number/
# Determine whether an integer is a palindrome. Do this without extra space.
return "".join([c for r in zigzag for c in r]) # flatten list of lists
# Check equivalence of first and last characters, moving inwards.
# Time - O(n)
# Space - O(1)
# python_1_to_1000/007_Reverse_Integer.py - m
class Solution(object):
_author_ = 'jake' def isPalindrome(self, x):
_project_ = 'leetcode' """
:type x: int
# https://leetcode.com/problems/reverse-integer/ :rtype: bool
# Reverse digits of an integer. """
# Example1: x = 123, return 321 s = str(x)
 left, right = 0, len(s)-1 # Input is guaranteed to be within the range from 1 to 3999.

while left < right: # Repeatedly take of as many copies of each numeral as possible until num is less than
if s[left] != s[right]: # the value of that numeral.
return False # Time - O(n) where n = len(str(num)), the longest roman equivalent is 8 where one digit maps to 4 chars
left += 1 # Space - O(n)
right -=1
class Solution(object):
return True def intToRoman(self, num):
"""
:type num: int
# python_1_to_1000/010_Regular_Expression_Matching.py - h :rtype: str
"""
_author_ = 'jake' mapping = [(1000, 'M'),
_project_ = 'leetcode' (900, 'CM'),
(500, 'D'),
# https://leetcode.com/problems/regular-expression-matching/ (400, 'CD'),
# Implement regular expression matching with support for '.' and '*'. (100, 'C'),
# '.' Matches any single character. (90, 'XC'),
# '*' Matches zero or more of the preceding element. (50, 'L'),
# The matching should cover the entire input string (not partial). (40, 'XL'),
(10, 'X'),
# Dynamic programming calculation of matrix of whether any prefix of s patches any prefix of p. (9, 'IX'),
# Time - O(m*n) when m = len(p) and n = len(s) (5, 'V'),
# Space - O(m*n) (4, 'IV'),
(1, 'I'),]
class Solution(object):
def isMatch(self, s, p): roman = []
for i, numeral in mapping:
# matched[i][j] is True if the first i chars of s (i.e. s[:i]) matches the first j chars of p (i.e. p[:j]) while num >= i:
matched = [[False for _ in range(len(p)+1)] for _ in range(len(s)+1)] num -= i
matched[0][0] = True # no pattern (j=0) matches no string and not any non-zero string roman.append(numeral)

for i in range(len(s)+1): return "".join(roman)

for j in range(1, len(p)+1):
pattern = p[j-1]

if pattern == '.': # dot matches any last character of s # python_1_to_1000/013_Roman_to_Integer.py

matched[i][j] = (i != 0 and matched[i-1][j-1])
_author_ = 'jake'
elif pattern == '*': # either ignore last 2 chars of p, or ignore last char of s provided it _project_ = 'leetcode'
star = p[j-2] # matches the star char
matched[i][j] = matched[i][j-2] or (i > 0 and matched[i-1][j] and (star == s[i-1] or star == '.')) # https://leetcode.com/problems/roman-to-integer/
# Given a roman numeral, convert it to an integer.
else: # pattern must match the last character of s # Input is guaranteed to be within the range from 1 to 3999.
matched[i][j] = (i != 0 and matched[i-1][j-1] and s[i-1] == pattern)
# Iterate along s, checking if the next 2 characters match any valid roman numeral.
return matched[-1][-1] # If so, add the value of the numeral to the result. Otherwise the next single
# character must match a numeral, which is added to the result.
# Time - O(n)
# Space - O(1)
# python_1_to_1000/011_Container_With_Most_Water.py - m
class Solution(object):
_author_ = 'jake' def romanToInt(self, s):
_project_ = 'leetcode' """
:type s: str
# https://leetcode.com/problems/container-with-most-water/ :rtype: int
# Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai), """
# n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). doubles = {'CM' : 900, 'CD' : 400, 'XC' : 90, 'XL' : 40, 'IX' :9, 'IV' : 4}
# Find two lines, which together with x-axis forms a container, such that the container contains the most water. singles = {'M' : 1000, 'D' : 500, 'C' : 100, 'L' : 50, 'X' : 10, 'V' : 5, 'I' : 1}

# Start with the widest separation of lines. To form a greater area, any lesser separation must have a greater integer = 0
# minimum boundary height. i = 0
# Time - O(n) while i < len(s):
# Space - O(1) if i < len(s) - 1 and s[i:i + 2] in doubles:
integer += doubles[s[i:i + 2]]
class Solution(object): i += 2
def maxArea(self, height): else:
""" integer += singles[s[i]]
:type height: List[int] i += 1
:rtype: int
""" return integer
left = 0
right = len(height)-1
max_area = (right - left) * min(height[right], height[left])
# python_1_to_1000/014_Longest_Common_Prefix.py
while left < right:
if height[left] < height[right]: # By moving in the lower boundary we have the possibility _author_ = 'jake'
left += 1 # of finding a larger area. _project_ = 'leetcode'
else:
right -= 1 # https://leetcode.com/problems/longest-common-prefix/
max_area = max(max_area, (right - left) * min(height[right], height[left])) # Write a function to find the longest common prefix string amongst an array of strings.

return max_area # Sort strings and find longest prefix of first and last, which are the most different.
# Alternatively all strings could be inserted into a trie and we find the first node
# with more than one child.
# python_1_to_1000/012_Integer_to_Roman.py - m # Time - O(k*n logn) where k is the length of the longest string and n is number of strings.
# Space - O(1)
_author_ = 'jake'
_project_ = 'leetcode' class Solution(object):
def longestCommonPrefix(self, strs):
# https://leetcode.com/problems/integer-to-roman/ """
# Given an integer, convert it to a roman numeral. :type strs: List[str]

:rtype: str :type target: int

""" :rtype: int
if not strs: """
return '' nums.sort()
closest = float('inf') # default if len(nums) < 3
strs.sort()
first = strs[0] for i in range(len(nums) - 2):
last = strs[-1] j = i + 1
k = len(nums) - 1
i = 0
while i < len(first) and i < len(last) and first[i] == last[i]: while j < k:
i += 1
return first[:i] triple = nums[i] + nums[j] + nums[k]
if triple == target: # early return, cannot do better
return target
if abs(triple - target) < abs(closest - target):
# python_1_to_1000/015_3Sum.py - m closest = triple

_author_ = 'jake' if triple - target > 0:

_project_ = 'leetcode' k -= 1
else:
# https://leetcode.com/problems/3sum/ j += 1
# Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
# Find all unique triplets in the array which gives the sum of zero. return closest
# Note: The solution set must not contain duplicate triplets.

# Sort the array. For each index i perform a bidirectional search on the higher values in the array.
# Skip over duplicates. Increment i to the next new minimum number. # python_1_to_1000/017_Letter_Combinations_of_a_Phone_Number.py - m
# Time - O(n**2), for each i at least one of j and k moves every iteration.
# Space - O(n) _author_ = 'jake'
_project_ = 'leetcode'
class Solution(object):
def threeSum(self, nums): # https://leetcode.com/problems/letter-combinations-of-a-phone-number/
""" # Given a digit string, return all possible letter combinations that the number could represent.
:type nums: List[int]
:rtype: List[List[int]] # For each digit add all possible letter mappings to each of the previous results.
""" # Alternatively can be solved recursively.
results = [] # Time - O(n * 4^n)
nums.sort() # Space - O(n * 4^n), max 4 possible chars per digit so O(4^n) strings each of length n

i = 0 class Solution(object):
while i < len(nums): def letterCombinations(self, digits):
j = i + 1 """
k = len(nums) - 1 :type digits: str
:rtype: List[str]
while j < k: """
if not digits or '0' in digits or '1' in digits:
triple_sum = nums[i] + nums[j] + nums[k] return []

if triple_sum == 0: # record result and move both j and k to next new numbers results = [[]]
results.append([nums[i], nums[j], nums[k]]) mapping = {'2' : ['a', 'b', 'c'],
k -= 1 '3' : ['d', 'e', 'f'],
while k > j and nums[k] == nums[k + 1]: '4' : ['g', 'h', 'i'],
k -= 1 '5' : ['j', 'k', 'l'],
j += 1 '6' : ['m', 'n', 'o'],
while j < k and nums[j] == nums[j - 1]: '7' : ['p', 'q', 'r', 's'],
j += 1 '8' : ['t', 'u', 'v'],
'9' : ['w', 'x', 'y' , 'z']}
elif triple_sum > 0: # decrement k to next new number
k -= 1 for digit in digits:
while k > j and nums[k] == nums[k + 1]: temp = []
k -= 1 for result in results:
else: # increment j to next new number for letter in mapping[digit]:
j += 1 temp.append(result + [letter])
while j < k and nums[j] == nums[j - 1]: results = temp
j += 1
# convert lists of chars to strings
i += 1 # increment i to next new number return ["".join(result) for result in results]
while i < len(nums) - 2 and nums[i] == nums[i - 1]:
i += 1
# python_1_to_1000/018_4Sum.py - m
return results
_author_ = 'jake'
_project_ = 'leetcode'

# https://leetcode.com/problems/4sum/
# python_1_to_1000/016_3Sum_Closest.py - m # Given an array nums of n integers, are there elements a, b, c, and d in nums such that a + b + c + d = target?
# Find all unique quadruplets in the array which gives the sum of target.
_author_ = 'jake' # Note: The solution set must not contain duplicate quadruplets.
_project_ = 'leetcode'
# Recursively reduce to 2sum problem.
# https://leetcode.com/problems/3sum-closest/ # Time - O(n^3), for each pair perform linear search on the rest of the array
# Given an array nums of n integers, find three integers in nums such that the sum is closest to a given number, target.
# Return the sum of the three integers. You may assume that each input would have exactly one solution. class Solution(object):
ELEMENTS = 4 # parametrise the number of elements being summed
# Sort the array. For each staring index bidirectional search in the rest of the array.
# Time - O(n**2) def fourSum(self, nums, target):
# Space - O(1) """
:type nums: List[int]
class Solution(object): :type target: int
def threeSumClosest(self, nums, target): :rtype: List[List[int]]
""" """
:type nums: List[int] results = []
 self.n_sum(sorted(nums), target, [], self.ELEMENTS, results) for c in s:
return results if c in match:
stack.append(c)
else:
def n_sum(self, nums, target, partial, n, results): # generalise for n-sum if not stack or match[stack.pop()] != c:
return False
if len(nums) < n or target > nums[-1]*n or target < nums[0]*n: # early return if impossible
return return not stack

if n == 2: # base case of linear bidirectional search for n == 2

left = 0
right = len(nums)-1 # python_1_to_1000/021_Merge_Two_Sorted_Lists.py
while left < right:
if nums[left] + nums[right] == target: _author_ = 'jake'
results.append(partial + [nums[left], nums[right]]) _project_ = 'leetcode'
left += 1
right -= 1 # https://leetcode.com/problems/merge-two-sorted-lists/
while nums[right] == nums[right+1] and right > left: # move to next different number if target # Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes
found of the first two lists.
right -=1
elif nums[left] + nums[right] < target: # Whilst there are nodes in both lists, link to lowest head node and increment that list. Finally link to
left += 1 # the list with remaining nodes.
else: # Time - O(m+n)
right -= 1 # Space - O(1)

else: # Definition for singly-linked list.

for i in range(len(nums)-n+1): # for all possible first numbers nums[i] class ListNode(object):
if i == 0 or nums[i] != nums[i-1]: # if not duplicate def __init__(self, x):
self.n_sum(nums[i+1:], target-nums[i], partial + [nums[i]], n-1, results) self.val = x
self.next = None

class Solution(object):
# python_1_to_1000/019_Remove_Nth_Node_From_End_of_List.py - m def mergeTwoLists(self, l1, l2):

_author_ = 'jake' prev = dummy = ListNode(None) # new dummy head for the merged list
_project_ = 'leetcode'
while l1 and l2: # link prev to the lowest node
# https://leetcode.com/problems/remove-nth-node-from-end-of-list/
# Given a linked list, remove the nth node from the end of list and return its head. if l1.val < l2.val:
prev.next = l1
# Advance first pointer n steps then advance both pointers at same rate. l1 = l1.next
# Time - O(n) else:
# Space - O(1) prev.next = l2
l2 = l2.next
# Definition for singly-linked list.
# class ListNode(object): prev = prev.next
# def __init__(self, x):
# self.val = x prev.next = l1 or l2 # link prev to the list with remaining nodes
# self.next = None return dummy.next

class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode # python_1_to_1000/022_Generate_Parentheses.py - m
:type n: int
:rtype: ListNode _author_ = 'jake'
""" _project_ = 'leetcode'
first, second = head, head
# https://leetcode.com/problems/generate-parentheses/
for i in range(n): # move first n steps forwards # Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
first = first.next
if not first: # Recursively add an opening left bracket if any remain, and a closing right bracket if more left brackets have been
return head.next used.
# Time - O(2^n), each recursion can generate 2 recursive calls althougn in practive this is an upper bound
while first.next: # move both pointers until first is at end # Space - O(2^n)
first = first.next
second = second.next class Solution(object):
second.next = second.next.next # nth from end is second.next def generateParenthesis(self, n):
return head """
:type n: int
:rtype: List[str]
# python_1_to_1000/020_Valid_Parentheses.py """
result = []
_author_ = 'jake' self.generate([], n, n, result)
_project_ = 'leetcode' return result

# https://leetcode.com/problems/valid-parentheses/ # Generates all parentheses given a starting prefix and remaining left and right brackets.
# Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. def generate(self, prefix, left, right, result):
# The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. if left == 0 and right == 0:
result.append("".join(prefix))
# Maintain a stack of opening brackets. For each closing bracket pop the head of the stack and check it matches. if left != 0:
# Time - O(n) self.generate(prefix + ['('], left-1, right, result)
# Space - O(n) if right > left:
self.generate(prefix + [')'], left, right-1, result)
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool # python_1_to_1000/023_Merge_k_Sorted_Lists.py - h
"""
stack = [] _author_ = 'jake'
match = {'(' : ')', '[' : ']', '{' : '}'} _project_ = 'leetcode'

# https://leetcode.com/problems/merge-k-sorted-lists/ # You may not alter the values in the nodes, only nodes itself may be changed.
# Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. # Only constant memory is allowed.

# Maintain a min heap of tuples of (val, list index) for the next node in each list. # If there are at least k nodes, recursively reverse remainder and append reversed group to reversed remainder.
# Also maintain a list of the next node to be merged for each list index. # Time - O(n)
# Time - O(n log k) for n total nodes, each of which is pushed and popped from heap in log k time. # Space - O(1)
# Space - O(k) for heap of k nodes
class Solution(object):
# Definition for singly-linked list. def reverseKGroup(self, head, k):
class ListNode(object): """
def __init__(self, x): :type head: ListNode
self.val = x :type k: int
self.next = None :rtype: ListNode
"""
import heapq if k < 2:
return head
class Solution(object):
def mergeKLists(self, lists): node = head
""" for _ in range(k):
:type lists: List[ListNode] if not node:
:rtype: ListNode return head # return head if there are not at least k nodes
""" node = node.next
prev = dummy = ListNode(None) # else node is now head of second group
next_nodes, heap = [], []
# reverse remainder after this group
for i, node in enumerate(lists): prev = self.reverseKGroup(node, k)
next_nodes.append(node) # next_nodes[i] is the next node to be merged from lists[i]
if node: for _ in range(k): # reverse this group, adding in front of prev
heap.append((node.val, i)) temp = head.next
heapq.heapify(heap) head.next = prev
prev = head
while heap: head = temp
value, i = heapq.heappop(heap)
node = next_nodes[i] return prev
prev.next = node # add node to merged list
prev = prev.next
if node.next: # python_1_to_1000/026_Remove_Duplicates_from_Sorted_Array.py
next_nodes[i] = node.next
heapq.heappush(heap, (node.next.val, i)) _author_ = 'jake'
_project_ = 'leetcode'
return dummy.next
# https://leetcode.com/problems/remove-duplicates-from-sorted-array/
# Given a sorted array, remove the duplicates in place such that each element appear only once and return the new
length.
# python_1_to_1000/024_Swap_Nodes_in_Pairs.py - m # Do not allocate extra space for another array, you must do this in place with constant memory.

_author_ = 'jake' # Maintain a pointer to the next index to be filled with a new number. Check every number against the previous num
_project_ = 'leetcode' # (if any) and if different, move to the next_new index.
# Time - O(n)
# https://leetcode.com/problems/swap-nodes-in-pairs/ # Space - O(1)
# Given a linked list, swap every two adjacent nodes and return its head.
# E.g. given 1->2->3->4, you should return the list as 2->1->4->3. class Solution(object):
# Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be def removeDuplicates(self, nums):
changed. """
:type nums: List[int]
# Store the previous node, swap and append in pairs. :rtype: int
# Time - O(n) """
# Space - O(1) next_new = 0 # index where the next unique number is to be moved to

# Definition for singly-linked list. for i in range(len(nums)):

class ListNode(object): if i == 0 or nums[i] != nums[i - 1]:
def __init__(self, x): nums[next_new] = nums[i]
self.val = x next_new += 1
self.next = None
return next_new
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode # python_1_to_1000/027_Remove_Element.py
:rtype: ListNode
""" _author_ = 'jake'
prev = dummy = ListNode(None) _project_ = 'leetcode'

while head and head.next: # https://leetcode.com/problems/remove-element/

next_head = head.next.next # Given an array and a value, remove all instances of that value in place and return the new length.
prev.next = head.next # Do not allocate extra space for another array, you must do this in place with constant memory.
head.next.next = head # The order of elements can be changed. It doesn't matter what you leave beyond the new length.
prev = head
head = next_head # Maintain pointer to next index to be used for any number not equal to val.
# Time - O(n)
prev.next = head # Space - O(1)
return dummy.next
class Solution(object):
def removeElement(self, nums, val):
"""
# python_1_to_1000/025_Reverse_Nodes_in_k-Group.py - h :type nums: List[int]
:type val: int
_author_ = 'jake' :rtype: int
_project_ = 'leetcode' """
next_free = 0
# https://leetcode.com/problems/reverse-nodes-in-k-group/ for i, num in enumerate(nums):
# Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. if num != val:
# If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. nums[next_free] = num
 next_free += 1
return next_free # For each stripe, maintain a sliding window of matched words.
# Time - O(n) where n = len(s). word_len stripes, each of which we move the start or end of the matched window
# forwards n / word_len times.
# Space - O(len(words)*word_len) for dictionary
# python_1_to_1000/028_Implement_strStr().py
from collections import Counter
_author_ = 'jake'
_project_ = 'leetcode' class Solution(object):
def findSubstring(self, s, words):
# https://leetcode.com/problems/implement-strstr/ """
# Implement strStr(). :type s: str
# Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. :type words: List[str]
:rtype: List[int]
# For each pssible starting point in haystack, check characters match with needle and break if not. """
# Alternatively KMP would improve expected time complexity. result = []
# Time - O(n^2) word_len = len(words[0])
# Space - O(1)
for stripe in range(word_len): # each stripe starts at a different position in s, modulo word_len
class Solution(object):
def strStr(self, haystack, needle): i = stripe # the next index in s that we want to match a word
""" to_match = len(words) # number of words still to be matched
:type haystack: str freq = Counter(words) # frequency of each words to be matched
:type needle: str
:rtype: int while i + to_match*word_len <= len(s): # remainder of s is long enough to hold remaining unmatched words
"""
for i in range(len(haystack) - len(needle) + 1): word = s[i:i+word_len] # next part of s attempting to be matched
for j in range(len(needle)): if word in freq: # match, decrement freq count
if haystack[i + j] != needle[j]: freq[word] -= 1
break if freq[word] == 0:
else: # for/else reaches here if no break del freq[word]
return i to_match -= 1
return -1 i += word_len
if to_match == 0: # all matched
result.append(i - word_len*len(words))

# python_1_to_1000/029_Divide_Two_Integers.py - m elif to_match != len(words): # some words have been matched

nb_matches = len(words) - to_match
_author_ = 'jake' first_word = s[i - nb_matches*word_len:i - (nb_matches-1)*word_len]
_project_ = 'leetcode' freq.setdefault(first_word, 0) # put first word matched back in dictionary
freq[first_word] += 1
# https://leetcode.com/problems/divide-two-integers/ to_match += 1
# Divide two integers without using multiplication, division and mod operator.
# If overflow, return MAX_INT. else: # no words matched
i += word_len
# Repeatedly double the divisor until it would exceed the dividend. Then repeatedly halve the divisor, subtracting
# it from the dividend whenever possible. return result
# Time - O(log n)
# Space - O(1)

class Solution(object): # python_1_to_1000/031_Next_Permutation.py - m

def divide(self, dividend, divisor):
""" _author_ = 'jake'
:type dividend: int _project_ = 'leetcode'
:type divisor: int
:rtype: int # https://leetcode.com/problems/next-permutation/
""" # Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
if divisor == 0: # If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending
return None order).
diff_sign = (divisor < 0) ^ (dividend < 0) # The replacement must be in-place, do not allocate extra memory.
dividend = abs(dividend)
divisor = abs(divisor) # Starting from the last number, move forward to find the first decrease nums[i].
# Find the smallest number bigger than nums[i], nums[j]. Swap nums[i] and nums[j].
result = 0 # Reverse all from i+1 onwards, or whole array if no decrease found in first step.
max_divisor = divisor # Time - O(n)
shift_count = 1 # Space - O(1)

while dividend >= (max_divisor << 1): # find divisor * 2^i where divisor * 2^(i+1) > dividend class Solution(object):
max_divisor <<= 1 def nextPermutation(self, nums):
shift_count <<= 1 """
:type nums: List[int]
while shift_count >= 1: :rtype: void Do not return anything, modify nums in-place instead.
if dividend >= max_divisor: # subtract max_divisor whenever possible """
dividend -= max_divisor if not nums or len(nums) == 1:
result += shift_count return
shift_count >>= 1
max_divisor >>= 1 i = len(nums)-2 # starting at back, find the first decrease - increasing it will increment the permutation
while i >= 0 and nums[i] >= nums[i+1]:
if diff_sign: i -= 1
result = -result
return max(min(result, 2**31-1), -2**31) # required for leetcode if i != -1: # if any decrease then find the smallest larger number to swap with
j = i+1
while j < len(nums) and nums[j] > nums[i]:
j += 1
# python_1_to_1000/030_Substring_with_Concatenation_of_All_Words.py - h j -= 1
nums[i], nums[j] = nums[j], nums[i]
_author_ = 'jake'
_project_ = 'leetcode' # reverse all from i+1 onwards since they were decreasing and increasing minimises permutation
left = i+1
# https://leetcode.com/problems/substring-with-concatenation-of-all-words/ right = len(nums)-1
# You are given a string, s, and a list of words, words, that are all of the same length. while left < right:
# Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once nums[left], nums[right] = nums[right], nums[left]
# and without any intervening characters. left += 1

right -= 1
_author_ = 'jake'
_project_ = 'leetcode'

# python_1_to_1000/032_Longest_Valid_Parentheses.py - h # https://leetcode.com/problems/search-for-a-range
# Given a sorted array of integers, find the starting and ending position of a given target value.
_author_ = 'jake' # Your algorithm's runtime complexity must be in the order of O(log n).
_project_ = 'leetcode' # If the target is not found in the array, return [-1, -1].

# https://leetcode.com/problems/longest-valid-parentheses/ # Search for target +/- 0.5 (not integer so not found) and return the index above this.
# Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) # If same index is returned for + and - 0.5 then target not found.
parentheses substring. # Binary search could be implemented iteratively or use the bisect module.
# For example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. # Time - O(log n)
# Space - O(1)
# Maintain a stack of indices in s of unmatched brackets. Pop an opening bracket when matched with a closing bracket.
# Push unmatched closing brackets and all opening brackets. Then find the longest gap between indices on the stack. class Solution(object):
# Time - O(n) def searchRange(self, nums, target):
# Space - O(n) """
:type nums: List[int]
class Solution(object): :type target: int
def longestValidParentheses(self, s): :rtype: List[int]
""" """
:type s: str def binary(target, left, right):
:rtype: int
""" if left > right:
stack = [] # indices of brackets that are not matched return left

for i, c in enumerate(s): mid = (left + right) // 2

if c == ")" and stack and s[stack[-1]] == '(': if target > nums[mid]:
stack.pop() # close matches an open on the stack left = mid + 1
else: else:
stack.append(i) # puch open brackets or unmatched close brackets right = mid - 1

stack.append(len(s)) # last unmatched index after end of s return binary(target, left, right)
max_length = stack[0] # first unmatched index before start of s
lower = binary(target - 0.5, 0, len(nums) - 1)
for index in range(1, len(stack)): # find max gap between remaining unmatched indices upper = binary(target + 0.5, 0, len(nums) - 1)
max_length = max(max_length, stack[index] - stack[index-1] - 1) return [-1, -1] if lower == upper else [lower, upper - 1]

return max_length

# python_1_to_1000/035_Search_Insert_Position.py

_author_ = 'jake'
# python_1_to_1000/033_Search_in_Rotated_Sorted_Array.py - m _project_ = 'leetcode'

_author_ = 'jake' # https://leetcode.com/problems/search-insert-position/

_project_ = 'leetcode' # Given a sorted array and a target value, return the index if the target is found.
# If not, return the index where it would be if it were inserted in order.
# https://leetcode.com/problems/search-in-rotated-sorted-array/ # You may assume no duplicates in the array.
# Suppose a sorted array is rotated at some pivot unknown to you beforehand.
# (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). # Iterative binary search until left > right or left or right move outside array.
# You are given a target value to search. If found in the array return its index, otherwise return -1. # Return left (the greater index), which would be the new index of inserted entry (could be len(nums) but not -1).
# You may assume no duplicate exists in the array. # Time - O(log n)
# Space - O(1)
# Binary search. If one side is sorted and target is in that region then rescurse on that side or else other side.
# Time - O(log n), half of the array is eliminated for every recursion. class Solution(object):
# Space - O(1) def searchInsert(self, nums, target):
"""
class Solution(object): :type nums: List[int]
def search(self, nums, target): :type target: int
""" :rtype: int
:type nums: List[int] """
:type target: int left = 0
:rtype: int right = len(nums)
"""
left, right = 0, len(nums) - 1 while left <= right and left < len(nums) and right >= 0:
mid = (left + right) // 2
while left <= right: if target == nums[mid]:
return mid
mid = (left + right) // 2 if target < nums[mid]:
right = mid - 1
if nums[mid] == target: else:
return mid left = mid + 1

if nums[left] <= nums[mid]: # LHS is sorted return left

if target >= nums[left] and target < nums[mid]: # target is on LHS
right = mid - 1
else: # python_1_to_1000/036_Valid_Sudoku.py - m
left = mid + 1
else: # RHS is sorted _author_ = 'jake'
if target <= nums[right] and target > nums[mid]: # target is on RHS _project_ = 'leetcode'
left = mid + 1
else: # https://leetcode.com/problems/valid-sudoku/
right = mid - 1 # Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
# The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
return -1
# Create a set of digits seen in each row, column and box. False if any duplicates.
# Time - O(n^2) for board of side n
# Space - O(n)

class Solution(object):
# python_1_to_1000/034_Search_for_a_Range.py - m def isValidSudoku(self, board):
 """
:type board: List[List[str]] for r in range(self.size):
:rtype: bool for c in range(self.size):
"""
size = 9 if len(self.board[r][c]) == 1:
digits = {str(i) for i in range(1,10)} continue
rows = [set() for _ in range(size)] for digit in self.board[r][c]: # loop over possible digits
cols = [set() for _ in range(size)] if self.is_valid(r, c, digit): # will always be valid on first recursion
boxes = [set() for _ in range(size)] save_set = self.board[r][c]
self.board[r][c] = digit
for r in range(size): if self.solve_recursive():
for c in range(size): return True
self.board[r][c] = save_set # revert back
digit = board[r][c] return False
if digit == '.': return True
continue

if digit not in digits: def is_valid(self, row, col, digit): # checks whether board is valid after adding digit in row, col
return False for i in range(self.size): # row and column
if self.board[row][i] == digit or self.board[i][col] == digit:
box = (size//3) * (r // (size//3)) + (c // (size//3)) return False
if digit in rows[r] or digit in cols[c] or digit in boxes[box]:
return False n = self.size // 3
rows[r].add(digit) for r in range(n*(row//n), n + n*(row//n)): # box
cols[c].add(digit) for c in range(n*(col//n), n + n*(col//n)):
boxes[box].add(digit) if self.board[r][c] == digit:
return False
return True return True

# python_1_to_1000/037_Sudoku_Solver.py - h
# python_1_to_1000/038_Count_and_Say.py - m
_author_ = 'jake'
_project_ = 'leetcode' _author_ = 'jake'
_project_ = 'leetcode'
# https://leetcode.com/problems/sudoku-solver/
# Write a program to solve a Sudoku puzzle by filling the empty cells. # https://leetcode.com/problems/count-and-say/
# Empty cells are indicated by the character '.'. # The count-and-say sequence is the sequence of integers beginning as follows:
# You may assume that there will be only one unique solution. # 1, 11, 21, 1211, 111221, ...
# 21 is read off as "one 2, then one 1" or 1211.
# Convert unknown cells to a set of possible digits, initially {1..9}. # Given an integer n, generate the nth sequence.
# Repeatedly use known cells to eliminate possibilities in unknown cells. Which creates new known cells etc.
# If this does not result in a solution, recursively guess each cell from its range of possibilities. # Iterate through the previous sequence. When we see a different number, append [1, num] to the new sequence.
# When we see the same number increment its count.
class Solution(object): # Time - O(2^n), the sequence at worst doubles each step
def solveSudoku(self, board): # Space - O(2^n)
"""
:type board: List[List[str]] class Solution(object):
:rtype: void Do not return anything, modify board in-place instead. def countAndSay(self, n):
""" """
self.size = 9 :type n: int
self.board = board :rtype: str
self.new_digits = [] # new digits at start or digits found by reducing to 1 possibility """
sequence = [1]
for r in range(self.size): for _ in range(n-1):
self.board[r] = [digit for digit in self.board[r]] # convert from string to list of digits next = []
for c in range(self.size): for num in sequence:
if self.board[r][c] == '.': if not next or next[-1] != num:
self.board[r][c] = {str(i) for i in range(1, 10)} # convert dot to set of possible digits next += [1, num]
else: else:
self.new_digits.append((r, c)) next[-2] += 1
sequence = next
while self.new_digits:
for r, c in self.new_digits: return "".join(map(str, sequence))
self.eliminate(r, c) # given a new digit in (r,c), eliminate that digit from row, col and box
self.new_digits = []
self.find_new() # identify cells with only one possible digit

self.solve_recursive() # python_1_to_1000/039_Combination_Sum.py - m

_author_ = 'jake'
def eliminate(self, row, col): _project_ = 'leetcode'
for i in range(self.size):
# https://leetcode.com/problems/combination-sum/
if isinstance(self.board[i][col], set): # Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate
self.board[i][col].discard(self.board[row][col]) # discard does not cause error if element not present numbers sums to T.
if isinstance(self.board[row][i], set): # The same repeated number may be chosen from C unlimited number of times.
self.board[row][i].discard(self.board[row][col]) # All numbers (including target) will be positive integers.
# The solution set must not contain duplicate combinations.
for box_row in range(3*(row//3), 3 + 3*(row//3)):
for box_col in range(3*(col//3), 3 + 3*(col//3)): # Subtract each candidate from target as many times as possible whilst remainder is non-negative. Recurse
if isinstance(self.board[box_row][box_col], set): # each time, moving on to the next candidate.
self.board[box_row][box_col].discard(self.board[row][col]) # Time - approx f^n where f is target/average_candidate and n is the number of candidates with this nb recursions

def find_new(self): class Solution(object):

for row in range(self.size): def combinationSum(self, candidates, target):
for col in range(self.size): """
if isinstance(self.board[row][col], set) and len(self.board[row][col]) == 1: :type candidates: List[int]
self.board[row][col] = self.board[row][col].pop() :type target: int
self.new_digits.append((row,col)) :rtype: List[List[int]]
"""
result = []
def solve_recursive(self): self.helper(candidates, 0, target, [], result)

return result # Your algorithm should run in O(n) time and uses constant space

def helper(self, nums, next, target, partial, result): # If an element of nums is a positive integer that could appear in nums (1 to len(nums) inclusive) and is not in
if target == 0: # correct place (nums[i] = i+1) then swap.
result.append(partial) # Time - O(n)
return # Space - O(1)
if next == len(nums):
return class Solution(object):
def firstMissingPositive(self, nums):
i = 0 """
while target - i * nums[next] >= 0: :type nums: List[int]
self.helper(nums, next + 1, target - i * nums[next], partial + [nums[next]] * i, result) :rtype: int
i += 1 """
i = 0
while i < len(nums):

# python_1_to_1000/040_Combination_Sum_II.py - m while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:
temp = nums[nums[i]-1]
_author_ = 'jake' nums[nums[i]-1] = nums[i]
_project_ = 'leetcode' nums[i] = temp

# https://leetcode.com/problems/combination-sum-ii/ i += 1
# Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the
candidate numbers sums to T. for i, num in enumerate(nums):
# Each number in C may only be used once in the combination. if nums[i] != i+1:
# All numbers (including target) will be positive integers. return i+1
# The solution set must not contain duplicate combinations. return len(nums)+1

# Count the frequency of each number in candidates. For each number subtract all possible numbers of copies up to
# the count and without exceeding target and recurse for the next number. Alternative iterative version below.
# Time - O((f+1)^n) where f is the max frequency of any number and n is the number of distinct numbers # python_1_to_1000/042_Trapping_Rain_Water.py - h

from collections import Counter _author_ = 'jake'

_project_ = 'leetcode'
class Solution(object):
def combinationSum2(self, candidates, target): # https://leetcode.com/problems/trapping-rain-water/
""" # Given n non-negative integers representing an elevation map where the width of each bar is 1,
:type candidates: List[int] # compute how much water it is able to trap after raining.
:type target: int
:rtype: List[List[int]] # Calculate the highest elevation to the right and to the left of every bar. Min of these is the max depth of water.
""" # Subtract the bar height from the max possible depth and floor at zero.
results = [] # Time - O(n)
freq = list(Counter(candidates).items()) # Space - O(n)
self.combos(freq, 0, target, [], results)
return results class Solution(object):
def trap(self, height):
def combos(self, freq, next, target, partial, results):
if target == 0: highest_right = [0] * len(height)
results.append(partial) for i in range(len(height)-2, -1, -1):
return highest_right[i] = max(highest_right[i+1], height[i+1])
if next == len(freq):
return highest_left, depth = [0] * len(height), 0
for i in range(1, len(height)): # depth[0] will be 0 so ok for range to start at 1
for i in range(freq[next][1]+1): highest_left[i] = max(highest_left[i-1], height[i-1])
if i * freq[next][0] > target: depth += max(0, min(highest_left[i], highest_right[i]) - height[i])
break
self.combos(freq, next+1, target-i*freq[next][0], partial + [freq[next][0]]*i, results) return depth

# Iterative version of same procedure.

class Solution_Iterative(object):
def combinationSum2(self, candidates, target):
results = []
partials = [[]] # python_1_to_1000/043_Multiply_Strings.py - m
freq = list(Counter(candidates).items())
_author_ = 'jake'
for candidate, count in freq: _project_ = 'leetcode'

new_partials = [] # https://leetcode.com/problems/multiply-strings/
for partial in partials: # Given two numbers represented as strings, return multiplication of the numbers as a string.
# The numbers can be arbitrarily large and are non-negative.
partial_sum = sum(partial) # Converting the input string to integer is NOT allowed.
for i in range(count + 1): # You should NOT use internal library such as BigInteger.
if partial_sum + candidate*i < target:
new_partials.append(partial + [candidate]*i) # Create a list of each digit in the result, starting wiht the least significant digit.
elif partial_sum + candidate*i == target: # Reverse input digit order. nums1[i] * nums2[j] is added to result[i+j+1] and result[i+j]
results.append(partial + [candidate]*i) # Alternatively: return str(int(num1) * int(num2))
if partial_sum + candidate*i >= target: # Time - O(m * n) where inputs are of lengths m and n
break # Space - O(max(m,n))

partials = new_partials class Solution(object):

def multiply(self, num1, num2):
return results """
:type num1: str
:type num2: str
# python_1_to_1000/041_First_Missing_Positive.py - h :rtype: str
"""
_author_ = 'jake' num1, num2 = num1[::-1], num2[::-1] # easier to work with lowest digits first
_project_ = 'leetcode' result = [0] * (len(num1) + len(num2))

# https://leetcode.com/problems/first-missing-positive/
# Given an unsorted integer array, find the first missing positive integer. for i in range(len(num1)):
# e.g. given [1,2,0] return 3, and [3,4,-1,1] return 2.
 int1 = ord(num1[i]) - ord('0') class Solution(object):
def jump(self, nums):
for j in range(len(num2)): """
:type nums: List[int]
int2 = ord(num2[j]) - ord('0') :rtype: int
"""
tens, units = divmod(int1 * int2, 10) if len(nums) == 1:
return 0
result[i + j] += units # add units and handle carry of units
if result[i + j] > 9: start, end = 0, 0 # indices in nums of current range
result[i + j + 1] += result[i + j] // 10 max_index = 0
result[i + j] %= 10 steps = 1

result[i + j + 1] += tens # add tens and handle carry of tens while True: # will always terminate since last index is accessible
if result[i + j + 1] > 9: for i in range(start, end+1):
result[i + j + 2] += result[i + j + 1] // 10 max_index = max(max_index, i + nums[i])
result[i + j + 1] %= 10 if max_index >= len(nums)-1:
return steps
while len(result) > 1 and result[-1] == 0: # remove trailing zeros steps += 1
result.pop() start, end = end + 1, max_index
return "".join(map(str, result[::-1])) # reverse and convert to string

# python_1_to_1000/046_Permutations.py - m
# python_1_to_1000/044_Wildcard_Matching.py - m
_author_ = 'jake'
_author_ = 'jake' _project_ = 'leetcode'
_project_ = 'leetcode'
# https://leetcode.com/problems/permutations/
# https://leetcode.com/problems/wildcard-matching/ # Given a collection of distinct numbers, return all possible permutations.
# Implement wildcard pattern matching with support for '?' and '*'.
# '?' Matches any single character. # For each number, insert it at all possible places in all existing permutations.
# '*' Matches any sequence of characters (including the empty sequence). # Alternatively recursively swap every index with every greater index (and itself).
# The matching should cover the entire input string (not partial). # Time - O(n^2 * n!). n! results, each of with has n elements added, each addition taking O(n) time for list slicing
# Space - O(n *n!)
# Record index in p of star and index in s at that time. Try to match without star, if fails back up and use *
# to match one more character from s. class Solution(object):
# Time - O(m * n), * at beginning of p could match many chars in s before failing and repeatedly backtrack def permute(self, nums):
# Space - O(1) """
:type nums: List[int]
class Solution(object): :rtype: List[List[int]]
def isMatch(self, s, p): """
permutations = [[]]
i, j = 0, 0 # next indices to be matched in s and p
star = -1 # last index in p of * for num in nums:
new_permutations = []
while i < len(s): for perm in permutations:
for i in range(len(perm) + 1):
# if beyond end of pattern or pattern is unmatched letter new_permutations.append(perm[:i] + [num] + perm[i:])
if j >= len(p) or (p[j] not in {'*' , '?'} and p[j] != s[i]): permutations = new_permutations
if star == -1: # no flexibility if no star
return False return permutations
j = star + 1 # reset p to character after star
star_i += 1 # reset s to charcater after star_i, i.e. use * to match one char from s
i = star_i class Solution2(object):
def permute(self, nums):
elif p[j] == '*': # record * index in p and next index to be matched in s """
star = j :type nums: List[int]
star_i = i :rtype: List[List[int]]
j += 1 """
return self.permute_helper(nums, 0)
else: # chars match or ?, increment both
i += 1 def permute_helper(self, nums, index):
j += 1
permutations = []
while j < len(p): # any remaining characters in p can only be *
if p[j] != '*': if index >= len(nums):
return False permutations.append(nums[:]) # make a new copy to freeze nums
j += 1
return True for i in range(index, len(nums)):
nums[i], nums[index] = nums[index], nums[i] # swap with all indices >= index
permutations += self.permute_helper(nums, index + 1)
nums[i], nums[index] = nums[index], nums[i] # swap back

# python_1_to_1000/045_Jump_Game_II.py - m return permutations

_author_ = 'jake'
_project_ = 'leetcode'

# https://leetcode.com/problems/jump-game-ii/
# Given an array of non-negative integers, you are initially positioned at the first index of the array.
# Each element in the array represents your maximum jump length at that position.
# Your goal is to reach the last index in the minimum number of jumps. # python_1_to_1000/047_Permutations_II.py - m
# The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last
index.) _author_ = 'jake'
# You can assume that you can always reach the last index. _project_ = 'leetcode'

# For each index in currently accessible range, update the max_index that can be reached in one more step. # https://leetcode.com/problems/permutations-ii/
# Iterate to next range, from end of previous range to max_index. # Given a collection of numbers that might contain duplicates, return all possible unique permutations.
# Time - O(n)
# Space - O(1) # Count occurences of each unique number. Recursively append each number if still has a positive count.
# Time - O(n^2 * n!), as 046_Permutations if all numbers are unique

# Space - O(n * n!)

from collections import Counter # python_1_to_1000/050_Power_Function.py - m

class Solution(object): _author_ = 'jake'

def permuteUnique(self, nums): _project_ = 'leetcode'
"""
:type nums: List[int] # https://leetcode.com/problems/powx-n/
:rtype: List[List[int]] # Implement pow(x, n).
"""
freq = Counter(nums) # Recursively calculate (pow(x, n//2))^2 if n is even or with additional factor of x if n is odd.
permutations = [] # Time - O(log n)
self.permute_helper(len(nums), [], freq, permutations) # Space - O(log n)
return permutations
class Solution(object):
def permute_helper(self, to_add, partial, freq, permutations): def myPow(self, x, n):
if to_add == 0: """
permutations.append(partial) :type x: float
:type n: int
for item in freq: :rtype: float
if freq[item] > 0: """
freq[item] -= 1 neg = n < 0
self.permute_helper(to_add-1, partial + [item], freq, permutations) pos_result = self.pos_pow(x, abs(n))
freq[item] += 1 return 1/pos_result if neg else pos_result

def pos_pow(self, x, n):

if n == 0:
return 1
# python_1_to_1000/048_Rotate_Image.py - m
temp = self.pos_pow(x, n//2)
_author_ = 'jake' temp *= temp
_project_ = 'leetcode'
return temp if n % 2 == 0 else temp * x
# https://leetcode.com/problems/rotate-image/
# You are given an n x n 2D matrix representing an image.
# Rotate the image by 90 degrees (clockwise).
# python_1_to_1000/051_N-Queens.py - h
# Number of layer to rotate is n//2. For each item along the top side of each layer, save as temp and
# move in the item from the next side, repeating until temp is put into the last side. _author_ = 'jake'
# Alternatively - matrix[:] = list(map(list, zip(*matrix[::-1]))). Reverse the order of row, unpack, _project_ = 'leetcode'
# zip and convert back to lists.
# Time - O(n^2) # https://leetcode.com/problems/n-queens/
# Space - O(1) # The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
# Given an integer n, return all distinct solutions to the n-queens puzzle.
class Solution(object): # Each solution contains a distinct board configuration of the n-queens' placement,
def rotate(self, matrix): # where 'Q' and '.' both indicate a queen and an empty space respectively.
"""
:type matrix: List[List[int]] # For each column, place a queen in each possible row that does not conflict with an existing queen.
:rtype: void Do not return anything, modify matrix in-place instead. # Time - O(n^2 * n!), n possible rows for first col, n-1 for second ... etc. each result size n^2
""" # Space - O(n^2 * n!)
n = len(matrix)
layers = n//2 class Solution(object):
def solveNQueens(self, n):
for layer in range(layers): """
for i in range(layer, n - layer - 1): :type n: int
temp = matrix[layer][i] :rtype: List[List[str]]
matrix[layer][i] = matrix[n - 1 - i][layer] """
matrix[n - 1 - i][layer] = matrix[n - 1 - layer][n - 1- i] partials = [[]] # solutions up to current row
matrix[n - 1 - layer][n - 1 - i] = matrix[i][n - 1 - layer] for col in range(n):
matrix[i][n - 1 - layer] = temp new_partials = []
for partial in partials:
for row in range(n):
if not self.conflict(partial, row):
# python_1_to_1000/049_Group_Anagrams.py - m new_partials.append(partial + [row])
partials = new_partials
_author_ = 'jake'
_project_ = 'leetcode' results = []
for partial in partials: # convert result to strings
# https://leetcode.com/problems/anagrams/ result = [['.'] * n for _ in range(n)]
# Given an array of strings, group anagrams together. for col, row in enumerate(partial):
result[row][col] = 'Q'
# Sort the letters in each word. Use sorted words as dictionary keys, values are unsorted words. for row in range(n):
# Anagrams have equivalent sorted words. result[row] = ''.join(result[row])
# Time - O(k log k * n) for n words of length k results.append(result)
# Space - O(k * n)
return results
from collections import defaultdict
def conflict(self, partial, new_row):
class Solution(object): for col, row in enumerate(partial):
def groupAnagrams(self, strs): if new_row == row: # same row
""" return True
:type strs: List[str] col_diff = len(partial) - col
:rtype: List[List[str]] if abs(new_row - row) == col_diff: # same diagonal
""" return True
sorted_words = defaultdict(list)
return False
for word in strs:
letter_list = [c for c in word]
letter_list.sort()
sorted_word = "".join(letter_list) # python_1_to_1000/052_N-Queens_II.py - h
sorted_words[sorted_word].append(word)
_author_ = 'jake'
return list(sorted_words.values()) _project_ = 'leetcode'
 leg_count = 0 # count of steps in current direction
# https://leetcode.com/problems/n-queens-ii/
# Follow up for N-Queens problem. for _ in range(len(matrix[0]) * len(matrix)):
# Now, instead outputting board configurations, return the total number of distinct solutions.
row += d_row
# As for N-Queens except just count solutions instead of converting to boards. col += d_col
# Time - O(n!) spiral.append(matrix[row][col])
# Space - O(n!) leg_count += 1

class Solution(object): # change direction

def totalNQueens(self, n): if (d_col != 0 and leg_count == row_leg) or (d_row != 0 and leg_count == col_leg):
""" if d_col != 0:
:type n: int row_leg -= 1
:rtype: List[List[str]] else:
""" col_leg -= 1
partials = [[]] d_row, d_col = d_col, -d_row
for col in range(n): leg_count = 0
new_partials = []
for partial in partials: return spiral
for row in range(n):
if not self.conflict(partial, row):
new_partials.append(partial + [row])
partials = new_partials # python_1_to_1000/055_Jump_Game.py - m

return len(partials) _author_ = 'jake'

_project_ = 'leetcode'
def conflict(self, partial, new_row):
for col, row in enumerate(partial): # https://leetcode.com/problems/jump-game/
if new_row == row: # Given an array of non-negative integers, you are initially positioned at the first index of the array.
return True # Each element in the array represents your maximum jump length at that position.
col_diff = len(partial) - col # Determine if you are able to reach the last index.
if row + col_diff == new_row or row - col_diff == new_row:
return True # Record the maximum index that can be reached. Initially this is index 0.
return False # Iterate through nums, returning False an index cannot be reached.
# Else update the maximum index with the current index + its value (the maximum jump).
# Time - O(n)
# python_1_to_1000/053_Maximum_Subarray.py - m # Space - O(1)

_author_ = 'jake' class Solution(object):

_project_ = 'leetcode' def canJump(self, nums):
"""
# https://leetcode.com/problems/maximum-subarray/ :type nums: List[int]
# Find the contiguous subarray within an array (containing at least one number) which has the largest sum. :rtype: bool
"""
# For each num calculate the max subarray sum ending with that num as either num alone (if previous sum was -ve) or max_index = 0
# num + previous sum (if previous sum was +ve)
# Time - O(n) for i, num in enumerate(nums):
# Space - O(1) if i > max_index:
return False
class Solution(object): max_index = max(max_index, i + num)
def maxSubArray(self, nums):
""" return True
:type nums: List[int]
:rtype: int
"""
overall_max = float('-inf') # python_1_to_1000/056_Merge_Intervals.py - m
max_ending_here = 0
_author_ = 'jake'
for num in nums: _project_ = 'leetcode'
if max_ending_here > 0:
max_ending_here += num # https://leetcode.com/problems/merge-intervals/
else: # Given a collection of intervals, merge all overlapping intervals.
max_ending_here = num
overall_max = max(overall_max, max_ending_here) # Sort intervals by start points. If interval starts before previous interval ends then merge, else add to result.
# Time - O(n log n)
return overall_max # Space - O(1)

class Solution(object):
# python_1_to_1000/054_Spiral_Matrix.py - m def merge(self, intervals):
"""
_author_ = 'jake' :type intervals: List[Interval]
_project_ = 'leetcode' :rtype: List[Interval]
"""
# https://leetcode.com/problems/spiral-matrix/ intervals.sort(key=lambda x : x[0])
# Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. merged = []

# Use row_leg and col_leg to traxk the max number of moves before turning. Decrease row_leg and col_leg then turning. for interval in intervals:
# Time - O(m * n) if not merged or merged[-1][1] < interval[0]:
# Space - O(1) merged.append(interval)
else:
class Solution(object): merged[-1][1] = max(merged[-1][1], interval[1])
def spiralOrder(self, matrix): return merged
"""
:type matrix: List[List[int]]
:rtype: List[int]
""" # python_1_to_1000/057_Insert_Intervals.py - m
if not matrix or not matrix[0]:
return [] _author_ = 'jake'
_project_ = 'leetcode'
spiral = []
row, col = 0, -1 # https://leetcode.com/problems/insert-interval/
d_row, d_col = 0, 1 # movement direction # Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
row_leg, col_leg = len(matrix[0]), len(matrix)-1 # steps before change of direction # You may assume that the intervals were initially sorted according to their start times.

row += d_r
# Find all intervals strictly to the left and to the right of new interval. If any intervals in between they col += d_c
# overlap with newInterval. If any overlap, update start of newInterval with start of first overlap and
# update end with end of last overlap. return spiral
# Time - O(n)
# Space - O(1)

class Solution(object): # python_1_to_1000/060_Permutation_Sequence.py - h

def insert(self, intervals, newInterval):
""" _author_ = 'jake'
:type intervals: List[List[int]] _project_ = 'leetcode'
:type newInterval: List[int]
:rtype: List[List[int]] # https://leetcode.com/problems/permutation-sequence/
""" # The set [1,2,3,…,n] contains a total of n! unique permutations.
left, right = 0, len(intervals) - 1 # By listing and labeling all of the permutations in order, we get the following sequence (ie, for n = 3):
while left < len(intervals) and intervals[left][1] < newInterval[0]: # "123", "132", "213", "231", "312", "321"
left += 1 # Given n and k, return the kth permutation sequence.

while right >= 0 and intervals[right][0] > newInterval[1]: # Find each digit according to the ratio between k and the total number of possible permutations.
right -= 1 # Time - O(n**2) since each iteration adds one digit and O9n) for del from list
# Space - O(n) to store chars list
if left <= right:
newInterval[0] = min(newInterval[0], intervals[left][0]) from math import factorial
newInterval[1] = max(newInterval[1], intervals[right][1])
class Solution(object):
return intervals[:left] + [newInterval] + intervals[right + 1:] def getPermutation(self, n, k):
"""
:type n: int
:type k: int
# python_1_to_1000/058_Length_of_Last_Word.py :rtype: str
"""
_author_ = 'jake' chars = [str(i) for i in range(1, n+1)] # the symbols that will be permuted
_project_ = 'leetcode' permutations = factorial(n) # total number of permutations for this n
k -= 1 # change indexing to 0
# https://leetcode.com/problems/length-of-last-word/ result = []
# Given a string s consists of upper/lower-case alphabets and empty space characters ' ',
# return the length of last word in the string. while chars:
# If the last word does not exist, return 0. digit = n * k // permutations # get the first digit (range is 0 to n-1)
# Note: A word is defined as a character sequence consists of non-space characters only. result.append(chars[digit]) # map from digit to a symbol
del chars[digit] # remove that symbol
# Start at last character and decrement i. permutations //= n # repeat for next digit with decreased permutations, n and k
# Set variable end when non-blank is seen. k -= digit * permutations
# Return at next non-blank. n -= 1
# Time - O(n)
# Space - O(1) return "".join(result)

class Solution(object):
def lengthOfLastWord(self, s):
""" # python_1_to_1000/061_Rotate_List.py - m
:type s: str
:rtype: int _author_ = 'jake'
""" _project_ = 'leetcode'
i = len(s) - 1
end = -1 # https://leetcode.com/problems/rotate-list/
# Given a list, rotate the list to the right by k places, where k is non-negative.
while i >= 0:
if s[i] == ' ' and end != -1: # Count length of list, reset k to k % length (avoids repeated cycles). Connect tail of list with head and then
return end - i # break k%length steps before the old tail.
if s[i] != ' ' and end == -1: # Time - O(n), n is length of list
end = i # Space - O(1)
i -= 1
return end + 1 if end != -1 else 0 # Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
# python_1_to_1000/059_Spiral_Matrix_II.py - m self.next = None

_author_ = 'jake' class Solution(object):

_project_ = 'leetcode' def rotateRight(self, head, k):
"""
# https://leetcode.com/problems/spiral-matrix-ii/ :type head: ListNode
# Given an integer n, generate a square matrix filled with elements from 1 to n**2 in spiral order. :type k: int
:rtype: ListNode
# Change direction clockwise when edge of matrix or non-zero cell is reached. """
# Time - O(n**2) if not head:
# Space - O(n**2) return

class Solution(object): count = 1

def generateMatrix(self, n): node = head
"""
:type n: int while node.next:
:rtype: List[List[int]] node = node.next
""" count += 1
spiral = [[0 for _ in range(n)] for _ in range(n)] node.next = head # connect tail to head
row, col = 0, 0
d_r, d_c = 0, 1 to_move = count - (k % count) #nb steps to move node before breaking
while to_move > 0:
count = 1 node = node.next
while count <= n*n: to_move -= 1
spiral[row][col] = count head = node.next # new head
count += 1 node.next = None
if row+d_r < 0 or row+d_r >= n or col+d_c < 0 or col+d_c >= n or spiral[row+d_r][col+d_c] != 0:
d_r, d_c = d_c, -d_r return head
 # Note: You can only move either down or right at any point in time.

# python_1_to_1000/062_Unique_Paths.py - m # Dynamic programming, min path to a cell = cell value + min(min paths to cells above and left)
# Time - O(m * n)
_author_ = 'jake' # Space - O(n)
_project_ = 'leetcode'
class Solution(object):
# https://leetcode.com/problems/unique-paths/ def minPathSum(self, grid):
# A robot is located at the top-left corner of a m x n grid. """
# The robot can only move either down or right at any point in time. :type grid: List[List[int]]
# The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). :rtype: int
# How many possible unique paths are there? """
m = len(grid)
# Dynamic programming, nb paths = paths from above cell + paths from right cell n = len(grid[0])
# Alternatively, catalan number.
# Time - O(m * n) min_path = [float('inf') for _ in range(n + 1)]
# Space - O(n), just keep last row instead of entire grid min_path[1] = 0

class Solution(object): for row in range(1, m + 1):

def uniquePaths(self, m, n): new_min_path = [float('inf') for _ in range(n + 1)]
""" for col in range(1, n + 1):
:type m: int cols new_min_path[col] = grid[row - 1][col - 1] + min(min_path[col], new_min_path[col - 1])
:type n: int rows min_path = new_min_path
:rtype: int
""" return min_path[-1]
if m == 0 or n == 0:
return 0
# python_1_to_1000/065_Valid_Number.py - h
row_paths = [1 for _ in range(n)] # first row, one path to each column
_author_ = 'jake'
for row in range(m-1): _project_ = 'leetcode'
new_row_paths = [1] # one path to first col of each row
for col in range(1, n): # https://leetcode.com/problems/valid-number/
new_row_paths.append(new_row_paths[-1] + row_paths[col]) # Validate if a given string is numeric.
row_paths = new_row_paths # Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before
implementing one.
return row_paths[-1]
# Test if integer or float or scientific. Allow for first character signs.
# Time - O(n)
# Space - O(n)
# python_1_to_1000/063_Unique_Paths_II.py - m
class Solution(object):
_author_ = 'jake' def isNumber(self, s):
_project_ = 'leetcode' self.digits = {str(i) for i in range(10)}
s = [c for c in s.strip().lower()]
# https://leetcode.com/problems/unique-paths-ii/ if not s:
# Follow up for "Unique Paths": return False
# Now consider if some obstacles are added to the grids. How many unique paths would there be? return self.is_int(s, True) or self.is_float(s) or self.is_sci(s)
# An obstacle and empty space is marked as 1 and 0 respectively in the grid.

# Dynamic programming. Nb paths is 0 if obstacle, else paths from above + paths from left. def is_int(self, s, signed):
# Time - O(m * n) if len(s) == 0:
# Space - O(n) return False
if s[0] == '-' and signed:
class Solution(object): s = s[1:]
def uniquePathsWithObstacles(self, obstacleGrid): elif s[0] == '+' and signed:
""" s = s[1:]
:type obstacleGrid: List[List[int]] if len(s) == 0:
:rtype: int return False
"""
m = len(obstacleGrid) for c in s:
n = len(obstacleGrid[0]) if c not in self.digits:
return False
if not m or not n: return True
return 0
if obstacleGrid[0][0] or obstacleGrid[-1][-1]:
return 0 def is_float(self, s):
try:
row_paths = [0 for _ in range(n+1)] dot = s.index('.')
row_paths[1] = 1 before = s[:dot]
after = s[dot+1:]
for row in range(1, m+1):
new_row_paths = [0] if before and before[0] in '+-':
for col in range(1, n+1): before = before[1:]
if obstacleGrid[row-1][col-1]: if before and not self.is_int(before, False):
new_row_paths.append(0) return False
else: if after and not self.is_int(after, False):
new_row_paths.append(new_row_paths[-1] + row_paths[col]) return False
row_paths = new_row_paths return before or after
except:
return row_paths[-1] return False

def is_sci(self, s):

try:
# python_1_to_1000/064_Minimum_Path_Sum.py - m e = s.index('e')
before = s[:e]
_author_ = 'jake' after = s[e+1:]
_project_ = 'leetcode'
if not before or not after:
# https://leetcode.com/problems/minimum-path-sum/ return False
# Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes if not self.is_int(before, True) and not self.is_float(before):
# the sum of all numbers along its path. return False

return self.is_int(after, True) # Space - O(maxWidth * nb_lines)

except:
return False class Solution(object):
def fullJustify(self, words, maxWidth):
"""
# python_1_to_1000/066_Plus_One.py :type words: List[str]
:type maxWidth: int
_author_ = 'jake' :rtype: List[str]
_project_ = 'leetcode' """
line_chars = 0 # number of chars on current line (without spaces)
# https://leetcode.com/problems/plus-one/ line_words = [] # list of words on current line
# Given a non-negative number represented as an array of digits, plus one to the number. justified = [] # output, list of justified strings
# The digits are stored such that the most significant digit is at the head of the list.
for word in words:
# Starting from least significant digit, replace with zeros until we find the first non 9, which is incremented.
# Time - O(n) if line_chars + len(line_words) + len(word) <= maxWidth: # add word to current line
# Space - O(1) line_words.append(word)
line_chars += len(word)
class Solution(object):
def plusOne(self, digits): else: # word cannot be added to current line
""" gaps = len(line_words) - 1 # nb gaps between words
:type digits: List[int] spaces = maxWidth - line_chars # nb of spaces to make line maxWidth
:rtype: List[int] line = [line_words[0]] # list of words and spaces
""" if gaps == 0: # pad end if single word
i = len(digits)-1 line.append(" " * spaces)
while i >= 0 and digits[i] == 9:
digits[i] = 0 for line_word in line_words[1:]: # distribute spaces between other words
i -= 1 space = spaces//gaps
if spaces % gaps != 0: # round up if uneven division of spaces
if i == -1: space += 1
return [1] + digits line.append(" " * space) # add space
return digits[:i] + [digits[i]+1] + digits[i+1:] spaces -= space # reduce remaining spaces and gaps
gaps -= 1
line.append(line_word)

# python_1_to_1000/067_Add_Binary.py justified.append("".join(line))

_author_ = 'jake' line_words = [word] # add word to next line.

_project_ = 'leetcode' line_chars = len(word)

# https://leetcode.com/problems/add-binary/ final_line = " ".join(line_words) # pad final line with spaces

# Given two binary strings, return their sum (also a binary string). final_line += " " * (maxWidth - len(final_line))
justified.append(final_line)
# Starting with least significant digits, add digits. Reverse result string.
# Time - O(max(m, n)) return justified
# Space - O(1)

class Solution(object):
def addBinary(self, a, b): # python_1_to_1000/069_Sqrt(x).py
"""
:type a: str _author_ = 'jake'
:type b: str _project_ = 'leetcode'
:rtype: str
""" # https://leetcode.com/problems/sqrtx/
result = [] # Implement int sqrt(int x).
carry = 0 # Compute and return the square root of x.
i = len(a)-1
j = len(b)-1 # Newton method. Initial guess of x. Iteratively update guess to be average of previous guess and x // guess.
# Since guess is too high, x // guess is too low.
while carry or i >= 0 or j >= 0: # Terminate when guess^2 <= x.
# Time - O((log x)^3) - log x from nb iterations, log x from multiple and log x from divide
total = carry # Space - O(1)
if i >= 0:
total += int(a[i]) class Solution(object):
i -= 1 def mySqrt(self, x):
if j >= 0: """
total += int(b[j]) :type x: int
j -= 1 :rtype: int
result.append(str(total % 2)) """
carry = total // 2 guess = x
while guess * guess > x:
return "".join(result[::-1]) guess = (guess + x // guess) // 2
return guess

# python_1_to_1000/068_Text_Justification.py - h

_author_ = 'jake' # python_1_to_1000/070_Climbing_Stairs.py

_project_ = 'leetcode'
_author_ = 'jake'
# https://leetcode.com/problems/text-justification/ _project_ = 'leetcode'
# Given an array of words and a length L, format the text such that each line has exactly L characters and is fully
(left and right) justified. # https://leetcode.com/problems/climbing-stairs/
# Pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L # You are climbing a stair case. It takes n steps to reach to the top.
characters. # Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
# Extra spaces between words should be distributed as evenly as possible.
# If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned # Dynamic programming. Base cases of no ways for n <= 0, 1 way for n == 1 and 2 ways for n == 2.
more spaces than the slots on the right. # For each additional step, the number of ways is taking one step from the previous step + taking two steps from the
# For the last line of text, it should be left justified and no extra space is inserted between words. # step before that. Result is a Fibonacci sequence.
# Each word is guaranteed not to exceed L in length. # Time - O(n)
# Space - O(1)
# Fill lines with words and single spaces until full. Then justify by distributing remaining spaces
# Time - O(maxWidth * nb_lines) class Solution(object):
 def climbStairs(self, n): return edit_distance(len(word1) - 1, len(word2) - 1)
"""
:type n: int
:rtype: int
""" # python_1_to_1000/073_Set_Matrix_Zeroes.py - m
if n <= 0:
return 0 _author_ = 'jake'
if n <= 2: _project_ = 'leetcode'
return n
# https://leetcode.com/problems/set-matrix-zeroes/
stairs, prev = 2, 1 # 2 ways to reach second step, one way to reach first # Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
for _ in range(3, n + 1):
stairs, prev = stairs + prev, stairs # Record whether first row and forst col contains zero. Then use first for and first col to flag whether body of
# matrix contains a zero in that row or col.
return stairs # Time - O(m * n)
# Space - O(1)

class Solution(object):
# python_1_to_1000/071_Simplify_Path.py - m def setZeroes(self, matrix):
"""
_author_ = 'jake' :type matrix: List[List[int]]
_project_ = 'leetcode' :rtype: void Do not return anything, modify matrix in-place instead.
"""
# https://leetcode.com/problems/simplify-path/ if not matrix or not matrix[0]:
# Given an absolute path for a file (Unix-style), simplify it. return 0

# Create result stack. Go up a level if '..'. Stay at same level if '.'. rows = len(matrix)
# Time - O(n) cols = len(matrix[0])
# Space - O(n)
first_row_zero = any([True for c in range(cols) if matrix[0][c] == 0])
class Solution(object): first_col_zero = any([True for r in range(rows) if matrix[r][0] == 0])
def simplifyPath(self, path):
""" for r in range(1, rows):
:type path: str for c in range(1, cols):
:rtype: str if matrix[r][c] == 0:
""" matrix[r][0] = 0
path_list = path.split('/') # does not treat consecutive delimiters as one if delimiter specified matrix[0][c] = 0
result = []
for r in range(1, rows):
for item in path_list: if matrix[r][0] == 0:
if item == '..': # go up one level if possible for c in range(1, cols):
if result: matrix[r][c] = 0
result.pop()
elif item and item != '.': # add item to path for c in range(1, cols):
result.append(item) if matrix[0][c] == 0:
# else ignore '.' and '' for r in range(1, rows):
matrix[r][c] = 0
return '/' + '/'.join(result)
if first_row_zero:
matrix[0] = [0] * cols
# python_1_to_1000/072_Edit_Distance.py - m if first_col_zero:
for r in range(rows):
_author_ = 'jake' matrix[r][0] = 0
_project_ = 'leetcode'

# https://leetcode.com/problems/edit-distance/
# Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. # python_1_to_1000/074_Search_a_2D_Matrix.py - m
# You have the following 3 operations permitted on a word (each 1 step):
# a) Insert a character _author_ = 'jake'
# b) Delete a character _project_ = 'leetcode'
# c) Replace a character
# https://leetcode.com/problems/search-a-2d-matrix/
# Dynamic programming. Base case if either string is empty, return unmatched length of other string. # Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
# If last characters matched then same cost as matching other characters. Else best case of insert, delete or replace. # Integers in each row are sorted from left to right.
# Time - O(m * n) # The first integer of each row is greater than the last integer of the previous row.
# Space - O(m * n)
# Treat the 2-d matrix as a 1-d list of length rows * cols. Binary search indices from 0 to rows * cols - 1.
class Solution(object): # Time - O(log m + log n)
def minDistance(self, word1, word2): # Space - O(1)
"""
:type word1: str class Solution(object):
:type word2: str def searchMatrix(self, matrix, target):
:rtype: int """
""" :type matrix: List[List[int]]
:type target: int
def edit_distance(i, j): :rtype: bool
if i < 0 or j < 0: """
return i + 1 + j + 1 if not matrix or not matrix[0]:
return False
if (i, j) in memo:
return memo[(i, j)] rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1
if word1[i] == word2[j]:
result = edit_distance(i - 1, j - 1) while high >= low:
else:
result = 1 + min(edit_distance(i - 1, j), mid = (high + low) // 2
edit_distance(i, j - 1), value = matrix[mid // cols][mid % cols] # convert mid to a row and column
edit_distance(i - 1, j - 1))
if target == value:
memo[(i, j)] = result return True
return result if target > value:
low = mid + 1
memo = {} else:

high = mid - 1 start += 1

return False if best_end == float('inf'):

return ''
return s[best_start:best_end+1]

# python_1_to_1000/075_Sort_Colors.py - m # python_1_to_1000/077_Combinations.py - m

_author_ = 'jake' _author_ = 'jake'

_project_ = 'leetcode' _project_ = 'leetcode'

# https://leetcode.com/problems/sort-colors/ # https://leetcode.com/problems/combinations/
# Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, # Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
# with the colors in the order red, white and blue.
# Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. # Recursively ignore the last number and choose k form n-1, or use the last number and combine with k-1 from n-1.
# Time - O(k * n! / (k! * (n-k)!)), nCk combinations each of length k
# Overwrite each index with blue. If index was red or white, add a new white and increment white pointer. If index # Space - O(k * n! / (k! * (n-k)!))
# was red, add a new red and increment red pointer.
# Time - O(n) class Solution(object):
# Space - O(1) def combine(self, n, k):
"""
class Solution(object): :type n: int
def sortColors(self, nums): :type k: int
""" :rtype: List[List[int]]
:type nums: List[int] """
:rtype: void Do not return anything, modify nums in-place instead. if k == 0: # or if k == 1 return [[i] for i in range(1,n+1)]
""" return [[]]
next_red, next_white = 0, 0 if n < k: # or if k == n return [[i for i in range(1,n+1)]]
return []
for i in range(len(nums)):
without_last = self.combine(n-1, k)
colour = nums[i]
nums[i] = 2 with_last = [[n] + combo for combo in self.combine(n-1, k-1)]

if colour < 2: return with_last + without_last

nums[next_white] = 1
next_white += 1

if colour == 0:
nums[next_red] = 0 # python_1_to_1000/078_Subsets.py - m
next_red += 1
_author_ = 'jake'
_project_ = 'leetcode'

# python_1_to_1000/076_Maximum_Window_Substring.py - h # https://leetcode.com/problems/subsets/
# Given a set of distinct integers, nums, return all possible subsets.
_author_ = 'jake' # The solution set must not contain duplicate subsets.
_project_ = 'leetcode'
# Each bit of binary number form 0 to 2**n - 1 represents whether or not an entry in nums is in that set.
# https://leetcode.com/problems/minimum-window-substring/ # Alternatively, copy partial subsets both with and without each item.
# Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity # Time - O(n * 2**n), 2**n subsets each of length n.
O(n). # Space - O(n * 2**n)
# If there is no such window in S that covers all characters in T, return the empty string "".
# If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. class Solution(object):
def subsets(self, nums):
# Slide end of window forwards when not all letters in t are matched with window. Slide start of window when all """
# letters are matched. Maintain the required count of each letter (can be negative if excess) and overall to_match. :type nums: List[int]
# Time - O(n) :rtype: List[List[int]]
# Space - O(1) """
nb_subsets = 2**len(nums)
from collections import Counter all_subsets = []

class Solution(object): for subset_nb in range(nb_subsets):

def minWindow(self, s, t):
""" subset = []
:type s: str for num in nums:
:type t: str if subset_nb % 2 == 1:
:rtype: str subset.append(num)
""" subset_nb //= 2
freq = Counter(t)
best_start, best_end = 0, float('inf') all_subsets.append(subset)
start, end = 0, -1 # first and last indices of window in s
to_match = len(t) return all_subsets

while end < len(s)-1 or to_match == 0: # can extend end or all matched so will increase start

if to_match != 0: # not all matched, extend end # python_1_to_1000/079_Word_Search.py - m

end += 1
if s[end] in freq: # reduce count, can be negative _author_ = 'jake'
freq[s[end]] -= 1 _project_ = 'leetcode'
if freq[s[end]] >= 0: # reduce to_match if count not negative
to_match -= 1 # https://leetcode.com/problems/word-search/
# Given a 2D board and a word, find if the word exists in the grid.
else: # all matched, check if new min window, increment start # The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally
if end - start < best_end - best_start: # or vertically neighboring. The same letter cell may not be used more than once.
best_end = end
best_start = start # For each starting position, depth first search moving in all 4 directions and marking visited cells.
if s[start] in freq: # add start letter back to count # Time - O(m * n * s), for each starting board position, try upto s characters
freq[s[start]] += 1 # Space - O(1)
if freq[s[start]] > 0:
to_match += 1 # increment to_match if positive count class Solution(object):
 def exist(self, board, word): :type target: int
""" :rtype: bool
:type board: List[List[str]] """
:type word: str return self.binary(nums, 0, len(nums)-1, target)
:rtype: bool
""" def binary(self, nums, left, right, target):
if not board or not board[0]:
return False if left > right:
rows, cols = len(board), len(board[0]) return False

for r in range(rows): mid = (left + right) // 2

for c in range(cols): if nums[mid] == target:
if self.can_find(word, 0, board, r, c): return True
return True
return False if nums[left] < nums[mid]: # LHS is sorted
if target < nums[mid] and target >= nums[left]: # check target in range of both ends
return self.binary(nums, left, mid-1, target) # target cannot be on RHS
def can_find(self, word, i, board, r, c): return self.binary(nums, mid+1, right, target) # target cannot be on LHS

if i >= len(word): # nothing more of word to find if nums[mid] < nums[right]: # RHS is sorted
return True if target > nums[mid] and target <= nums[right]: # check target in range of both ends
if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]): # outside board return self.binary(nums, mid+1, right, target) # target cannot be on LHS
return False return self.binary(nums, left, mid-1, target) # target cannot be on RHS
if word[i] != board[r][c]: # no match letter
return False if nums[left] == nums[mid] and nums[mid] != nums[right]: # LHS is flat and does not include target
return self.binary(nums, mid+1, right, target) # so check RHS
board[r][c] = '*' # set this position so cannot be used again if nums[right] == nums[mid] and nums[mid] != nums[left]: # RHS is flat and does not include target
return self.binary(nums, left, mid-1, target) # so check LHS
if (self.can_find(word, i+1, board, r+1, c) or self.can_find(word, i+1, board, r-1, c) or
self.can_find(word, i+1, board, r, c+1) or self.can_find(word, i+1, board, r, c-1)): if self.binary(nums, left, mid-1, target): # both sides flat, if not fount on one side check the other
return True return True
return self.binary(nums, mid+1, right, target)
board[r][c] = word[i] # if False, reset position to letter
return False

# python_1_to_1000/082_Remove_Duplicates_from_Sorted_List_II.py - m
# python_1_to_1000/080_Remove_Duplicates_from_Sorted_Array_II.py - m
_author_ = 'jake'
_author_ = 'jake' _project_ = 'leetcode'
_project_ = 'leetcode'
# https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
# https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ # Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the
# Follow up for "Remove Duplicates": original list.
# What if duplicates are allowed at most twice?
# For example, given sorted array nums = [1,1,1,2,2,3], # If node is duplicated, move past all nodes of same value. Else add node to final list.
# Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. # Time - O(n)
# Space - O(1)
# Maintain a pointer to the next index to contain a result. If a new number does not have 2 copies already
# in result then add it. # Definition for singly-linked list.
# Time - O(2) class ListNode(object):
# Space - O(1) def __init__(self, x):
self.val = x
class Solution(object): self.next = None
def removeDuplicates(self, nums):
""" class Solution(object):
:type nums: List[int] def deleteDuplicates(self, head):
:rtype: int """
""" :type head: ListNode
next = 2 # next index to be filled with result :rtype: ListNode
"""
for index in range(2, len(nums)): pseudo = prev = ListNode(None)
pseudo.next = head
if nums[index] != nums[next-2]: # result does not contain 2 copies of this num node = head
nums[next] = nums[index]
next += 1 while node:

return min(next, len(nums)) if node.next and node.val == node.next.val: # node begins a sequence of duplicates
duplicate_value = node.val
node = node.next
# python_1_to_1000/081_Search_in_Rotated_Sorted_Array_II.py - m while node and node.val == duplicate_value: # skip over all duplicates
node = node.next
_author_ = 'jake' prev.next = None # list ends until non-duplicate found
_project_ = 'leetcode'
else: # node is not duplicated
# https://leetcode.com/problems/search-in-rotated-sorted-array-ii/ prev.next = node # add to resulting list
# Follow up for "Search in Rotated Sorted Array": prev = node
# What if duplicates are allowed? node = node.next
# Would this affect the run-time complexity? How and why?
# Write a function to determine if a given target is in the array. return pseudo.next

# When splitting the array at mid, one side contains the rotation point. The other side must be increasing or flat.
# Rotation point side cannot be increasing, only flat or decreasing.
# Therefor if we find an increasing side we know whether to recurse on that side or the other. # python_1_to_1000/083_Remove_Duplicates_from_Sorted_List.py
# Then if either side is not flat we know it is not sorted adn the other side is, so recurse there.
# If both sides are flat we must check them both. _author_ = 'jake'
# Time - O(n) _project_ = 'leetcode'
# Space - O(n)
# https://leetcode.com/problems/remove-duplicates-from-sorted-list/
class Solution(object): # Given a sorted linked list, delete all duplicates such that each element appear only once.
def search(self, nums, target):
""" # If next node is same as node, link node to node.next.next. Else move to next node.
:type nums: List[int] # Time - O(n)

# Space - O(1) heights = [0] * cols

# Definition for singly-linked list. for row in range(rows):

class ListNode(object):
def __init__(self, x): heights = [heights[i]+1 if matrix[row][i]=='1' else 0 for i in range(cols)]
self.val = x heights.append(0)
self.next = None stack = [0]

class Solution(object): for col in range(1, len(heights)):

def deleteDuplicates(self, head): while stack and heights[col] < heights[stack[-1]]:
""" height = heights[stack.pop()]
:type head: ListNode if not stack:
:rtype: ListNode width = col
""" else:
node = head width = col - stack[-1] - 1
max_area = max(max_area, height * width)
while node and node.next:
if node.val == node.next.val: stack.append(col)
node.next = node.next.next
else: return max_area
node = node.next

return head
# python_1_to_1000/086_Partition_List.py - m

_author_ = 'jake'
# python_1_to_1000/084_Largest_Rectangle_in_Histogram.py - h _project_ = 'leetcode'

_author_ = 'jake' # https://leetcode.com/problems/partition-list/

_project_ = 'leetcode' # Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or
equal to x.
# https://leetcode.com/problems/largest-rectangle-in-histogram/ # You should preserve the original relative order of the nodes in each of the two partitions.
# Given n non-negative integers representing the histogram's bar height where the width of each bar is 1,
# find the area of largest rectangle in the histogram. # Create new pseudo heads for lists of nodes lesser and greater than x.
# Time - O(n)
# For each bar, find the largest rectangle including that bar as the lowest bar. # Space - O(1)
# An index is popped from the stack when a lower bar to the right is found.
# We calculate the largest area with the bar at the popped index as the height (lowest bar in rectangle). # Definition for singly-linked list.
# Width is determined by the closest lower bar to the left and right. class ListNode(object):
# Time - O(n) def __init__(self, x):
# Space - O(n) self.val = x
self.next = None
class Solution(object):
def largestRectangleArea(self, heights): class Solution(object):
""" def partition(self, head, x):
:type heights: List[int] """
:rtype: int :type head: ListNode
""" :type x: int
max_area = 0 :rtype: ListNode
heights = [0] + heights + [0] # stack will not be empty and last genuine bar will be popped """
stack = [0] # indices of bars in non-decreasing height order lesser_head = lesser = ListNode(None)
greater_head = greater = ListNode(None)
for i, bar in enumerate(heights[1:], 1):
node = head
while heights[stack[-1]] > bar: # pop taller off stack while node:
if node.val < x:
height = heights[stack.pop()] # form rectangle with popped bar determining height lesser.next = node
width = i - stack[-1] - 1 # i and stack[-1] - 1 are the first lower bars on left and right lesser = node
max_area = max(max_area, height * width) else: # node.val >= x
greater.next = node
stack.append(i) greater = node
node = node.next
return max_area
greater.next = None # if last node not greater then break link to last node
lesser.next = greater_head.next # join lists
return lesser_head.next

# python_1_to_1000/085_Maximal_Rectangle.py - h
# python_1_to_1000/087_Scramble_String.py - h
_author_ = 'jake'
_project_ = 'leetcode' _author_ = 'jake'
_project_ = 'leetcode'
# https://leetcode.com/problems/maximal-rectangle/
# Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. # https://leetcode.com/problems/scramble-string/
# Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
# For each row build a 'histogram' of the number of 1s above and including each column. Then proceed as for problem 084 # To scramble the string, we may choose any non-leaf node and swap its two children.
# and pop a column off the stack whenever its 2 boundaries are lower. # Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
# Time - O(m*n)
# Space - O(n) # Base cases of strings containing different characters or same string. Else for all partition points, lest and right
# sides are scrambled versions, before or after swapping.
class Solution(object): # Time - exponential since 4n recursive calls for string of length n.
def maximalRectangle(self, matrix):
""" from collections import Counter
:type matrix: List[List[str]]
:rtype: int class Solution(object):
""" def isScramble(self, s1, s2):
if not matrix or not matrix[0]: """
return 0 :type s1: str
:type s2: str
rows = len(matrix) :rtype: bool
cols = len(matrix[0]) """
count1 = Counter(s1)
max_area = 0 for c in s2:
 if c not in count1: return gray
return False
count1[c] -= 1
if count1[c] < 0:
return False
# python_1_to_1000/090_Subsets_II.py - m
if s1 == s2:
return True _author_ = 'jake'
_project_ = 'leetcode'
for partition in range(1, len(s1)):
# https://leetcode.com/problems/subsets-ii/
s1_l = s1[:partition] # partition number of chars from left # Given a collection of integers that might contain duplicates, nums, return all possible subsets.
s1_r = s1[partition:] # last (len(s1) - partition) chars # Note: The solution set must not contain duplicate subsets.
s2_l = s2[:partition]
s2_r = s2[partition:] # Count the frequency of times each num in nums. Starting with the empty subset, for each num append it to all
s2_l_swap = s2[:-partition] # (len(s2) - partition) chars from left # subsets every possible number of times (between 0 and its frequency in nums, inclusive).
s2_r_swap = s2[-partition:] # last partition chars # Time - O(n * 2**n), worst case when nums are all ujnique
# Space - O(n * 2**n)
if (self.isScramble(s1_l, s2_l) and self.isScramble(s1_r, s2_r)) or \
(self.isScramble(s1_l, s2_r_swap) and self.isScramble(s1_r, s2_l_swap)): from collections import Counter
return True
class Solution(object):
return False def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
# python_1_to_1000/088_Merge_Sorted_Array.py """
num_count = Counter(nums)
_author_ = 'jake' results = [[]]
_project_ = 'leetcode'
for num in num_count:
# https://leetcode.com/problems/merge-sorted-array/ results += [partial+[num]*i for i in range(1,num_count[num]+1) for partial in results]
# Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
# You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from return results
nums2.
# The number of elements initialized in nums1 and nums2 are m and n respectively.

# Start from end of nums1. Move largest elements from each array.
# Time - O(m + n) # python_1_to_1000/091_Decode_Ways.py - m
# Space - O(1)
_author_ = 'jake'
class Solution(object): _project_ = 'leetcode'
def merge(self, nums1, m, nums2, n):
""" # https://leetcode.com/problems/decode-ways/
:type nums1: List[int] # A message containing letters from A-Z is being encoded to numbers using the following mapping:
:type m: int # 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26
:type nums2: List[int] # Given an encoded message containing digits, determine the total number of ways to decode it.
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead. # Dynamic programming. Calc ways for prefix of length i from prefixes of lengths i-1 and i-2.
""" # Time - O(n)
i, j, k = m - 1, n - 1, m + n - 1 # Space - O(n), could be O(1) by keeping only last 2 values of nb_ways

while i >= 0 and j >= 0: class Solution(object):

if nums1[i] > nums2[j]: def numDecodings(self, s):
nums1[k] = nums1[i] """
i -= 1 :type s: str
else: :rtype: int
nums1[k] = nums2[j] """
j -= 1 if not s:
k -= 1 return 0

if i < 0: # Nothing to move if only nums1 remain, else move rest of nums2 nb_ways = [0] * (len(s)+1) # nb_ways[i] is number of ways to decode prefix of length i
nums1[:k+1] = nums2[:j+1] nb_ways[0] = 1 # required else '10' will be 0
if s[0] != '0':
nb_ways[1] = 1
# python_1_to_1000/089_Gray_Code.py - m
for i in range(1, len(s)):
_author_ = 'jake'
_project_ = 'leetcode' if s[i] != '0': # last char is not '0'
nb_ways[i+1] += nb_ways[i] # use all ways to decode without this char
# https://leetcode.com/problems/gray-code/ if 10 <= int(s[i-1:i+1]) <= 26: # last 2 form int between 10 and 26
# The gray code is a binary numeral system where two successive values differ in only one bit. nb_ways[i+1] += nb_ways[i-1] # use all ways to decode without last 2 chars
# Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code.
# A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: return nb_ways[-1]
# 00 - 0, 01 - 1, 11 - 3, 10 - 2

# Grey sequence of n + 1 is formed starting with sequence for n, then appending the reverse of that sequence with
# the extra bit set. # python_1_to_1000/092_Reverse_Linked_List_II.py - m
# GC(0) = [0], GC(1) = [0,1], GC(2) = [0,1,3,2], GC(3) = [0,1,3,2,6,7,5,4]
# Time - O(2**n) _author_ = 'jake'
# Space - O(2**n) _project_ = 'leetcode'

class Solution(object): # https://leetcode.com/problems/reverse-linked-list-ii/

def grayCode(self, n): # Reverse a linked list from position m to n. Do it in-place and in one-pass.
""" # m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
:type n: int
:rtype: List[int] # Find tail of non-reversed section, reverse nodes between m and n, link back between non-reversed sections.
""" # Time - O(n)
gray = [0] # Space - O(1)

for i in range(n): # Definition for singly-linked list.

gray += [x + 2 ** i for x in reversed(gray)] class ListNode(object):
def __init__(self, x):

self.val = x # Given a binary tree, return the inorder traversal of its nodes' values.
self.next = None # Note: Recursive solution is trivial, could you do it iteratively?

class Solution(object): # From root, go as far left as possible pushing all nodes onto stack. While nodes on stack, pop a node and add it to
def reverseBetween(self, head, m, n): # the result. Its left child (if any) has already been visited because it was added to the stack later so popped
""" # earlier. If the node has a right child, add that child and all its left branch to the stack.
:type head: ListNode # Time - O(n)
:type m: int # Space - O(n)
:type n: int
:rtype: ListNode # Definition for a binary tree node.
""" # class TreeNode(object):
pseudo = ListNode(None) # create a new pseudo head # def __init__(self, x):
pseudo.next = head # self.val = x
node = pseudo # self.left = None
n -= m # n = nb nodes to be reversed - 1 # self.right = None

while m > 1: # find the tail of the first non-reversed section class Solution(object):
node = node.next def inorderTraversal(self, root):
m -= 1 """
:type root: TreeNode
reversed_head = None :rtype: List[int]
next_reverse = node.next """
stack, result = [], []
while n >= 0: # add next_reverse in front of reversed_head
tail = next_reverse.next while root: # make top of stack the smallest value
next_reverse.next = reversed_head stack.append(root)
reversed_head = next_reverse root = root.left
next_reverse = tail
n -= 1 while stack:

node.next.next = tail # link tail of reversed section to second non-reversed section node = stack.pop()
node.next = reversed_head # link tail of the first non-reversed section to reversed section result.append(node.val)

return pseudo.next if node.right:

node = node.right
while node:
# python_1_to_1000/093_Restore_IP_Addresses.py - m stack.append(node)
node = node.left
_author_ = 'jake'
_project_ = 'leetcode' return result

# https://leetcode.com/problems/restore-ip-addresses/
# Given a string containing only digits, restore it by returning all possible valid IP address combinations. # python_1_to_1000/095_Unique_Binary_Search_Trees_II.py - m
# E.g. given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
_author_ = 'jake'
# For each of the 4 sections of an IP address, use 3 chars if between 100 and 255, 2 if > 10 and always use 1 char - _project_ = 'leetcode'
# provided that the remaining chars are not too few or too many to make an IP address.
# an IP address # https://leetcode.com/problems/unique-binary-search-trees-ii/
# Time - O(1), max of 4**3 possibilities for any s # Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
# Space - O(1)
# Any number i from 1 to n is the root. Numbers less than i form the left subtree, numbers greater from the right.
class Solution(object): # Time - O(n**2 * Catalan(n)) where Catalan(n) = 2n! / (n+1)!n!
def restoreIpAddresses(self, s): # Space - O(n * Catalan(n))
"""
:type s: str # Definition for a binary tree node.
:rtype: List[str] class TreeNode(object):
""" def __init__(self, x):
NB_SECTIONS = 4 self.val = x
if 3 * NB_SECTIONS < len(s) < NB_SECTIONS: # cannot make any IPs self.left = None
return [] self.right = None

results = [[]] class Solution(object):

def generateTrees(self, n):
while NB_SECTIONS > 0: """
:type n: int
new_results = [] :rtype: List[TreeNode]
"""
for result in results: if n <= 0:
return []
used = sum((len(section) for section in result)) # number of used characters in this partial result return self.generate(1, n)
remaining = len(s) - used # number of remaining chars in s
def generate(self, left, right):
if 3 * (NB_SECTIONS - 1) >= remaining - 3 >= NB_SECTIONS - 1 and 100 <= int(s[used:used + 3]) <= 255:
new_results.append(result + [s[used:used + 3]]) if left > right:
if 3 * (NB_SECTIONS - 1) >= remaining - 2 >= NB_SECTIONS - 1 and 10 <= int(s[used:used + 2]): return [None]
new_results.append(result + [s[used:used + 2]])
if 3 * (NB_SECTIONS - 1) >= remaining - 1 >= NB_SECTIONS - 1: results = []
new_results.append(result + [s[used]]) for i in range(left, right+1):

NB_SECTIONS -= 1 left_trees = self.generate(left, i-1)

results = new_results right_trees = self.generate(i+1, right)
for l in left_trees:
return ['.'.join(result) for result in results] for r in right_trees:
root = TreeNode(i)
root.left = l
root.right = r
results.append(root)
# python_1_to_1000/094_Binary_Tree_Inorder_Traversal.py
return results
_author_ = 'jake'
_project_ = 'leetcode'

# https://leetcode.com/problems/binary-tree-inorder-traversal/ # python_1_to_1000/096_Unique_Binary_Search_Trees.py - m
_author_ = 'jake' # https://leetcode.com/problems/validate-binary-search-tree/
_project_ = 'leetcode' # Given a binary tree, determine if it is a valid binary search tree (BST).
# Assume a BST is defined as follows:
# https://leetcode.com/problems/unique-binary-search-trees/ # The left subtree of a node contains only nodes with keys less than the node's key.
# Given an integer n, count all structurally unique BST's (binary search trees) that store values 1...n. # The right subtree of a node contains only nodes with keys greater than the node's key.
# Both the left and right subtrees must also be binary search trees.
# Dynamic programming. Base case of 1 for n = 0 or 1. For each of n possible root nodes, multiply the
# possible left subtrees with the right subtrees. # Perform an inorder traversal and check that each node is greater than the previous. Does not work if equal nodes
# Time - O(n**2) # are allowed.
# Space - O(n) # Alternatively track the upper and lower bounds possible for each node, depending on parents.
# Time - O(n)
# Definition for a binary tree node. # Space - O(n), or log n if balanced
class TreeNode(object):
def __init__(self, x): # Definition for a binary tree node.
self.val = x class TreeNode(object):
self.left = None def __init__(self, x):
self.right = None self.val = x
self.left = None
class Solution(object): self.right = None
def numTrees(self, n):
""" class Solution(object):
:type n: int def isValidBST(self, root):
:rtype: int """
""" :type root: TreeNode
memo = [-1] * (n+1) # memo[i] is number of ways for i nodes :rtype: bool
return self.helper(n, memo) """
self.correct = True
def helper(self, n, memo): self.prev = float('-inf')
if n <= 1: self.inorder(root)
return 1 # 1 tree for n==0 (empty tree) and 1 tree for n==1 return self.correct

if memo[n] != -1: def inorder(self, node):

return memo[n] if not node or not self.correct: # return if already found out of order
return
count = 0
for i in range(1, n+1): # take each number 1...n as root self.inorder(node.left)
# all numbers < i form left subtree, all > i form right subtree
# multiply possibilities if node.val <= self.prev:
count += self.helper(i-1, memo) * self.helper(n-i, memo) self.correct = False
memo[n] = count return # halt exploration
return count self.prev = node.val

self.inorder(node.right)

# python_1_to_1000/097_Interleaving_String.py - m
class Solution2(object):
_author_ = 'jake' def isValidBST(self, root):
_project_ = 'leetcode' return self.valid(root, float('-inf'), float('inf'))

# https://leetcode.com/problems/interleaving-string/ def valid(self, node, lower, upper): # node.val must be above lower and below upper
# Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. if not node:
return True
# If the next char of s1 or s2 matches s3, recurse on the remainder. if node.val <= lower or node.val >= upper: # can be amended if equal values are allowed
# Time - O(m * n), every prefix of s1 * every prefix of s2 return False
# Space - O(m * n) return self.valid(node.left, lower, node.val) and self.valid(node.right, node.val, upper)

class Solution(object):
def isInterleave(self, s1, s2, s3):
""" # python_1_to_1000/099_Recover_Binary_Search_Tree.py - m
:type s1: str
:type s2: str _author_ = 'jake'
:type s3: str _project_ = 'leetcode'
:rtype: bool
""" # https://leetcode.com/problems/recover-binary-search-tree/
if len(s1) + len(s2) != len(s3): # early return # The values of 2 nodes of a binary search tree (BST) are swapped by mistake.
return False # Recover the tree without changing its structure.
return self.helper(s1, s2, s3, 0, 0, {})
# Perform an inorder traversal tracking the previous node. The first time a non-increasing node value is found,
# store the previous node. The second time a non-increasing node value is found, store the node.
def helper(self, s1, s2, s3, i, j, memo): # i, j are indices of next char to be matched in s1, s2 # E.g. for 1,2,3,8,5,6,7,4,9 we store 8 and 4.
# Time - O(n)
if i >= len(s1) or j >= len(s2): # base case, one string already matched # Space - O(n), recursion depth worst case, log n if balanced
return s1[i:] + s2[j:] == s3[i+j:]
# Definition for a binary tree node.
if (i, j) in memo: class TreeNode(object):
return memo[(i, j)] def __init__(self, x):
self.val = x
result = False self.left = None
if s1[i] == s3[i+j] and self.helper(s1, s2, s3, i+1, j, memo): self.right = None
result = True
elif s2[j] == s3[i+j] and self.helper(s1, s2, s3, i, j+1, memo): class Solution(object):
result = True def recoverTree(self, root):
"""
memo[(i, j)] = result :type root: TreeNode
return result :rtype: void Do not return anything, modify root in-place instead.
"""
self.swapped1 = None
self.swapped2 = None
# python_1_to_1000/098_Validate_Binary_Search_Tree.py - m self.prev = TreeNode(float('-inf'))
self.inorder(root)
_author_ = 'jake' self.swapped1.val, self.swapped2.val = self.swapped2.val, self.swapped1.val
_project_ = 'leetcode'

def inorder(self, node): if not left_node or not right_node:

if not node: return False
return
if left_node.val != right_node.val:
self.inorder(node.left) return False

if node.val <= self.prev.val: return self.is_mirror(right_node.right, left_node.left) and \

if not self.swapped1: self.is_mirror(left_node.right, right_node.left)
self.swapped1 = self.prev
if self.swapped1:
self.swapped2 = node # python_1_to_1000/102_Binary_Tree_Level_Order_Traversal.py - m

self.prev = node _author_ = 'jake'

_project_ = 'leetcode'
self.inorder(node.right)
# https://leetcode.com/problems/binary-tree-level-order-traversal/
# Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

# python_1_to_1000/100_Same_Tree.py # Create a list of all non-null nodes from the nodes in the level above.
# Time - O(n)
_author_ = 'jake' # Space - O(n)
_project_ = 'leetcode'
# Definition for a binary tree node.
# https://leetcode.com/problems/same-tree/ # class TreeNode(object):
# Given two binary trees, write a function to check if they are equal or not. # def __init__(self, x):
# Two binary trees are considered equal if they are structurally identical and the nodes have the same value. # self.val = x
# self.left = None
# Traverse both trees, checking nodes exist in same places and values are same. Could preorder, inorder or postorder. # self.right = None
# Time - O(min(m, n))
# Space - O(min(m, n)), or log is balanced class Solution(object):
def levelOrder(self, root):
# Definition for a binary tree node. """
class TreeNode(object): :type root: TreeNode
def __init__(self, x): :rtype: List[List[int]]
self.val = x """
self.left = None result = []
self.right = None if not root:
return result
class Solution(object):
def isSameTree(self, p, q): level_nodes = [root]
"""
:type p: TreeNode while level_nodes:
:type q: TreeNode
:rtype: bool new_level_nodes = []
""" result.append([])
if not p and not q:
return True for node in level_nodes:
if not p or not q: result[-1].append(node.val)
return False if node.left:
new_level_nodes.append(node.left)
if p.val != q.val: if node.right:
return False new_level_nodes.append(node.right)
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
level_nodes = new_level_nodes

return result

# python_1_to_1000/101_Symmetric_Tree.py
# python_1_to_1000/103_Binary_Tree_Zigzag_Level_Order_Traversal.py - m
_author_ = 'jake'
_project_ = 'leetcode' _author_ = 'jake'
_project_ = 'leetcode'
# https://leetcode.com/problems/symmetric-tree/
# Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). # https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
# Given a binary tree, return the zigzag level order traversal of its nodes' values.
# Check if left and right subtrees are both present or not, then if root values are equal. Then recurse on their # (ie, from left to right, then right to left for the next level and alternate between).
# subtrees being mirrors - left/left of right/right and left/right of right/left
# Time - O(n) # Alternately append new nodes from left to right and right to left.
# Space - O(n) # Time - O(n)
# Space - O(n)
# Definition for a binary tree node.
# class TreeNode(object): # Definition for a binary tree node.
# def __init__(self, x): # class TreeNode(object):
# self.val = x # def __init__(self, x):
# self.left = None # self.val = x
# self.right = None # self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root): class Solution(object):
""" def zigzagLevelOrder(self, root):
:type root: TreeNode """
:rtype: bool :type root: TreeNode
""" :rtype: List[List[int]]
if not root: """
return True if not root:
return self.is_mirror(root.left, root.right) return []
traversal = []
def is_mirror(self, left_node, right_node):
level = [root]
if not left_node and not right_node: forward = True
return True
 while level:
return root
new_level = []
if forward: preorder.reverse() # reverse so we can pop in O(1) time
traversal.append([n.val for n in level]) inorder.reverse()
else: return build(None)
traversal.append([n.val for n in level[::-1]])

for node in level: # python_1_to_1000/106_Construct_Binary_Tree_from_Postorder_and_Inorder_Traversal.py - m

if node.left:
new_level.append(node.left) _author_ = 'jake'
if node.right: _project_ = 'leetcode'
new_level.append(node.right)
# https://leetcode.com/problems/construct-binary-tree-from-postorder-and-inorder-traversal/
level = new_level # Given inorder and postorder traversal of a tree, construct the binary tree.
forward = not forward # You may assume that duplicates do not exist in the tree.

return traversal # Construct in postorder. Last element of postorder is root. Partition preorder about this element.
# Build the right subtree first until postorder[0] is not in inorder.
# Time - O(n)
# Space - O(n)

# python_1_to_1000/104_Maximum_Depth_of_Binary_Tree.py # Definition for a binary tree node.

class TreeNode(object):
_author_ = 'jake' def __init__(self, x):
_project_ = 'leetcode' self.val = x
self.left = None
# https://leetcode.com/problems/maximum-depth-of-binary-tree/ self.right = None
# Given a binary tree, find its maximum depth.
# The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. class Solution(object):
def buildTree(self, inorder, postorder):
# Base case of zer for null node, else 1 + max of left and right subtrees. """
# Time - O(n) :type inorder: List[int]
# Space - O(n) :type postorder: List[int]
:rtype: TreeNode
# Definition for a binary tree node. """
# class TreeNode(object): if not inorder: # no inorder signifies null tree even if postorder is not null
# def __init__(self, x): return None
# self.val = x
# self.left = None inorder_index = inorder.index(postorder.pop())
# self.right = None root = TreeNode(inorder[inorder_index])

class Solution(object): root.right = self.buildTree(inorder[inorder_index+1:], postorder) # right first

def maxDepth(self, root): root.left = self.buildTree(inorder[:inorder_index], postorder)
"""
:type root: TreeNode return root
:rtype: int
"""
if not root: # python_1_to_1000/107_Binary_Tree_Level_Order_Traversal_II.py - m
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) _author_ = 'jake'
_project_ = 'leetcode'

# python_1_to_1000/105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.py - m # https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
# Given a binary tree, return the bottom-up level order traversal of its nodes' values.
_author_ = 'jake' # I.e. from left to right, level by level from leaf to root.
_project_ = 'leetcode'
# Perform an inorder traversal, tracking depth and appending node values to corresponding sub-list. Reverse
# https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ # result before returning.
# Given preorder and inorder traversal of a tree, construct the binary tree. # Time - O(n)
# You may assume that duplicates do not exist in the tree. # Space - O(n)

# Build until we reach stop value, initially None. Take first preorder as root then recurse left until inorder is # Definition for a binary tree node.
# root value. Then discard inorder and recurse right until final stop. class TreeNode(object):
# Time - O(n) def __init__(self, x):
# Space - O(n) self.val = x
self.left = None
from collections import deque self.right = None

# Definition for a binary tree node. class Solution(object):

class TreeNode(object): def levelOrderBottom(self, root):
def __init__(self, x): """
self.val = x :type root: TreeNode
self.left = None :rtype: List[List[int]]
self.right = None """
traversal = []
class Solution(object): self.inorder(root, 0, traversal)
def buildTree(self, preorder, inorder): return traversal[::-1]
"""
:type preorder: List[int] def inorder(self, node, depth, traversal):
:type inorder: List[int]
:rtype: TreeNode if not node:
""" return
def build(stop):
if len(traversal) == depth:
if not inorder or inorder[-1] == stop: traversal.append([])
return None
self.inorder(node.left, depth+1, traversal)
root_val = preorder.pop()
root = TreeNode(root_val) traversal[depth].append(node.val)
root.left = build(root_val) # build left subtree until inorder reaches root_val
inorder.pop() # then discard root_val self.inorder(node.right, depth+1, traversal)
root.right = build(stop) # build right subtree until inorder reaches original stop

root.left = left_subtree
node_as_list[0] = node_as_list[0].next # update entry to next node of linked-list

# python_1_to_1000/108_Convert_Sorted_Array_to_Binary_Search_Tree.py root.right = self.list_to_bst(node_as_list, mid + 1, end)

_author_ = 'jake' return root

_project_ = 'leetcode'

# https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
# Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
# python_1_to_1000/110_Balanced_Binary_Tree.py
# Mid element is root, recursively form left and right subtrees.
# Time - O(n) _author_ = 'jake'
# Space - O(n) _project_ = 'leetcode'

# Definition for a binary tree node. # https://leetcode.com/problems/balanced-binary-tree/

class TreeNode(object): # Given a binary tree, determine if it is height-balanced.
def __init__(self, x): # A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node
self.val = x # never differ by more than 1.
self.left = None
self.right = None # Helper function balanced returns the depth of the root if the tree is balance or else -1 if not balanced.
# A tree is not balance if either left or right subtree is not balanced, or the difference in left and right subtree
class Solution(object): # depths is greater than 1.
def sortedArrayToBST(self, nums): # Time - O(n), visit all nodes
""" # Space - O(n)
:type nums: List[int]
:rtype: TreeNode class Solution(object):
""" def isBalanced(self, root):
return self.convert(nums, 0, len(nums)-1) """
:type root: TreeNode
def convert(self, nums, left, right): :rtype: bool
if left > right: """
return None def balanced(node):
mid = (left + right) // 2
root = TreeNode(nums[mid]) if not node:
root.left = self.convert(nums, left, mid-1) return 0
root.right = self.convert(nums, mid+1, right)
return root left_depth = balanced(node.left)
right_depth = balanced(node.right)

if left_depth == -1 or right_depth == -1:

# python_1_to_1000/109_Convert_Sorted_List_to_Binary_Search_Tree.py - m return -1
if abs(left_depth - right_depth) > 1:
_author_ = 'jake' return -1
_project_ = 'leetcode'
return 1 + max(left_depth, right_depth)

# https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ return balanced(root) != -1

# Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

# Count the length of the list. Form left subtree from nodes before mid. Mid node forms root, then right subtree
# from nodes after mid. When a new tree node is made, advance the linked list pointer. Bottom-up approach.
# Time - O(n)
# Space - O(n) # python_1_to_1000/111_Minimum_Depth_of_Binary_Tree.py

# Definition for singly-linked list. _author_ = 'jake'

class ListNode(object): _project_ = 'leetcode'
def __init__(self, x):
self.val = x # https://leetcode.com/problems/minimum-depth-of-binary-tree/
self.next = None # Given a binary tree, find its minimum depth.
# The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
# Definition for a binary tree node.
class TreeNode(object): # If either subtrees is not present, return 1 + minDepth of existing subtree. If both (or neither) subtrees, return
def __init__(self, x): # 1 + min of subtree minDepths
self.val = x # Time - O(n)
self.left = None # Space - O(n)
self.right = None
# Definition for a binary tree node.
class TreeNode(object):
class Solution(object): def __init__(self, x):
def sortedListToBST(self, head): self.val = x
""" self.left = None
:type head: ListNode self.right = None
:rtype: TreeNode
""" class Solution(object):
count = 0 def minDepth(self, root):
node = head """
while node: :type root: TreeNode
count += 1 :rtype: int
node = node.next """
return self.list_to_bst([head], 0, count - 1) # [head] is mutable list of next list node to be converted if not root:
return 0

def list_to_bst(self, node_as_list, start, end): # convert linked-list nodes from start to end (inclusive) l = self.minDepth(root.left)
r = self.minDepth(root.right)
if start > end:
return None if not l or not r:
return 1 + l + r
mid = (start + end) // 2
return 1 + min(l, r)
left_subtree = self.list_to_bst(node_as_list, start, mid - 1) # will update contents of node_as_list to
# become the mid node of linked list
root = TreeNode(node_as_list[0].val)
# python_1_to_1000/112_Path_Sum.py # Each node only has a right child. Left subtree is flattened before right.

_author_ = 'jake' # Records the root of the previous subtree flattened as an instance field.
_project_ = 'leetcode' # Flattens right subtree, after which self.prev is the root of the right subtree.
# Then connects the flattened left subtree to the flattened right subtree.
# https://leetcode.com/problems/path-sum/ # Then removes the link from the root to the old left subtree, and sets the
# Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up # root.right to the root of the left subtree (now flattened).
# all the values along the path equals the given sum. # Time - O(n)
# Space - O(n)
# Base cases of False if no node and True if leaf node with correct sum. Else subtract node value and check if
# True in either subtree. # Definition for a binary tree node.
# Time - O(n) class TreeNode(object):
# Space - O(n) def __init__(self, x):
self.val = x
# Definition for a binary tree node. self.left = None
class TreeNode(object): self.right = None
def __init__(self, x):
self.val = x class Solution(object):
self.left = None
self.right = None def __init__(self): # instance field self.prev to track previous node
self.prev = None
class Solution(object):
def hasPathSum(self, root, sum): def flatten(self, root):
""" """
:type root: TreeNode :type root: TreeNode
:type sum: int :rtype: None Do not return anything, modify root in-place instead.
:rtype: bool """
""" if not root:
if not root: return
return False
self.flatten(root.right)
sum -= root.val self.flatten(root.left)
if sum == 0 and not root.left and not root.right: # leaf node
return True root.left = None
root.right = self.prev
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum) self.prev = root

# python_1_to_1000/113_Path_Sum_II.py - m # python_1_to_1000/115_Distinct_Subsequences.py - h

_author_ = 'jake' _author_ = 'jake'

_project_ = 'leetcode' _project_ = 'leetcode'

# https://leetcode.com/problems/path-sum-ii/ # https://leetcode.com/problems/distinct-subsequences/
# Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. # Given a string S and a string T, count the number of distinct subsequences of T in S.
# A subsequence of a string is a new string which is formed from the original string by deleting some (can be none)
# Maintain a partial path, appending latest node and decrementing target. When path has been explored, pop node off # of the characters without disturbing the relative positions of the remaining characters.
# partial path. Base cases are no node and leaf with remaining target of zero.
# Time - O(n log n), balanced tree has n/2 leaves and height log n # Dynamic programming. For all prefixes of S and T calculate the number of sequences. Base case is that the prefix
# Space - O(n log n), every path of balanced tree has correct sum # of T is the empty string, which is one subsequence of every prefix of S.
# The number of times T[:r] is a subsequence of S[:c] is the number of times T[:r] is a subsequence of S[:c - 1], plus
# Definition for a binary tree node. # if the last chars of T[:r] and S[:c] match then every T[:r - 1] subsequence of S[:c] can also be extended.
class TreeNode(object): # empty string is a subsequence of any string.
def __init__(self, x): # Time - O(m * n) where m = len(S) and n = len(T)
self.val = x # Space - O(m)
self.left = None
self.right = None
class Solution(object):
class Solution(object): def numDistinct(self, s, t):
def pathSum(self, root, sum): """
""" :type s: str
:type root: TreeNode :type t: str
:type sum: int :rtype: int
:rtype: List[List[int]] """
""" prev_subsequences = [1 for _ in range(len(s) + 1)] # empty string is always one subsequence of any string
paths = []
self.preorder(root, sum, [], paths) for r in range(1, len(t) + 1): # first r characters of T, i.e. T[:r]
return paths
subsequences = [0 for _ in range(len(s) + 1)]
def preorder(self, node, target, partial, paths):
for c in range(r, len(s) + 1): # first c chars of S. If c < r then no possibilities
if not node:
return subsequences[c] = subsequences[c - 1] # all T[:r] subsequences of S[:c - 1] are also
# subsequences of S[:c]
target -= node.val if s[c - 1] == t[r - 1]: # last chars match, add T[:r-1] subsequences of S[:c-1]
partial.append(node.val) subsequences[c] += prev_subsequences[c - 1]
if target == 0 and not node.left and not node.right:
paths.append(partial[:]) prev_subsequences = subsequences

self.preorder(node.left, target, partial, paths) return prev_subsequences[-1]

self.preorder(node.right, target, partial, paths)

partial.pop()

# python_1_to_1000/116_Populating_Next_Right_Pointers_in_Each_Node.py - m
# python_1_to_1000/114_Flatten_Binary_Tree_to_Linked_List.py - m
_author_ = 'jake'
_author_ = 'jake' _project_ = 'leetcode'
_project_ = 'leetcode'
# https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
# https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ # Given a binary tree, populate each next pointer to point to its next right node.
# Given a binary tree, flatten it to a linked list in-place. # If there is no next right node, the next pointer should be set to NULL.

# You may only use constant extra space. # Given numRows, generate the first numRows of Pascal's triangle.
# You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two
children). # Next row is sum of consecutive pairs of items from previous row.
# Time - O(n**2)
# Breadth first search by level. # Space - O(n**2)
# Time - O(n)
# Space - O(n) class Solution(object):
def generate(self, numRows):
# Definition for binary tree with next pointer. """
class TreeLinkNode(object): :type numRows: int
def __init__(self, x): :rtype: List[List[int]]
self.val = x """
self.left = None if numRows == 0:
self.right = None return []
self.next = None
pascal = [[1]]
class Solution(object):
def connect(self, root): for i in range(1, numRows):
"""
:type root: TreeLinkNode pascal.append([1])
:rtype: nothing for num1, num2 in zip(pascal[-2][:-1], pascal[-2][1:]):
""" pascal[-1].append(num1 + num2)
level = [root] pascal[-1].append(1)

while level and level[0]: # if first item is None then all are None because perfect, so terminate return pascal

next_level = []
prev = None
# python_1_to_1000/119_Pascal's_Triangle_II.py
for node in level: # set next right pointer
if prev: _author_ = 'jake'
prev.next = node _project_ = 'leetcode'
prev = node
# https://leetcode.com/problems/pascals-triangle-ii/
next_level.append(node.left) # add nodes to next level list, do not check if None # Given an index k, return the kth row of the Pascal's triangle.
next_level.append(node.right)
# Next row is sum of consecutive pairs of previous row.
level = next_level # Time - O(n**2)
# Space - O(n)

# python_1_to_1000/117_Populating_Next_Right_Pointers_in_Each_Node_II.py - m class Solution(object):

def getRow(self, rowIndex):
_author_ = 'jake' """
_project_ = 'leetcode' :type rowIndex: int
:rtype: List[int]
# https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ """
# Follow up for problem "Populating Next Right Pointers in Each Node". row = [1]
# What if the given tree could be any binary tree? Would your previous solution still work? for i in range(rowIndex):
row = [1] + [row[i]+row[i+1] for i in range(len(row)-1)] + [1]
# Breadth first search by level. Only append non-null nodes to level list. return row
# Time - O(n)
# Space - O(n)
# python_1_to_1000/120_Triangle.py - m
# Definition for binary tree with next pointer.
class TreeLinkNode(object): _author_ = 'jake'
def __init__(self, x): _project_ = 'leetcode'
self.val = x
self.left = None # https://leetcode.com/problems/triangle/
self.right = None # Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row
self.next = None below.

class Solution(object): # Bottom-ip dynamic programming. Min path is value of that element + min of the 2 paths to elements below.
def connect(self, root): # Time - O(n**2) for triangle height n since all elements visited
""" # Space - O(1), modifies input data
:type root: TreeLinkNode
:rtype: nothing class Solution(object):
""" def minimumTotal(self, triangle):
if not root: """
return :type triangle: List[List[int]]
level = [root] :rtype: int
"""
while level: for row in range(len(triangle)-2, -1, -1):
next_level = []
prev = None for col in range(len(triangle[row])):
for node in level: triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1])
if prev:
prev.next = node return triangle[0][0]
prev = node
if node.left:
next_level.append(node.left) # python_1_to_1000/121_Best_Time_to_Buy_and_Sell_Stock.py
if node.right:
next_level.append(node.right) _author_ = 'jake'
_project_ = 'leetcode'
level = next_level
# https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
# Say you have an array for which the ith element is the price of a given stock on day i.
# If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),
# python_1_to_1000/118_Pascal's_Triangle.py # design an algorithm to find the maximum profit.

_author_ = 'jake' # Record the max cash after buying stock at any point previously (which is negative), and the max cash after selling
_project_ = 'leetcode' # as the cash after boying + sale proceeds.
# Time - O(n)
# https://leetcode.com/problems/pascals-triangle/ # Space - O(1)
 # def __init__(self, x):
class Solution(object): # self.val = x
def maxProfit(self, prices): # self.left = None
""" # self.right = None
:type prices: List[int]
:rtype: int class Solution(object):
""" def maxPathSum(self, root):
buy = float('-inf') # maximum cash balance after buying a stock """
sell = 0 # maximum cash balance after buying and selling a stock :type root: TreeNode
:rtype: int
for price in prices: """
buy = max(-price, buy) # max of buying earlier or now return self.helper(root)[0]
sell = max(price + buy, sell) # max of selling earlier or now
def helper(self, node): # returns tuple of (via, down) where via is max path sum via (and including) this node
return sell # or via any node below, down is max path sum downwards from this node
if not node:
return float('-inf'), 0 # -inf for via if no node since path must have at least one node

# python_1_to_1000/122_Best_Time_to_Buy_and_Sell_Stock_II.py - m left_via, left_down = self.helper(node.left)

right_via, right_down = self.helper(node.right)
_author_ = 'jake'
_project_ = 'leetcode' # either use this node and go down left and/or right if positive, or best of left and right via.
via = max(node.val + max(0, left_down) + max(0, right_down), left_via, right_via)
# https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ # use this node and go down max of right or left if positive.
# Say you have an array for which the ith element is the price of a given stock on day i. down = node.val + max(0, left_down, right_down)
# Design an algorithm to find the maximum profit. You may complete as many transactions as you like
# (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple return via, down
# transactions at the same time (ie, you must sell the stock before you buy again).

# Sum all price increases.

# Time - O(n)
# Space - O(n), could be O(1) without creating a new list
# python_1_to_1000/125_Valid_Palindrome.py
class Solution(object):
def maxProfit(self, prices): _author_ = 'jake'
""" _project_ = 'leetcode'
:type prices: List[int]
:rtype: int # https://leetcode.com/problems/valid-palindrome/
""" # Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
return sum([max(prices[i]-prices[i-1], 0) for i in range(1,len(prices))])
# Convert to lower case and remove non-alphanumeric characters.
# Time - O(n)
# Space - O(n)
# python_1_to_1000/123_Best_Time_to_Buy_and_Sell_Stock_III.py - h
import string
_author_ = 'jake'
_project_ = 'leetcode' class Solution(object):
def isPalindrome(self, s):
# https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ """
# Say you have an array for which the ith element is the price of a given stock on day i. :type s: str
# Design an algorithm to find the maximum profit. You may complete at most two transactions. :rtype: bool
# You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). """
allowed = set(string.ascii_lowercase + string.digits)
# As per problem 121 with an additional buy and sell. s = [c for c in s.lower() if c in allowed]
# Time - O(n)
# Space - O(1) i, j = 0, len(s)-1
while i < j:
class Solution(object): if s[i] != s[j]:
def maxProfit(self, prices): return False
""" i += 1
:type prices: List[int] j -= 1
:rtype: int return True
"""
buy1, buy2 = float('-inf'), float('-inf')
sell1, sell2 = 0, 0

for price in prices: # python_1_to_1000/126_Word_Ladder_II.py - h

buy1 = max(buy1, -price)
sell1 = max(sell1, price + buy1) _author_ = 'jake'
buy2 = max(buy2, sell1 - price) _project_ = 'leetcode'
sell2 = max(sell2, price + buy2)
# https://leetcode.com/problems/word-ladder-ii/
return sell2 # Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s)
# from beginWord to endWord, such that:
# Only one letter can be changed at a time
# python_1_to_1000/124_Binary_Tree_Maximum_Path_Sum.py - h # Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
# Note:
_author_ = 'jake' # Return an empty list if there is no such transformation sequence.
_project_ = 'leetcode' # All words have the same length.
# All words contain only lowercase alphabetic characters.
# https://leetcode.com/problems/binary-tree-maximum-path-sum/ # You may assume no duplicates in the word list.
# Given a binary tree, find the maximum path sum. # You may assume beginWord and endWord are non-empty and are not the same.
# For this problem, a path is defined as any sequence of nodes from some starting node to any node in
# the tree along the parent-child connections. # Bidirectional breadth first search. Frontiers of valid neighbouring words are gradually expanded. Swap to use the
# The path must contain at least one node and does not need to go through the root. # smaller frontier in each round, stop when either frontier is empty (return empty list) or an intersection is found.
# Build ladders to srat using left parents and to end using right parents.
# Recursive helper function calculates max path downwards from and including any node and max path via a node or via # Time - O(b^(d/2)) where b is branching factor and d is depth between start and end
# any node below.
# Time - O(n) from collections import defaultdict
# Space - O(1) import string

# Definition for a binary tree node. class Solution(object):

# class TreeNode(object): def findLadders(self, beginWord, endWord, wordList):

"""
:type beginWord: str new_front = set()
:type endWord: str for word in front:
:type wordList: List[str]
:rtype: List[List[str]] visited.add(word) # add word to set of those already removed from frontiers
"""
if endWord not in wordList: for i in range(len(word)): # add reachable words to frontier
return [] next_words = graph[word[:i] + '_' + word[i + 1:]]
next_words -= visited # apart from if already removed from a frontier
wordList = set(wordList) # convert to set for O(1) lookup new_front |= next_words
left, right = {beginWord}, {endWord} # frontiers at both ends
left_parents, right_parents = defaultdict(set), defaultdict(set) # map word to its parent length += 1
swapped = False # have the frontiers been swapped? front = new_front

while left and right and not (left & right): # while both frontiers and no intersection if len(back) < len(front): # expand the smaller frontier next
front, back = back, front
if len(right) < len(left): # swap to expand smaller frontier
left, right = right, left return 0
left_parents, right_parents = right_parents, left_parents
swapped = not swapped

next_left = defaultdict(set)
for word in left: # python_1_to_1000/128_Longest_Consecutive_Sequence.py - m
for char in string.ascii_lowercase:
for i in range(len(beginWord)): _author_ = 'jake'
n = word[:i] + char + word[i + 1:] # replace every position with every char _project_ = 'leetcode'
if n in wordList and n not in left_parents: # valid word not been used
next_left[n].add(word) # https://leetcode.com/problems/longest-consecutive-sequence/
# Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
left_parents.update(next_left)
left = set(next_left.keys()) # Test if each number starts a new sequence, if it does then count that sequence.
# Time - O(n), visits each number at most twice
if swapped: # swap back # Space - O(n)
left, right = right, left
left_parents, right_parents = right_parents, left_parents class Solution(object):
def longestConsecutive(self, nums):
ladders = [[word] for word in left & right] # start from central intersection """
while ladders and ladders[0][0] not in beginWord: # extend ladders left to start :type nums: List[int]
ladders = [[p] + l for l in ladders for p in left_parents[l[0]]] :rtype: int
while ladders and ladders[0][-1] != endWord: # extend ladders right to end """
ladders = [l + [p] for l in ladders for p in right_parents[l[-1]]] numset = set(nums) # no ordering, O(1) lookup
longest = 0
return ladders
for num in numset:

# python_1_to_1000/127_Word_Ladder.py - h if num-1 in numset: # not the start of a sequence

continue
_author_ = 'jake'
_project_ = 'leetcode' seq = 0
while num in numset: # move along this sequence
# https://leetcode.com/problems/word-ladder/ seq += 1
# Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation num += 1
# sequence from beginWord to endWord, such that: longest = max(longest, seq)
# Only one letter can be changed at a time.
# Each transformed word must exist in the word list. Note that beginWord is not a transformed word. return longest
# Note:
# Return 0 if there is no such transformation sequence.
# All words have the same length.
# All words contain only lowercase alphabetic characters.
# You may assume no duplicates in the word list.
# python_1_to_1000/129_Sum_Root_to_Leaf_Numbers.py - m
# Bidirectional depth first search. Process wordList to be able to find neighbours.
# Time - O(n*k*k) to build graph for n words of length k. O(b^(d/2)) for bidirectional BFS with branching _author_ = 'jake'
# factor b and depth d _project_ = 'leetcode'
# Space - O(n*k) for graph
# https://leetcode.com/problems/sum-root-to-leaf-numbers/
from collections import defaultdict # Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
# An example is the root-to-leaf path 1->2->3 which represents the number 123.
class Solution(object): # Find the total sum of all root-to-leaf numbers.
def ladderLength(self, beginWord, endWord, wordList):
""" # Recursively find the sum of all paths from a node to all leaves having already seen path value of partial.
:type beginWord: str # Time - O(n)
:type endWord: str # Space - O(n)
:type wordList: List[str]
:rtype: int # Definition for a binary tree node.
""" class TreeNode(object):
length = 1 def __init__(self, x):
visited = set() self.val = x
if endWord not in wordList: self.left = None
return 0 self.right = None

graph = defaultdict(set) class Solution(object):

for word in wordList: # build a mapping of words reachable by changing one letter def sumNumbers(self, root):
for i in range(len(word)): """
wildcard = word[:i] + '_' + word[i + 1:] :type root: TreeNode
graph[wildcard].add(word) :rtype: int
"""
front, back = {beginWord}, {endWord} # frontiers in both directions return self.helper(root, 0)

while front: def helper(self, node, partial):

if front & back: # intersection between frontiers if not node: # no path to leaves
return length return 0
 partial = 10 * partial + node.val # incorporate this node.val _author_ = 'jake'
_project_ = 'leetcode'
if not node.left and not node.right: # base case, leaf
return partial # https://leetcode.com/problems/palindrome-partitioning-ii/
# Given a string s, partition s such that every substring of the partition is a palindrome.
return self.helper(node.left, partial) + self.helper(node.right, partial) # Return the minimum cuts needed for a palindrome partitioning of s.

# Initialise worst case for each prefix as length of prefix - 1. For each character expand outwards both odd and even
# python_1_to_1000/130_Surrounded_Regions.py - m # length palindromes. Whenever a palindrome is found, update min_cuts for that palindrome plus the left prefix.
# Time - O(n**2)
_author_ = 'jake' # Space - O(n)
_project_ = 'leetcode'
class Solution(object):
# https://leetcode.com/problems/surrounded-regions/ def minCut(self, s):
# Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. """
# A region is captured by flipping all 'O's into 'X's in that surrounded region. :type s: str
:rtype: int
# All edge cells containing 'O' and their adjoining 'O' cannot be surrounded. Temporarily flag these cells, by depth- """
# first search. Then convert all unflagged 'O' (that can be surrounded) to 'X'. min_cuts = [i-1 for i in range(len(s)+1)] # min_cuts[i] is min cuts for prefix s[:i] of length i
# Time - O(m * n)
# Space - O(m * n) for i in range(len(s)): # for each character as centre of palindrome

class Solution(object): left, right = i, i # expand to find all odd-length palindromes

def solve(self, board): while left >= 0 and right < len(s) and s[left] == s[right]:
""" min_cuts[right + 1] = min(min_cuts[right + 1], 1 + min_cuts[left])
:type board: List[List[str]] left -= 1
:rtype: void Do not return anything, modify board in-place instead. right += 1
"""
if not board or not board[0]: left, right = i, i+1 # expand to find all even-length palindromes
return while left >= 0 and right < len(s) and s[left] == s[right]:
min_cuts[right + 1] = min(min_cuts[right + 1], 1 + min_cuts[left])
rows, cols = len(board), len(board[0]) left -= 1
right += 1
to_expand = [] # stack of cells to be checked
return min_cuts[-1]
for row in range(rows): # add all edge cells to stack
to_expand += [(row, 0), (row, cols - 1)]
for col in range(1, cols-1):
to_expand += [(0, col), (rows - 1, col)] # python_1_to_1000/133_Clone_Graph.py - m

while to_expand: # if cell contains 'O', change to temporary 'T' and add neighbours to stack _author_ = 'jake'
row, col = to_expand.pop() _project_ = 'leetcode'
if 0 <= row < rows and 0 <= col < cols and board[row][col] == 'O':
board[row][col] = 'T' # https://leetcode.com/problems/clone-graph/
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]: # Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors
to_expand.append((row + dr, col + dc))
# When a new node is discovered it is copied, added to mapping and to_clone. Main while loop makes directed edges
for row in range(rows): # change all 'T' back to 'O' and all 'O' to 'X' # to neighbors.
for col in range(cols): # Time - O(m + n), edges + nodes
if board[row][col] == 'O': # Space - O(m + n)
board[row][col] = 'X'
elif board[row][col] == 'T': # Definition for a undirected graph node
board[row][col] = 'O' class UndirectedGraphNode(object):
def __init__(self, x):
self.label = x
# python_1_to_1000/131_Palindrome_Partitioning.py - m self.neighbors = []

_author_ = 'jake' class Solution(object):

_project_ = 'leetcode' def cloneGraph(self, node):
"""
# https://leetcode.com/problems/palindrome-partitioning/ :type node: UndirectedGraphNode
# Given a string s, partition s such that every substring of the partition is a palindrome. :rtype: UndirectedGraphNode
# Return all possible palindrome partitioning of s. """
if not node:
# If any prefix of s is a palindrome, then recursively partition the suffix into palindromes. return
# Time - O(2**n), for string of length n there we can partition or not after each letter cloned_start = UndirectedGraphNode(node.label)
# Space - O(2**n) to_clone = [node] # list (or set) of original nodes
node_mapping = {node : cloned_start} # original to cloned nodes
class Solution(object):
def partition(self, s): while to_clone:
"""
:type s: str node = to_clone.pop() # node is in mapping but does not have links to neighbors
:rtype: List[List[str]] clone_node = node_mapping[node]
"""
partitons = [] for neighbor in node.neighbors:
self.find_partitions(s, [], partitons) if neighbor not in node_mapping: # create copies of neighbors if not already existing
return partitons clone_neightbor = UndirectedGraphNode(neighbor.label)
node_mapping[neighbor] = clone_neightbor
to_clone.append(neighbor)
def find_partitions(self, s, partial, partitions): else:
if not s: clone_neightbor = node_mapping[neighbor]
partitions.append(partial)
clone_node.neighbors.append(clone_neightbor) # directed edges from clone_node
for i in range(1, len(s)+1):
prefix = s[:i] return cloned_start
if prefix == prefix[::-1]:
self.find_partitions(s[i:], partial + [s[:i]], partitions)

# python_1_to_1000/134_Gas_Station.py - m

_author_ = 'jake'
# python_1_to_1000/132_Palindrome_Partitioning_II.py - h _project_ = 'leetcode'

return xor
# https://leetcode.com/problems/gas-station/
# There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
# You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next # python_1_to_1000/137_Single_Number_II.py - m
# station (i+1). You begin the journey with an empty tank at one of the gas stations.
# Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. _author_ = 'jake'
_project_ = 'leetcode'
# If total gas >= total cost then a circuit is possible.
# Iterate round the circuit, updating current tank balance and total. If current tank is negative, cannot start at # https://leetcode.com/problems/single-number-ii/
# that station so update start to next possible station. # Given an array of integers, every element appears three times except for one. Find that single one.
# Time - O(n)
# Space - O(1) # If a bit is set in num, but not set in ones or twos then that bit is then set in ones.
# If a bit is set in num, set in ones but not in twos then that bit is then set in twos and not ones.
class Solution(object): # If a bit is set in num, but not set in ones or twos then that bit is then set in ones.
def canCompleteCircuit(self, gas, cost): # Time - O(n)
""" # Space - O(1)
:type gas: List[int]
:type cost: List[int] class Solution(object):
:rtype: int def singleNumber(self, nums):
""" """
start, tank, total = 0, 0, 0 :type nums: List[int]
:rtype: int
for station in range(len(gas)): """
balance = gas[station] - cost[station] ones, twos = 0, 0
tank += balance
total += balance for num in nums:
if tank < 0: ones = (ones ^ num) & ~twos # xor of all nums that have appeared once only
start = station + 1 twos = (twos ^ num) & ~ones # xor of all nums that have appeared twice only
tank = 0
return ones
return -1 if total < 0 else start

# python_1_to_1000/135_Candy.py - h # python_1_to_1000/138_Copy_List_with_Random_Pointer.py

_author_ = 'jake' _author_ = 'jake'

_project_ = 'leetcode' _project_ = 'leetcode'

# https://leetcode.com/problems/candy/ # https://leetcode.com/problems/copy-list-with-random-pointer/
# There are N children standing in a line. Each child is assigned a rating value. # A linked list is given such that each node contains an additional random pointer which could point to any node in the
# You are giving candies to these children subjected to the following requirements: list or null.
# Each child must have at least one candy. # Return a deep copy of the list.
# Children with a higher rating get more candies than their neighbors.
# What is the minimum candies you must give? # Duplicate every node and insert copy in list after original node. Link copied nodes to random pointers, which
# follow random pointers of original nodes. Separate out original and copied lists.
# Find how many candies are required due to children on left and then on right. # Time - O(n)
# Result for each child is the higher of those values. # Space - O(1)
# Time - O(n)
# Space - O(n) # Definition for singly-linked list with a random pointer.
class RandomListNode(object):
class Solution(object): def __init__(self, x):
def candy(self, ratings): self.label = x
""" self.next = None
:type ratings: List[int] self.random = None
:rtype: int
""" class Solution(object):
left = [1 for _ in range(len(ratings))] # default to 1 per child def copyRandomList(self, head):
right = [1 for _ in range(len(ratings))] """
:type head: RandomListNode
for i in range(1, len(ratings)): # increase above previous child if greater rating :rtype: RandomListNode
if ratings[i] > ratings[i-1]: """
left[i] = left[i-1] + 1 node = head
while node:
candies = left[-1] # rightmost child not included in loop below next = node.next
for i in range(len(ratings)-2, -1, -1): copy = RandomListNode(node.label)
if ratings[i] > ratings[i+1]: # increase if greater rating node.next = copy
right[i] = right[i+1] + 1 copy.next = next
candies += max(left[i], right[i]) # child gets higher of candies due to left and right node = next

return candies node = head

while node:
if node.random:
# python_1_to_1000/136_Single_Number.py node.next.random = node.random.next
node = node.next.next
_author_ = 'jake'
_project_ = 'leetcode' pseudo = prev = RandomListNode(0)
node = head
# https://leetcode.com/problems/single-number/ while node:
# Given an array of integers, every element appears twice except for one. Find that single one. prev.next = node.next
node.next = node.next.next
# Any number xor with itself is zero. node = node.next
# Time - O(n) prev = prev.next
# Space - O(1)
return pseudo.next
class Solution(object):
def singleNumber(self, nums):
""" # python_1_to_1000/139_Word_Break.py - m
:type nums: List[int]
:rtype: int _author_ = 'jake'
""" _project_ = 'leetcode'
xor = 0
for num in nums: # https://leetcode.com/problems/word-break/
xor ^= num # Given a string s and a dictionary of words dict, determine if s can be segmented into a
# space-separated sequence of one or more dictionary words. # Given a linked list, determine if it has a cycle in it.

# Dynamic programming. A prefix can be made from words in dictionary if it can be split into a shorter prefix # Increment fast pointer by 2 nodes and slow pointer by 1 node per time step. If loop, fast will catch up with slow
# that can be made and another word in dictionary. # else fast will reach end.
# Time - O(n**3), there are O(n**2) substrings s[j:i], each taking O(n) to create # Time - O(n)
# Space - O(n) # Space - O(1)

class Solution(object): # Definition for singly-linked list.

def wordBreak(self, s, wordDict): class ListNode(object):
""" def __init__(self, x):
:type s: str self.val = x
:type wordDict: Set[str] self.next = None
:rtype: bool
""" class Solution(object):
can_make = [False] * (len(s)+1) # can_make[i] is True if can make prefix of length i def hasCycle(self, head):
can_make[0] = True """
:type head: ListNode
for i in range(1, len(s)+1): # prefix length :rtype: bool
for j in range(i-1, -1, -1): # j is existing prefix, start with longest + shortest new word """
if can_make[j] and s[j:i] in wordDict: fast, slow = head, head
can_make[i] = True while fast and fast.next:
break slow = slow.next
fast = fast.next.next
return can_make[-1] if fast == slow:
return True
return False

# python_1_to_1000/140_Word_Break_II.py - h

_author_ = 'jake' # python_1_to_1000/142_Linked_List_Cycle_II.py - m

_project_ = 'leetcode'
_author_ = 'jake'
# https://leetcode.com/problems/word-break-ii/ _project_ = 'leetcode'
# Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid
dictionary word. # https://leetcode.com/problems/linked-list-cycle-ii/
# Return all such possible sentences. # Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

# Test if word can be broken as per problem 139. For all prefixes of s in the dictionary, recurse on the suffix. # If there are k nodes before a cycle of c nodes, when slow reaches start of loop, fast is k % c into loop.
# Time - O(n**3 * 2**(n-1)) # When fast reaches slow, both are c - k % c into the loop. Restart fast at head and move both 1 step at a time.
# Space - O(n * 2**(n-1)), 2**(n-1) possible partitions of string of length n (every combination of gaps between words) # After k steps, both are at start of loop.
# each partiton is of length n. Memo for shorter suffixes does not impact big O. # Time - O(n)
# Space - O(1)
class Solution(object):
# Definition for singly-linked list.
def canBreak(self, s, wordDict): class ListNode(object):
can_make = [False] * (len(s)+1) # can_make[i] is True if can make prefix of length i def __init__(self, x):
can_make[0] = True self.val = x
for i in range(1, len(s)+1): # prefix length self.next = None
for j in range(i-1, -1, -1): # j is existing prefix, start with longest + shortest new word
if can_make[j] and s[j:i] in wordDict: class Solution(object):
can_make[i] = True def detectCycle(self, head):
break """
return can_make[-1] :type head: ListNode
:rtype: ListNode
"""
def wordBreak(self, s, wordDict): fast, slow = head, head
""" while fast and fast.next:
:type s: str fast = fast.next.next
:type wordDict: Set[str] slow = slow.next
:rtype: List[str] if fast == slow:
"""
if not self.canBreak(s, wordDict): fast = head
return [] while fast != slow:
result_lists = self.break_word(s, 0, wordDict, {}) fast = fast.next
return [" ".join(result) for result in result_lists] # convert back to strings slow = slow.next
return slow

def break_word(self, s, left, wordDict, memo): # break from s[left] onwards return None

if left >= len(s): # base case

return [[]]
if left in memo: # python_1_to_1000/143_Reorder_List.py - m
return memo[left]
_author_ = 'jake'
results = [] _project_ = 'leetcode'
for i in range(left+1, len(s)+1): # try all possible prefixes
prefix = s[left:i] # https://leetcode.com/problems/reorder-list/
suffix_breaks = self.break_word(s, i, wordDict, memo) # Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
if suffix_breaks and prefix in wordDict: # Do this in-place without altering the nodes' values.
for suffix_break in suffix_breaks:
results.append([prefix] + suffix_break) # Find the mid point, reverse list after mid point, then interleave the 2 sides.
# Time - O(n)
memo[left] = results[:] # Space - O(1)
return results
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
# python_1_to_1000/141_Linked_List_Cycle.py self.val = x
self.next = None
_author_ = 'jake'
_project_ = 'leetcode' class Solution(object):
def reorderList(self, head):
# https://leetcode.com/problems/linked-list-cycle/ """

:type head: ListNode # which is reversed before returning result).

:rtype: void Do not return anything, modify head in-place instead. # Add left children to stack before right so right subtrees are visited before left.
""" # Alternatively, recurse left, recurse right then visit node.
if not head: # Time - O(n)
return None # Space - O(n)

# set slow to mid for odd length lists, first of second half for even # Definition for a binary tree node.
fast, slow = head, head class TreeNode(object):
while fast and fast.next: def __init__(self, x):
fast = fast.next.next self.val = x
slow = slow.next self.left = None
self.right = None
# reverse nodes after slow (slow has pointers from both sides)
prev, node = None, slow from collections import deque
while node:
prev, node.next, node = node, prev, node.next class Solution(object):
def postorderTraversal(self, root):
first, second = head, prev # heads of the normal and reversed lists """
while second.next: :type root: TreeNode
first.next, first = second, first.next # insert second after first :rtype: List[int]
second.next, second = first, second.next # insert first after second """
if not root:
return []

result = deque() # deque instead of list so we can append at front

# python_1_to_1000/144_Binary_Tree_Preorder_Traversal.py stack = [root]

_author_ = 'jake' while stack:

_project_ = 'leetcode' node = stack.pop()
result.appendleft(node.val)
# https://leetcode.com/problems/binary-tree-preorder-traversal/
# Given a binary tree, return the preorder traversal of its nodes' values. if node.left:
stack.append(node.left)
# Maintain a stack of nodes discovered and to be visited. Add right children to stack before left so left subtrees if node.right:
# are visited before right. stack.append(node.right)
# Alternatively, visit node, recurse left then recurse right.
# Time - O(n) return list(result)
# Space - O(n)

# Definition for a binary tree node. class Solution2(object):

class TreeNode(object): def postorderTraversal(self, root):
def __init__(self, x): result = []
self.val = x self.postorder(root, result)
self.left = None return result
self.right = None
def postorder(self, node, result):
class Solution(object): if not node:
def preorderTraversal(self, root): return
""" self.postorder(node.left, result)
:type root: TreeNode self.postorder(node.right, result)
:rtype: List[int] result.append(node.val)
"""
if not root:
return []

preorder = [] # python_1_to_1000/146_LRU_Cache.py - m
stack = [root]
_author_ = 'jake'
while stack: _project_ = 'leetcode'
node = stack.pop()
preorder.append(node.val) # https://leetcode.com/problems/lru-cache/
if node.right: # Design and implement a data structure for Least Recently Used cache. It should support the following operations:
stack.append(node.right) # push right first so left is popped first # get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
if node.left: # set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
stack.append(node.left) # it should invalidate the least recently used item before inserting a new item.

return preorder # Dictionary stores keys with values of nodes. Nodes form double linked list containing key, value pairs. DLL is in
# order of use with least recent at head and most recent at tail.
# Time - O(1) to set and get
class Solution2(object): # Space - O(n)
def preorderTraversal(self, root):
result = [] class Node:
self.preorder(root, result) def __init__(self, key, val):
return result self.key = key
self.val = val
def preorder(self, node, result): self.prev = None
if not node: self.next = None
return
result.append(node.val) class DLL:
self.preorder(node.left, result) def __init__(self):
self.preorder(node.right, result) self.head = Node(None, None) # least recently used, remove at head
self.tail = Node(None, None) # most recently used, add and update at tail
self.head.next = self.tail
self.tail.prev = self.head
# python_1_to_1000/145_Binary_Tree_Postorder_Traversal.py
def insert(self, node):
_author_ = 'jake' node.prev, self.tail.prev.next = self.tail.prev, node
_project_ = 'leetcode' node.next, self.tail.prev = self.tail, node

# https://leetcode.com/problems/binary-tree-postorder-traversal/ def remove_at_head(self):

# Given a binary tree, return the postorder traversal of its nodes' values. node = self.head.next
node.next.prev = self.head
# Maintain a stack of nodes discovered and to be visited. Nodes are added to front of result (or the end of a list self.head.next = self.head.next.next
 key = node.key
del node insertion = dummy
return key while insertion.next.val <= node.val:
insertion = insertion.next
def update(self, node):
node.prev.next = node.next # take out from existing position node.next = insertion.next # put node after insertion
node.next.prev = node.prev insertion.next = node
self.insert(node) # put back at tail
return dummy.next

class LRUCache(object):

def __init__(self, capacity): # python_1_to_1000/148_Sort_List.py - m

"""
:type capacity: int _author_ = 'jake'
""" _project_ = 'leetcode'
self.capacity = capacity
self.queue = DLL() # https://leetcode.com/problems/sort-list/
self.mapping = {} # Sort a linked list in O(n log n) time using constant space complexity.

# Base case is empty list or single node. Else recursively split list in half, sort halves and merge.
def get(self, key): # Time - O(n log n)
""" # Space - O(n)
:rtype: int
""" # Definition for singly-linked list.
if key not in self.mapping: class ListNode(object):
return -1 def __init__(self, x):
node = self.mapping[key] self.val = x
self.queue.update(node) self.next = None
return node.val
class Solution(object):
def sortList(self, head):
def set(self, key, value): """
""" :type head: ListNode
:type key: int :rtype: ListNode
:type value: int """
:rtype: nothing if not head or not head.next:
""" return head
if key in self.mapping: # update value and move node to tail
node = self.mapping[key] fast, slow, prev = head, head, None
node.val = value while fast and fast.next:
self.queue.update(node) prev, slow, fast = slow, slow.next, fast.next.next
return
prev.next = None
node = Node(key, value) # else new key one = self.sortList(head)
self.mapping[key] = node two = self.sortList(slow)
self.queue.insert(node)
return self.merge(one, two)
if self.capacity == 0: # cache is full, eject oldest
removed_key = self.queue.remove_at_head()
del self.mapping[removed_key] def merge(self, one, two):
else: # decrement capacity
self.capacity -= 1 dummy = merged = ListNode(None)

while one and two:

# python_1_to_1000/147_Insertion_Sort_List.py - m if one.val <= two.val:

merged.next = one
_author_ = 'jake' one = one.next
_project_ = 'leetcode' else:
merged.next = two
# https://leetcode.com/problems/insertion-sort-list/ two = two.next
# Sort a linked list using insertion sort. merged = merged.next

# Maintain a sorted part of the list. For each next node, find its correct location by iterating along sorted section. merged.next = one or two # add remaining list
# Time - O(n**2)
# Space - O(1) return dummy.next

# Definition for singly-linked list.

class ListNode(object): # python_1_to_1000/149_Max_Points_on_a_Line.py - h
def __init__(self, x):
self.val = x _author_ = 'jake'
self.next = None _project_ = 'leetcode'

class Solution(object): # https://leetcode.com/problems/max-points-on-a-line/

def insertionSortList(self, head): # Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
"""
:type head: ListNode # For each point, calculate the gradient of the line to all other points and store in dictionary. Python accepts
:rtype: ListNode # floats as dictionary keys and floating point accuracy is not an issue for sufficiently small x and y.
""" # Infinite slopes are stored with key of 'inf'. If both x and y are the same, both points lie on all lines with the
sorted_tail = dummy = ListNode(float('-inf')) # sorted_tail is last node of sorted section # first point. Calculate the max number of points on a line with each base point in turn, only considering other points
dummy.next = head # that have not already been the base point.
# Time - O(n**2)
while sorted_tail.next: # Space - O(n)

node = sorted_tail.next # Definition for a point.

class Point(object):
if node.val >= sorted_tail.val: # node already in correct place def __init__(self, a=0, b=0):
sorted_tail = sorted_tail.next self.x = a
continue self.y = b

sorted_tail.next = sorted_tail.next.next # cut out node from collections import defaultdict

:rtype: str
class Solution(object): """
def maxPoints(self, points): words = s.split()
""" return " ".join(words[::-1])
:type points: List[Point]
:rtype: int
""" # python_1_to_1000/152_Maximum_Product_Subarray.py - m
if len(points) <= 2:
return len(points) _author_ = 'jake'
_project_ = 'leetcode'
overall_max = 2
# https://leetcode.com/problems/maximum-product-subarray/
for i, point in enumerate(points): # for each point # Find the contiguous subarray within an array (containing at least one number) which has the largest product.

gradients = defaultdict(int) # key is gradient, value is nb lines involving point with this gradient # Calculate the most positive and most negative subarray products ending at each element.
max_points = 1 # point is on every line # Either the element alone or multiplied by previous most positive or most negative.
# Time - O(n)
for point_2 in points[i+1:]: # check all # Space - O(1)

if point.x == point_2.x: class Solution(object):

if point.y == point_2.y: # same point, on all lines def maxProduct(self, nums):
max_points += 1 """
else: # infinite gradient :type nums: List[int]
gradients['inf'] += 1 :rtype: int
"""
else: largest_product = float('-inf')
gradient = (point_2.y - point.y) / float(point_2.x - point.x) most_neg, most_pos = 1, 1
gradients[gradient] += 1
for num in nums:
if gradients: most_pos, most_neg = max(num, most_pos * num, most_neg * num), min(num, most_pos * num, most_neg * num)
max_points += max(gradients.values()) largest_product = max(largest_product, most_pos, most_neg)
overall_max = max(overall_max, max_points)
return largest_product
return overall_max

# python_1_to_1000/153_Find_Minimum_in_Rotated_Sorted_Array.py - m

# python_1_to_1000/150_Evaluate_Reverse_Polish_Notation.py - m _author_ = 'jake'

_project_ = 'leetcode'
_author_ = 'jake'
_project_ = 'leetcode' # https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
# Suppose a sorted array is rotated at some pivot unknown to you beforehand.
# https://leetcode.com/problems/evaluate-reverse-polish-notation/ # (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
# Evaluate the value of an arithmetic expression in Reverse Polish Notation. # Find the minimum element.
# Valid operators are +, -, *, /. Each operand may be an integer or another expression. # You may assume no duplicate exists in the array.

# Push numbers onto stack. Apply operators to top 2 members of stack and push back result. # If right element is less than mid element, min mist be to right of mid. Else min mist be mid or left.
# Faster but less concise without using eval(). # Time - O(log n)
# Time - O(n) # Space - O(1)
# Space - O(n)
class Solution(object):
class Solution(object): def findMin(self, nums):
def evalRPN(self, tokens): """
""" :type nums: List[int]
:type tokens: List[str] :rtype: int
:rtype: int """
""" left = 0
ops = {'+', '-', '/', '*'} right = len(nums)-1
stack = []
while left < right:
for token in tokens:
if nums[left] <= nums[right]: # not rotated, left is min
if token in ops: break
right = stack.pop()
left = stack.pop() mid = (left + right) // 2
if token == '/': if nums[right] < nums[mid]: # min must be on right of mid
stack.append(int(left / float(right))) # round down left = mid + 1
else: else: # nums[right] > nums[mid]
stack.append((eval(str(left) + token + str(right)))) right = mid # min must be mid or on left
else: # nums[right] != nums[mid] because loop terminated if left == right and if right == left + 1 then
stack.append(int(token)) # mid == left and since nums are unique num[left] != nums[right]

return stack[-1] return nums[left]

# python_1_to_1000/154_Find_Minimum_in_Rotated_Sorted_Array_II.py - h
# python_1_to_1000/151_Reverse_Words_in_a_String.py - m
_author_ = 'jake'
_author_ = 'jake' _project_ = 'leetcode'
_project_ = 'leetcode'
# https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
# https://leetcode.com/problems/reverse-words-in-a-string/ # Follow up for "153 Find Minimum in Rotated Sorted Array": What if duplicates are allowed?
# Given an input string, reverse the string word by word.
# As per problem 153 except if nums[left] == nums[right] == nums[mid] must search both left and right.
# Parse int a list of words by spaces, reverse word list and recombine with spaces. # Time - O(n)
# Time - O(n) # Space - O(1)
# Space - O(n)
class Solution(object):
class Solution(object): def findMin(self, nums):
def reverseWords(self, s): """
""" :type nums: List[int]
:type s: str :rtype: int
 """ # class TreeNode(object):
left, right = 0, len(nums)-1 # def __init__(self, x):
# self.val = x
while left < right: # self.left = None
# self.right = None
if nums[left] < nums[right]: # already sorted
break class Solution(object):
def upsideDownBinaryTree(self, root):
mid = (left + right) // 2 """
:type root: TreeNode
if nums[right] < nums[mid]: :rtype: TreeNode
left = mid + 1 # discontinuity on RHS of mid """
elif nums[right] > nums[mid] or nums[left] > nums[mid]: if not root or not root.left: # if no left then no right, leaf
right = mid # discontinuity is mid or LHS return root
else: # nums[right] == nums[mid] == nums[left]
left += 1 new_root = self.upsideDownBinaryTree(root.left) # recurse left
right -= 1 node = new_root
while node.right: # traverse as far right as possible
return nums[left] node = node.right

node.left = root.right
# python_1_to_1000/155_Min_Stack.py - m node.right = root
root.left = None
_author_ = 'jake' root.right = None
_project_ = 'leetcode'
return new_root
# https://leetcode.com/problems/min-stack/
# Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
# push(x) -- Push element x onto stack. # python_1_to_1000/157_Read_N_Characters_Given_Read4.py
# pop() -- Removes the element on top of the stack.
# top() -- Get the top element. _author_ = 'jake'
# getMin() -- Retrieve the minimum element in the stack. _project_ = 'leetcode'

# Main stack has all items, mins stack has items less than or equal to previous min. # https://leetcode.com/problems/read-n-characters-given-read4/
# Note : no error handling for empty stack required # The API: int read4(char *buf) reads 4 characters at a time from a file.
# Time - O(1) # The return value is the actual number of characters read. Eg, it returns 3 if only 3 characters are left in the file.
# Space - O(n) # By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

class MinStack(object): # Read up to 4 chars into buf4 and copy to buf (which is modified in-place).
# Time - O(n)
def __init__(self): # Space - O(n)
"""
initialize your data structure here. # The read4 API is already defined for you.
""" # @param buf, a list of characters
self.main = [] # @return an integer
self.mins = [] def read4(buf):
pass
def push(self, x):
""" class Solution:
:type x: int def read(self, buf, n):
:rtype: void
""" total_chars, last_chars = 0, 4
self.main.append(x)
if not self.mins or x <= self.mins[-1]: while last_chars == 4 and total_chars < n:
self.mins.append(x)
buf4 = [""] * 4 # temporary buffer
def pop(self): last_chars = min(read4(buf4), n - total_chars)
""" buf[total_chars:total_chars+last_chars] = buf4
:rtype: void total_chars += last_chars
"""
item = self.main.pop() return total_chars
if item == self.mins[-1]:
self.mins.pop()
# python_1_to_1000/158_Read_N_Characters_Given_Read4_II_-_Call_multiple_times.py - h
def top(self):
""" _author_ = 'jake'
:rtype: int _project_ = 'leetcode'
"""
return self.main[-1] # https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/
# The API: int read4(char *buf) reads 4 characters at a time from a file.
def getMin(self): # The return value is the actual number of characters read.
""" # By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
:rtype: int # The read function may be called multiple times.
"""
return self.mins[-1] # Use a double-linked list to store any characters read by read4 but not required. Use those characters first
# on the next call of read().
# Time - O(n)
# python_1_to_1000/156_Binary_Tree_Upside_Down.py - m # Space - O(n)

_author_ = 'jake' # The read4 API is already defined for you.

_project_ = 'leetcode' # @param buf, a list of characters
# @return an integer
# https://leetcode.com/problems/binary-tree-upside-down/ def read4(buf):
# Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the pass
# same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned
# into left leaf nodes. Return the new root. from collections import deque

# Base case for recursion is a leaf node or None. Recursively process left subtree, find rightmost path, add previous class Solution(object):
# right on left and previous root on right. def __init__(self):
# Time - O(n) self.leftover = deque() # store chars read by read4 but not added previous buf
# Space - O(1)
def read(self, buf, n):
# Definition for a binary tree node. """

:type buf: Destination buffer (List[str]) """

:type n: Maximum number of characters to read (int) :type head1, head1: ListNode
:rtype: The number of characters read (int) :rtype: ListNode
""" """
total_chars, added_chars, read_chars = 0, 4, 0 if not headA or not headB:
return None
while self.leftover and total_chars < n: # add leftover chars to buf
buf[total_chars] = self.leftover.popleft() savedA, savedB = headA, headB
total_chars += 1
while headA != headB:
while added_chars == 4 and total_chars < n: # add blocks of 4 chars up to eof headA = savedB if not headA else headA.next
buf4 = [""] * 4 # temporary buffer headB = savedA if not headB else headB.next
read_chars = read4(buf4)
added_chars = min(read_chars, n - total_chars) gc.collect() # required to pass leetocde strict memory usage
buf[total_chars:total_chars+added_chars] = buf4 return headA
total_chars += added_chars

while read_chars > added_chars: # save extra chars class Solution2(object):

self.leftover.append(buf4[added_chars]) def getIntersectionNode(self, headA, headB):
added_chars += 1 """
:type head1, head1: ListNode
return total_chars :rtype: ListNode
"""
if not headA or not headB:
# python_1_to_1000/159_Longest Substring_with_At_Most_Two_Distinct_Characters.py - m return None

_author_ = 'jake' savedA, savedB = headA, headB

_project_ = 'leetcode' len_diff = 0

# https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ while headA.next:

# Given a string, find the length of the longest substring T that contains at most 2 distinct characters. len_diff += 1
headA = headA.next
# Maintain a window of the longest substring. If a 3rd char is found, reset the window start to after the first while headB.next:
# seen char. len_diff -= 1
# Time - O(n) headB = headB.next
# Space - O(1)
if headA != headB: # no intersection
class Solution(object): return
def lengthOfLongestSubstringTwoDistinct(self, s):
""" headA, headB = savedA, savedB
:type s: str
:rtype: int while len_diff != 0: # traverse longer list for length difference
""" if len_diff > 0:
start, max_substring = 0, 0 headA = headA.next
last_seen = {} # key is char, value is last index of char len_diff -= 1
else:
for i, c in enumerate(s): headB = headB.next
len_diff += 1
if c in last_seen or len(last_seen) < 2: # extend substring with same start
max_substring = max(max_substring, i - start + 1) while headA != headB:
headA = headA.next
else: # c not in current substring and 2 chars seen headB = headB.next
for seen in last_seen:
if seen != s[i-1]: # find the char that is not the previous char gc.collect()
start = last_seen[seen] + 1 # move start to after this char return headA
del last_seen[seen]
break
# python_1_to_1000/161_One_Edit_Distance.py - m
last_seen[c] = i
_author_ = 'jake'
return max_substring _project_ = 'leetcode'

# https://leetcode.com/problems/one-edit-distance/
# Given two strings s and t, determine if they are both one edit distance apart.

# python_1_to_1000/160_Intersection_of_Two_Linked_Lists.py # If same lengths find the one different char (replacement edit) and test all else are same.
# If length diff of 1, find the extra char in longer and check all else is the same.
_author_ = 'jake' # Time - O(n)
_project_ = 'leetcode' # Space - O(1)

# https://leetcode.com/problems/intersection-of-two-linked-lists/ class Solution(object):

# Write a program to find the node at which the intersection of two singly linked lists begins. def isOneEditDistance(self, s, t):
# If the two linked lists have no intersection at all, return null. """
# The linked lists must retain their original structure after the function returns. :type s: str
# You may assume there are no cycles anywhere in the entire linked structure. :type t: str
:rtype: bool
# Traverse both lists, when reach end switch to start of other list. If lists have l1 and l2 nodes before intersect """
# and k nodes after then both traversals intersect after l1 + l2 + k nodes. If no intersection, k = 0 and both pointers diff = len(s) - len(t)
# meet at None. if abs(diff) > 1: # early break
# Alternatively, count lengths and traverse longer list for length difference before traversing both in step. return False
# Time - O(n)
# Space - O(1) edit = False
if diff == 0: # one replacement
import gc # used to manually clear the memory for c_s, c_t in zip(s, t):
if c_s != c_t:
# Definition for singly-linked list. if edit: # already seen a replacement
class ListNode(object): return False
def __init__(self, x): edit = True
self.val = x return edit # False if no replacement
self.next = None
else: # abs(diff) == 1
class Solution(object): long, short = s, t
def getIntersectionNode(self, headA, headB): if diff < 0:
 long, short = short, long # Return 0 if the array contains less than 2 elements.
i = 0 # find the mismatch # You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
while i < len(short) and long[i] == short[i]:
i += 1 # Bucket sort. By pigeon-hole principle we ensure at least one bucket is empty or numbers are equally separated
return long[i+1:] == short[i:] # remainders must be same # by the same distance.
# Time - O(n)
# Space - O(n)
# python_1_to_1000/162_Find_Peak_Element.py - m
class Solution(object):
_author_ = 'jake' def maximumGap(self, nums):
_project_ = 'leetcode' """
:type nums: List[int]
# https://leetcode.com/problems/find-peak-element/ :rtype: int
# A peak element is an element that is greater than its neighbors. """
# Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. if len(nums) < 2:
# The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. return 0
# You may imagine that num[-1] = num[n] = -∞.
lower = min(nums)
# If array has 3 or more elements, return mid if it is a peak else recurse on the side with a higher element. difference = max(nums) - lower
# If array has < 3 elements, return index of greater. gaps = len(nums) - 1 # number of spaces between sorted nums
# Time - O(log n) if difference == 0: # all nums are same
# Space - O(1) return 0

class Solution(object): width = difference // gaps # range of integers // number of gaps

def findPeakElement(self, nums): if width == 0:
""" width = 1
:type nums: List[int]
:rtype: int nb_buckets = 1 + difference // width # ensure max(nums) goes in final bucket
"""
left, right = 0, len(nums)-1 buckets = [[None, None] for _ in range(nb_buckets)] # max and min of each bucket

while left < right - 1: # at least 3 elements for num in nums:

bucket = (num - lower) // width
mid = (left + right) // 2 buckets[bucket][0] = min(buckets[bucket][0], num) if buckets[bucket][0] != None else num
buckets[bucket][1] = max(buckets[bucket][1], num) if buckets[bucket][1] != None else num
if nums[mid] >= nums[mid+1] and nums[mid] >= nums[mid-1]:
return mid last_used_bucket = 0
if nums[mid+1] > nums[mid]: # RHS is higher (LHS could be also but arbitrarily choose RHS) max_gap = difference // gaps # default case of no empty buckets
left = mid + 1 for i in range(nb_buckets - 1):
else: # LHS must be higher if RHS is not if not buckets[i][0] and buckets[i + 1][0]:
right = mid - 1 max_gap = max(max_gap, buckets[i + 1][0] - buckets[last_used_bucket][1])
elif buckets[i][0]:
if nums[left] >= nums[right]: last_used_bucket = i
return left
return right return max_gap

# python_1_to_1000/163_Missing_Ranges.py # python_1_to_1000/165_Compare_Version_Numbers.py - m

_author_ = 'jake' _author_ = 'jake'

_project_ = 'leetcode' _project_ = 'leetcode'

# https://leetcode.com/problems/missing-ranges/ # https://leetcode.com/problems/compare-version-numbers/
# Given a sorted integer array where elements are in the inclusive range [lower, upper], return its missing ranges. # Compare two version numbers version1 and version2.
# For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"]. # If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
# You may assume that the version strings are non-empty and contain only digits and the . character.
# Track the last number seen. If num == last_seen+2 then last_seen+1 is the start and end of a missing range. # The . character does not represent a decimal point and is used to separate number sequences.
# If num > last_seen+2 then inclusive range last_seen+1 to num-1 is missing. Update last_seen. Do nothing if
# num is last_seen or last_seen+1 since nothing is missing. # Split by '.' and pad shorter list with [0]. Then compare each section.
# Time - O(n) # Time - O(n)
# Space - O(n) # Space - O(n)

class Solution(object): import itertools

def findMissingRanges(self, nums, lower, upper):
""" class Solution(object):
:type nums: List[int] def compareVersion(self, version1, version2):
:type lower: int """
:type upper: int :type version1: str
:rtype: List[str] :type version2: str
""" :rtype: int
last_seen = lower-1 """
nums.append(upper+1) v1 = [int(v) for v in version1.split('.')] # split by "." and convert to int
missing = [] v2 = [int(v) for v in version2.split('.')]

for num in nums: for i1, i2 in itertools.zip_longest(v1, v2, fillvalue=0): # pad shorter with zeros
if num == last_seen + 2: if i1 > i2:
missing.append(str(last_seen+1)) return 1
elif num > last_seen + 2: if i1 < i2:
missing.append(str(last_seen+1) + '->' + str(num-1)) return -1
last_seen = num
return 0 # all version components are same
return missing

# python_1_to_1000/166_Fraction_to_Recurring_Decimal.py - m

# python_1_to_1000/164_Maximum_Gap.py - m _author_ = 'jake'

_project_ = 'leetcode'
_author_ = 'jake'
_project_ = 'leetcode' # https://leetcode.com/problems/fraction-to-recurring-decimal/
# Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
# https://leetcode.com/problems/maximum-gap/ # If the fractional part is repeating, enclose the repeating part in parentheses.
# Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

# Find the initial integer part then repeatedly multiply by 10, divide by denominator and calculate remainder. If column = deque() # faster than list for appendleft()
# same remainder repeats there is a cycle. while n > 0:
n, output = divmod(n-1, 26)
class Solution(object): column.appendleft(output)
def fractionToDecimal(self, numerator, denominator):
""" return "".join([chr(i+ord('A')) for i in column])
:type numerator: int
:type denominator: int
:rtype: str
"""
if denominator == 0: # python_1_to_1000/169_Majority_Element.py
return None
decimal = [] # store result as a list _author_ = 'jake'
if numerator * denominator < 0: # negative sign _project_ = 'leetcode'
decimal.append('-')
# https://leetcode.com/problems/majority-element/
output, remainder = divmod(abs(numerator), abs(denominator)) # divide and modulo combined # Given an array of size n, find the majority element. The majority element appears more than [n/2] times.
decimal.append(str(output)) # You may assume that the array is non-empty and the majority element always exist in the array.
if remainder == 0:
return "".join(decimal) # When the count is zero, the next element becomes the candidate. When an element is the same as the candidate,
# increment the count, else decrement the count.
decimal.append('.') # Time - O(n)
seen = {} # key is remainder, value is index in decimal # Space - O(1)

while remainder != 0: class Solution(object):

if remainder in seen: def majorityElement(self, nums):
return "".join(decimal[:seen[remainder]] + ['('] + decimal[seen[remainder]:] + [')']) """
seen[remainder] = len(decimal) :type nums: List[int]
output, remainder = divmod(remainder*10, abs(denominator)) :rtype: int
decimal.append(str(output)) """
count, candidate = 0, None
return "".join(decimal)
for i, num in enumerate(nums):

if count == 0:
candidate = num
# python_1_to_1000/167_Two_Sum_II_-_Input_array_is_sorted.py - m
if candidate == num:
_author_ = 'jake' count += 1
_project_ = 'leetcode' else:
count -= 1
# https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
# Given an array of integers that is already sorted in ascending order, find an ordered pair of indices of two numbers return candidate
# such that they add up to a specific target number.
# Please note that your returned answers (both index1 and index2) are not zero-based.
# You may assume that each input would have exactly one solution. # python_1_to_1000/170_Two_Sum_III_-_Data_structure_design.py

# Start pointers at both ends of array. Increment left if sum is too low or decrement right if sum is too high. _author_ = 'jake'
# Time - O(n) _project_ = 'leetcode'
# Space - O(1)
# https://leetcode.com/problems/two-sum-iii-data-structure-design/
class Solution(object): # Design and implement a TwoSum class. It should support the following operations: add and find.
def twoSum(self, numbers, target): # add - Add the number to an internal data structure.
""" # find - Find if there exists any pair of numbers which sum is equal to the value.
:type numbers: List[int]
:type target: int # Use a dictionary to store each number and whether it has been added multiple times. To find, for each num in
:rtype: List[int] # dictionary look for the difference between target value and that num, or for the num to be duplicated if it
""" # is half of the target value.
left, right = 0, len(numbers)-1 # Time - O(1) to add, O(n) to find
# Space - O(n)
while True:
class TwoSum(object):
pair_sum = numbers[left] + numbers[right]
if pair_sum == target: def __init__(self):
return [left+1, right+1] """
initialize your data structure here
if pair_sum < target: """
left += 1 self.nums = {} # key is num, value is True if num is duplicated else False
else:
right -= 1 def add(self, number):
"""
Add the number to an internal data structure.
# python_1_to_1000/168_Excel_Sheet_Column_Title.py :rtype: nothing
"""
_author_ = 'jake' self.nums[number] = number in self.nums # False for first occurence, True for multiple occurrences
_project_ = 'leetcode'
def find(self, value):
# https://leetcode.com/problems/excel-sheet-column-title/ """
# Given a positive integer, return its corresponding column title as appear in an Excel sheet. Find if there exists any pair of numbers which sum is equal to the value.
# For example:, 1 -> A, 2 -> B, 3 -> C, ..., 26 -> Z, 27 -> AA :type value: int
:rtype: bool
# Generate characters starting with least significant by calculating remainder of division by 26. """
# Time - O(log n) for num in self.nums:
# Space - O(log n) if value == 2 * num: # need num to be duplicated
if self.nums[num]:
from collections import deque return True
else: # look for difference
class Solution(object): if value - num in self.nums:
def convertToTitle(self, n): return True
""" return False
:type n: int
:rtype: str
"""
# python_1_to_1000/171_Excel_Sheet_Column_Number.py def next(self):
"""
_author_ = 'jake' :rtype: int
_project_ = 'leetcode' """
node = self.stack.pop()
# https://leetcode.com/problems/excel-sheet-column-number/ result = node.val
# Given a column title as appear in an Excel sheet, return its corresponding column number. if node.right:
node = node.right
# For each char, multiply previous result by 26 and add value of char while node:
# Time - O(n) self.stack.append(node)
# Space - O(n) node = node.left
return result
class Solution(object):
def titleToNumber(self, s):
""" # python_1_to_1000/174_Dungeon_Game.py - h
:type s: str
:rtype: int _author_ = 'jake'
""" _project_ = 'leetcode'
result = 0
for c in s: # https://leetcode.com/problems/dungeon-game/
result = result*26 + ord(c) - ord('A') + 1 # The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon.
return result # The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the
# top-left room and must fight his way through the dungeon to rescue the princess.
# The knight has an initial health point represented by a positive integer. If at any point his health point drops
# python_1_to_1000/172_Factorial_Trailing_Zeros.py - m # to 0 or below, he dies immediately.
# Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms;
_author_ = 'jake' # other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
_project_ = 'leetcode' # In order to reach the princess as quickly as possible, the knight moves only rightward or downward in each step.
# Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
# https://leetcode.com/problems/factorial-trailing-zeroes/
# Given an integer n, return the number of trailing zeroes in n!. # Dynamic programming. Min health to reach end from any room is health lost/gained in that room + min required
# after moving down or right, floored at 1 since health cannot be zero.
# Every trailing zero is created by a factor of 5 (since there are many more factors of 2 that together make # Time - O(n * m)
# trailing zeroes). Count the numbers in 1..n that are divisible by 5, then those divisible by 25 which have a # Space - O(n + m)
# second factor of 5, then 125 etc ...
# Time - O(log n) class Solution(object):
# Space - O(1) def calculateMinimumHP(self, dungeon):
"""
class Solution(object): :type dungeon: List[List[int]]
def trailingZeroes(self, n): :rtype: int
""" """
:type n: int rows, cols = len(dungeon), len(dungeon[0])
:rtype: int
""" for r in range(rows - 1): # add new final column and row of infinity
zeroes = 0 dungeon[r].append(float('inf'))
power_of_5 = 5 dungeon.append([float('inf') for _ in range(cols + 1)])

while power_of_5 <= n: dungeon[rows - 1].append(1) # final room requires min health of 1
zeroes += n // power_of_5
power_of_5 *= 5 for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
return zeroes dungeon[r][c] = max(1, -dungeon[r][c] + min(dungeon[r+1][c], dungeon[r][c+1]))

return dungeon[0][0]

# python_1_to_1000/173_Binary_Search_Tree_Iterator.py - m

_author_ = 'jake' # python_1_to_1000/179_Largest_Number.py - m

_project_ = 'leetcode'
_author_ = 'jake'
# https://leetcode.com/problems/binary-search-tree-iterator/ _project_ = 'leetcode'
# Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
# Calling next() will return the next smallest number in the BST. # https://leetcode.com/problems/largest-number/
# next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. # Given a list of non negative integers, arrange them such that they form the largest number.
# For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
# Iterative inorder traversal. Go left to smallest node, pushing all nodes onto stack. After popping a node, # Note: The result may be very large, so you need to return a string instead of an integer.
# add to stack all nodes on path to its inorder successor by moving to right child then as far left as possible.
# Time - O(n) worst case and O(1) average for __init__() and next(). # Comparator sorts by checking which order of concatenation gives the larger result.
# Space - O(n) worst case, log n if balanced. # Time - O(n log n)
# Space - O(n)
# Definition for a binary tree node
class TreeNode(object): import functools
def __init__(self, x):
self.val = x class Solution:
self.left = None # @param {integer[]} nums
self.right = None # @return {string}
def largestNumber(self, nums):
class BSTIterator(object):
def __init__(self, root): def comparator(x, y): # inputs are string representations of non-negative ints
""" if x+y > y+x: # no need to convert to int because x+y and y+x are same length
:type root: TreeNode return -1 # so lexicographic string sort behaves like numeric sort
""" else:
self.stack = [] return 1
while root:
self.stack.append(root) nums = list(map(str, nums)) # convert to strings
root = root.left nums.sort(key=functools.cmp_to_key(comparator))

def hasNext(self): return str(int("".join(nums))) # remove excess leading zeroes

"""
:rtype: bool
"""
return True if self.stack else False # python_1_to_1000/186_Reverse_Words_in_a_String_II.py - m

# Time - O(n * k)
_author_ = 'jake' # Space - O(n * k)
_project_ = 'leetcode'
class Solution(object):
# https://leetcode.com/problems/reverse-words-in-a-string-ii/ def maxProfit(self, k, prices):
# Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. """
# The input string does not contain leading or trailing spaces and the words are always separated by a single space. :type k: int
:type prices: List[int]
# Revese entire string then reverse each word individually. :rtype: int
# Alternatively use built-in reverse() and reversed() functions. """
# Time - O(n) if k >= len(prices) // 2: # can transact as often as required to get max profit
# Space - O(1) return sum([max(0, prices[i] - prices[i-1]) for i in range(1, len(prices))])

class Solution: # buys[i] is the max profit after i-1 buy/sell transactions and another buy
# @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o'] # sells[i] is the max profit after i buy/sell transactions
# @return nothing buys, sells = [float('-inf') for _ in range(k + 1)], [0 for _ in range(k + 1)]
def reverseWords(self, s):
for price in prices:
self.reverse(s, 0, len(s)-1) for i in range(1, len(buys)):

s.append(' ') # temporary space to signify end of last word buys[i] = max(buys[i], sells[i-1] - price) # add -price to previous best after i-1 transactions
start = 0 if buys[i] == buys[i-1]: # additional transaction has not increased profit
for i in range(len(s)): break
if s[i] == ' ': sells[i] = max(sells[i], buys[i] + price) # add +price to max after i-1 transactions and another buy
self.reverse(s, start, i-1) # reverse word from start to i-1
start = i+1 # start of next word return max(sells)
s.pop()

def reverse(self, s, left, right):

while left < right: # python_1_to_1000/189_Rotate_Array.py - m
s[left], s[right] = s[right], s[left]
left += 1 _author_ = 'jake'
right -= 1 _project_ = 'leetcode'

# https://leetcode.com/problems/rotate-array/
class Solution2: # Rotate an array of n elements to the right by k steps.
def reverseWords(self, s):
s.reverse() # Reverse entire array, then reverse left k elements and right n-k elements.
s.append(' ') # Alternatively, split after n-k elements and swap slices.
start = 0 # Time - O(n)
for i in range(len(s)): # Space - O(1)
if s[i] == ' ':
s[start:i] = reversed(s[start:i]) class Solution(object):
start = i+1 def rotate(self, nums, k):
s.pop() """
:type nums: List[int]
:type k: int
# python_1_to_1000/187_Repeated_DNA_Sequences.py - m :rtype: void Do not return anything, modify nums in-place instead.
"""
_author_ = 'jake' k %= len(nums)
_project_ = 'leetcode' nums.reverse()
nums[:k] = reversed(nums[:k])
# https://leetcode.com/problems/repeated-dna-sequences/ nums[k:] = reversed(nums[k:])
# All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG".
# When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. class Solution2(object):
# Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. def rotate(self, nums, k):
n = len(nums)
# Store all substrings of length 10 in a set, if substring is duplicated add to result set. k %= n
# Time - O(n) nums[:] = nums[n-k:] + nums[:n-k]
# Space - O(n)

class Solution(object): # python_1_to_1000/190_Reverse_Bits.py

def findRepeatedDnaSequences(self, s):
""" _author_ = 'jake'
:type s: str _project_ = 'leetcode'
:rtype: List[str]
""" # https://leetcode.com/problems/reverse-bits/
substrings, repeated = set(), set() # Reverse bits of a given 32 bits unsigned integer.
TARGET = 10 # For example, given input 43261596 (represented in binary as 00000010100101000001111010011100),
# return 964176192 (represented in binary as 00111001011110000010100101000000).
for i in range(len(s)-TARGET+1):
# Convert to string of binary. Reverse and convert base 2 string back to int.
substring = s[i:i+TARGET] # Alternatively, if bit i is set than add 2**(31-i) to the result.
if substring in substrings: # Time - O(log n)
repeated.add(substring) # Space - O(log n)
else:
substrings.add(substring) class Solution:
# @param n, an integer
return list(repeated) # convert set to list # @return an integer
def reverseBits(self, n):
binary = bin(n)
# python_1_to_1000/188_Best_Time_to_Buy_and_Sell_Stock_IV.py - h binary = binary[2:] # remove header '0b'
reversed_binary = binary[::-1] + ''.join(['0' for _ in range(32 - len(binary))])
_author_ = 'jake' return int(reversed_binary, 2) # convert from base 2
_project_ = 'leetcode'

# https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/ class Solution2:

# Say you have an array for which the ith element is the price of a given stock on day i. # @param n, an integer
# Design an algorithm to find the maximum profit. You may complete at most k transactions. # @return an integer
# You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). def reverseBits(self, n):

# Dynamic programming. Max profit after i buys = cost + max after i-1 transactions. reversed, bit = 0, 31
# Max profit after i sells = sale price + max after i-1 transactions and additional buy.
 while n != 0: right_view = []
if n % 2 == 1: # last bit is set layer = [root]
reversed += 2**bit
bit -= 1 while layer:
n //= 2
right_view.append(layer[-1].val)
return reversed next_layer = []

for node in layer:

# python_1_to_1000/191_Number_of_1_Bits.py if node.left:
next_layer.append(node.left)
_author_ = 'jake' if node.right:
_project_ = 'leetcode' next_layer.append(node.right)

# https://leetcode.com/problems/number-of-1-bits/ layer = next_layer

# Write a function that takes an unsigned integer and returns the number of ’1' bits (known as the Hamming weight).
return right_view
# Convert to string and count '1' chars.
# Time - O(log n)
# Space - O(log n) class Solution2(object):
def rightSideView(self, root):
class Solution(object): right_side = []
def hammingWeight(self, n): self.recursive(root, 0, right_side)
""" return right_side
:type n: int
:rtype: int def recursive(self, node, depth, right_side):
"""
return sum(c == "1" for c in bin(n)[2:]) if not node:
return

# python_1_to_1000/198_House_Robber.py - m if depth >= len(right_side): # update right_side with this node

right_side.append(node.val)
_author_ = 'jake' else:
_project_ = 'leetcode' right_side[depth] = node.val

# https://leetcode.com/problems/house-robber/ self.recursive(node.left, depth+1, right_side) # recurse left before right

# You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, self.recursive(node.right, depth+1, right_side)
# the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and
# it will automatically contact the police if two adjacent houses were broken into on the same night.
# Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount # python_1_to_1000/200_Number_of_Islands.py - m
# of money you can rob tonight without alerting the police.
_author_ = 'jake'
# Either do not rob current house and take max from all previous houses, or rob current house, skip previous and _project_ = 'leetcode'
# take max of all others.
# Time - O(n) # https://leetcode.com/problems/number-of-islands/
# Space - O(1) # Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
# An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
class Solution(object): # You may assume all four edges of the grid are all surrounded by water.
def rob(self, nums):
""" # If cell is '1' then set to '0' and recurse for all adjacent cells.
:type nums: List[int] # Time - O(m * n)
:rtype: int # Space - O(1)
"""
if not nums: class Solution(object):
return 0 def numIslands(self, grid):
loot, prev = nums[0], 0 # max from robbing this and previous adjacent houses """
:type grid: List[List[str]]
for num in nums[1:]: :rtype: int
loot, prev = max(num + prev, loot), loot """
if not grid:
return loot return 0

rows, cols = len(grid), len(grid[0])

# python_1_to_1000/199_Binary_Tree_Right_Side_View.py - m islands = 0
for r in range(rows):
_author_ = 'jake' for c in range(cols):
_project_ = 'leetcode' if grid[r][c] == '1':
islands += 1
# https://leetcode.com/problems/binary-tree-right-side-view/ self.set_island(r, c, grid)
# Given a binary tree, imagine yourself standing on the right side of it,
# return the values of the nodes you can see ordered from top to bottom. return islands

# BFS layer by layer. Add to result last value found in a layer. def set_island(self, row, col, grid):
# Alternatively, recursively pre-order traverse tracking depth and updating result for each node. if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
# Time - O(n) return
# Space - O(n) if grid[row][col] != '1':
return
# Definition for a binary tree node. grid[row][col] = '0'
class TreeNode(object): self.set_island(row+1, col, grid)
def __init__(self, x): self.set_island(row-1, col, grid)
self.val = x self.set_island(row, col+1, grid)
self.left = None self.set_island(row, col-1, grid)
self.right = None

class Solution(object):
def rightSideView(self, root): # python_1_to_1000/201_Bitiwse_AND_of_Numbers_Range.py - m
"""
:type root: TreeNode _author_ = 'jake'
:rtype: List[int] _project_ = 'leetcode'
"""
if not root: # https://leetcode.com/problems/bitwise-and-of-numbers-range/
return [] # Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

# Starting from the most significant bit that is set in n, compare each bit in n to the equivalent bit in m. # Definition for singly-linked list.
# If both bits are the same, set the same bit in the result to its value in m and n. class ListNode(object):
# Stop when a bit is set differently in m and n. def __init__(self, x):
# When any bit is different, all less significant bits must take on both values of 0 and 1 in the range. self.val = x
# Time - O(log n) self.next = None
# Space - O(1)
class Solution(object):
from math import log def removeElements(self, head, val):
"""
class Solution(object): :type head: ListNode
def rangeBitwiseAnd(self, m, n): :type val: int
""" :rtype: ListNode
:type m: int """
:type n: int dummy = prev = ListNode(None) # dummy in case head is deleted
:rtype: int dummy.next = head
"""
if m == 0: while head:
return 0
result = 0 if head.val == val:
prev.next, head.next, head = head.next, None, head.next
bit = int(log(n, 2)) # highest bit that is set in n else:
prev, head = head, head.next
while bit >= 0 and ((m & (1 << bit)) == (n & (1 << bit))):
if (m & (1 << bit)): # if this bit is set return dummy.next
result += 2**bit
bit -= 1
# python_1_to_1000/204_Count_Primes.py - m
return result
_author_ = 'jake'
_project_ = 'leetcode'
# python_1_to_1000/202_Happy_Number.py
# https://leetcode.com/problems/count-primes/
_author_ = 'jake' # Count the number of prime numbers less than a non-negative number, n.
_project_ = 'leetcode'
# Sieve numbers. Assume all are prime and eliminate those with factors.
# https://leetcode.com/problems/happy-number/ # Time - O(n***3/2)
# Write an algorithm to determine if a number is "happy". # Space - O(n)
# A happy number is a number defined by the following process: Starting with any positive integer,
# replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 class Solution(object):
# (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this def countPrimes(self, n):
# process ends in 1 are happy numbers. """
:type n: int
# Fast and slow pointers increment to the next sum of square digits. If in a cycle pointers will converge at :rtype: int
# a value other than 1, if no cycle pointers will both be 1. """
# Alternatively, if n == 4 then we are in a cycle. See https://en.wikipedia.org/wiki/Happy_number sieve = [False, False] + [True for _ in range(n-2)] # 0 and 1 are not prime
# Time - O(log n)
# Space - O(1) for i in range(2, int(n**0.5) + 1): # end at sqrt since any j not prime must have a factor <= sqrt(j)

class Solution(object): if sieve[i]: # i is prime

def isHappy(self, n):
""" sieve[i*i:n:i] = [False] * len(sieve[i*i:n:i]) # list comprehension faster than loop
:type n: int # start at i*i since i*(i-1) already eliminated
:rtype: bool return sum(sieve)
"""
if n == 1:
return True, 1 # python_1_to_1000/205_Isomorphic_Strings.py
slow = sum([int(c)*int(c) for c in str(n)])
fast = sum([int(c)*int(c) for c in str(slow)]) _author_ = 'jake'
_project_ = 'leetcode'
while fast != slow:
slow = sum([int(c)*int(c) for c in str(slow)]) # https://leetcode.com/problems/isomorphic-strings/
fast = sum([int(c)*int(c) for c in str(fast)]) # Given two strings s and t, determine if they are isomorphic.
fast = sum([int(c)*int(c) for c in str(fast)]) # Two strings are isomorphic if the characters in s can be replaced to get t.
# All occurrences of a character must be replaced with another character while preserving the order of characters.
return slow == 1 # No two characters may map to the same character but a character may map to itself.

class Solution2(object): # Store a mapping from chars of s to chars of t. If a char in s is already in mapping then check that the char in t
def isHappy(self, n): # is same as previously observed. Check also that a new mapping of char in s is not to a char in t already mapped.
""" # Time - O(n)
:type n: int # Space - O(n)
:rtype: bool
""" class Solution(object):
while True: def isIsomorphic(self, s, t):
if n == 1: """
return True :type s: str
if n == 4: :type t: str
return False :rtype: bool
n = sum([int(c)*int(c) for c in str(n)]) """
if len(s) != len(t):
return False

# python_1_to_1000/203_Remove_Linked_List_Elements.py s_to_t = {}
t_mapped = set()
_author_ = 'jake'
_project_ = 'leetcode' for cs, ct in zip(s, t):

# https://leetcode.com/problems/remove-linked-list-elements/ if cs in s_to_t:
# Remove all elements from a linked list of integers that have value val. if s_to_t[cs] != ct:
return False
# Iterate along list, cutting out nodes with val. elif ct in t_mapped:
# Time - O(n) return False
# Space - O(1) s_to_t[cs] = ct
t_mapped.add(ct)
 return True # Node stores dictionary mapping letters to child nodes. Array would use fixed space regardless of actual nb children.
# Note that node does not explicitly store letter.
# Time - O(n) to create where n is total length of all words, O(k) to search where k is length of word.
# Space - O(n)
# python_1_to_1000/206_Reverse_Linked_List.py
class TrieNode(object):
_author_ = 'jake' def __init__(self):
_project_ = 'leetcode' """
Initialize your data structure here.
# https://leetcode.com/problems/reverse-linked-list/ """
# Reverse a singly linked list. self.children = {} # mapping from letter to child TrieNodes
self.terminal = False # flag indicates whole word
# Iterative resvers. Alternatively, use recursion.
# Time - O(n) class Trie(object):
# Space - O(1)
def __init__(self):
# Definition for singly-linked list. self.root = TrieNode()
class ListNode(object): self.root.terminal = True # empty string is a whole word
def __init__(self, x):
self.val = x def insert(self, word):
self.next = None """
Inserts a word into the trie.
class Solution(object): :type word: str
def reverseList(self, head): :rtype: void
""" """
:type head: ListNode node = self.root
:rtype: ListNode for c in word:
""" if c not in node.children: # create a node if it does not exist
reversed = None node.children[c] = TrieNode()
while head: node = node.children[c]
next = head.next node.terminal = True # set to True at end of word
head.next = reversed
reversed = head def search(self, word):
head = next """
return reversed Returns if the word is in the trie.
:type word: str
:rtype: bool
# python_1_to_1000/207_Course_Schedule.py - m """
node = self.root
_author_ = 'jake' for c in word:
_project_ = 'leetcode' if c in node.children:
node = node.children[c]
# https://leetcode.com/problems/course-schedule/ else:
# There are a total of n courses you have to take, labeled from 0 to n - 1. return False
# Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed return node.terminal # only True if terminal
as a pair: [0,1]
# Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? def startsWith(self, prefix):
"""
# Topological sort. Find nodes with no dependencies. Remove outgoing edges from each such node. Repeat until Returns if there is any word in the trie
# no node has no dependencies. that starts with the given prefix.
# Time - O(m + n), edges + nodes :type prefix: str
# Space - O(m + n) :rtype: bool
"""
from collections import defaultdict node = self.root
for c in prefix:
class Solution(object): if c in node.children:
def canFinish(self, numCourses, prerequisites):