<jupyter_start><jupyter_text>100) Same Tree--------------Given two binary trees, write a function to check if they are the same or not.Two binary trees are considered the same if they are structurally identical and the nodes have the same value.<jupyter_code>class TreeNode(object):
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution(object):
    
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        
        if (not p and q) or (p and not q):
            return False
        elif not p or not q:
            return True
        else:            
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

a = TreeNode(5)
a.left = TreeNode(4)
a.right = TreeNode(6)
a.right.right =  TreeNode(8)

b = TreeNode(5)
b.left = TreeNode(4)
b.right = TreeNode(6)
b.right.right =  TreeNode(8)

sol = Solution()
sol.isSameTree(a, b)<jupyter_output><empty_output><jupyter_text>99) Recover BST----------------Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree without changing its structure.Note:A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?<jupyter_code>class TreeNode(object):
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None
        
class Solution(object):
    
    def __init__(self):
        self.badpair1 = None
        self.badpair2 = None
        self.inorder = [None, None, None]
        self.curr = 0
    
    def swap(self, a, b):
        tmp = a.val
        a.val = b.val
        b.val = tmp
    
    def sol(self, root):
        self.infix(root)
        if not self.badpair[1]:
            #adjascent
            
        else:
            
    
    def infix(self, root):
        
        if root.left:
            self.infix(root.left)
        self.curr = (self.curr+1)%3
        self.inorder[self.curr] = root
        currval = root
        preval1 = self.inorder[(self.curr-1)%3]
        #preval2 = self.inorder[(self.curr-2)%3]
        
        if preval1 and not preval2:
            #print "" + str(preval1.val) + ", " + str(currval.val)
            if not (preval1.val <= currval.val):
                if self.badpair[0]:
                    self.badpair[1] = preval1
                    swap(self.badpair[0], self.badpair[1])
                else:
                    self.badpair[0] = preval1
            
        
        if preval1 and preval2:
            #print "" + str(preval2.val) + ", " + str(preval1.val) + ", " + str(currval.val)
            if not (preval1.val <= currval.val) #or not (preval2.val <= preval1.val):
                if self.badpair[0]:
                    self.badpair[1] = preval1
                    self.swap(self.badpair[0], self.badpair[1])
                else:
                    self.badpair[0] = preval1
                
        if root.right:
            self.infix(root.right)

b = TreeNode(4)
b.left = TreeNode(5)
b.right = TreeNode(6)


sol = Solution()
sol.infix(b)

# After Swap
print(sol.badpair[0].val)
print(sol.badpair[1].val)


#Soln.: 
# Just check the pairs of consecutive numbers inorder 
# if there are 2 inconsistencies swap the offending elements, 
# if only one inconsistency swap the elements in the pair.<jupyter_output>4
5<jupyter_text>98) Validate Binary Search Tree-----------Given a binary tree, determine if it is a valid binary search tree (BST).Assume a BST is defined as follows:The left subtree of a node contains only nodes with keys less than the node's key.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.<jupyter_code># Same as above, if there is an offending inorder element pair invalidate the BST<jupyter_output><empty_output><jupyter_text>22) Generate Parentheses---------------------Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is:<jupyter_code>class Soln(object):
    
    
    def __init__(self):
        self.pars = []

    def genparens(self, n, left, right, strn):
        
        if left==n and right==n:
            self.pars.append(strn)
        if left < n:
            self.genparens(n, left+1, right, strn+"(")
        if right<left:
            self.genparens(n, left, right+1, strn+")")

    def genParenths(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        self.genparens(n, 0, 0, "")
        return self.pars


#s = Soln()
#s.genParenths(6)<jupyter_output><empty_output><jupyter_text>23) Merge k Sorted Lists--------------------Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.<jupyter_code># Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        mini = 0
        for i in range(len(lists)):
            if lists[i].val < mini.val:
                mini = i
        head = lists[mini]
        
        lists[mini] = lists[mini].next
        head.next  = self.mergeKLists(lists)
        
        return head
        
    def printlist(self, l):
        i = l
        while i is not None:
            print i.val
            i = i.next

# 1. Naive sorting of all the numbers -- O(Nk.log(Nk))
# 2. tracking current smallest and n-way merge -- O(Nk)
# 3. Use a heap/priorityQ for selecting min. Pop the min in O(1) and insert the next element in O(logk) -- O(Nlogk)
# 4. Merge lists in pairs of two at a time -- O(Nlogk)<jupyter_output><empty_output><jupyter_text>24) Swap Nodes in pairs------Given a linked list, swap every two adjacent nodes and return its head.For example,Given 1->2->3->4, you should return the list as 2->1->4->3.Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.<jupyter_code># Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if not head:
            return head
        
        root = head.next
        rest = self.swapPairs(root.next)
        root.next = head
        head.next = rest        
        
        return root

lis = ListNode(1)
lis.next = ListNode(2)
lis.next.next = ListNode(3)
lis.next.next.next = ListNode(4)

s = Solution()
lr = s.swapPairs(lis)

print lr.val
print lr.next.val
print lr.next.next.val
print lr.next.next.next.val<jupyter_output>2
1
4
3<jupyter_text>25. Reverse Nodes in k-Group-----Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.You may not alter the values in the nodes, only nodes itself may be changed.Only constant memory is allowed.For example,Given this linked list: 1->2->3->4->5For k = 2, you should return: 2->1->4->3->5For k = 3, you should return: 3->2->1->4->5<jupyter_code># Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        checklen = 0
        c = head
        while c:
            c=c.next
            checklen+=1
        
        if checklen<k:
            return head
        
        end = head
        root = None
        for i in range(k):
            curr = head
            head = head.next
            
            curr.next = root
            root = curr
            
        end.next = self.reverseKGroup(head, k)
        
        return root
            
lis = ListNode(1)
lis.next = ListNode(2)
lis.next.next = ListNode(3)
lis.next.next.next = ListNode(4)
lis.next.next.next.next = ListNode(5)
lis.next.next.next.next.next = ListNode(6)

s = Solution()
lr = s.reverseKGroup(lis, 4)

print lr.val
print lr.next.val
print lr.next.next.val
print lr.next.next.next.val
print lr.next.next.next.next.val
print lr.next.next.next.next.next.val<jupyter_output>4
3
2
1
5
6<jupyter_text>26. 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.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.Example:Given nums = [1,1,2],Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.It doesn't matter what you leave beyond the new length.<jupyter_code>class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        count = 0
        pos = {}
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                count += 1
                pos[i] = count
        
        curcount = 0
        for i in range(len(nums)):
            if i in pos:
                curcount = pos[i]
            
            nums[i-curcount] = nums[i]
        
        return i-curcount+1

s=Solution()
num=[1, 1, 2, 2, 3, 4, 5, 6, 7, 10, 10, 11, 11, 11, 11, 11, 13, 15]
length = s.removeDuplicates(num)
print num
print length

# Ans. Solve this in one traversal, by just keeping track of curcount and not needing a pos hash 
# or keep track of the tail of list so far<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 10, 11, 13, 15, 11, 11, 11, 11, 11, 13, 15]
11<jupyter_text>27. Remove Element-----Given an array and a value, remove all instances of that value in-place and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.The order of elements can be changed. It doesn't matter what you leave beyond the new length.Example:Given nums = [3,2,2,3], val = 3,Your function should return length = 2, with the first two elements of nums being 2.<jupyter_code># same as before keep track of the tail, in the condition above check equal to given value instead.
# if the order of the elements in the array could be changed, 
# then swap with last element if its not equal to the value and update last element<jupyter_output><empty_output><jupyter_text>28. Implement strStr()-----Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.Example 1:Input: haystack = "hello", needle = "ll"Output: 2Example 2:Input: haystack = "aaaaa", needle = "bba"Output: -1<jupyter_code>class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        an = len(needle)
        bn = len(haystack)
        
        for i in range(bn):
            hay_curr = i
            needle_curr = 0
            while needle_curr < an and hay_curr < bn and haystack[hay_curr] == needle[needle_curr]:
                hay_curr += 1
                needle_curr += 1
            if an == needle_curr:
                return i+1
            
        return -1

s = Solution()
s.strStr("helooooooll0", "ll")

# Use KMP algorithm for str comparison<jupyter_output><empty_output><jupyter_text>29. Divide Two Integers------Divide two integers without using multiplication, division and mod operator.If it is overflow, return MAX_INT.<jupyter_code>class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        
        q = 0
        dividend -= divisor
        while dividend > 0:
            q += 1
            dividend -= divisor
            #print(dividend)
        
        return q 

    def divide2(self, dividend, divisor): # This is wrong algo
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sumq = 0
        def divide_help(divd, divs, curr, ts):
            if curr == divd:
                return ts
            elif curr > divd:
                return 0
            else:
                curq = divide_help(divd, divs, curr<<1, ts<<1)
                if curq == 0:
                    newq = divide_help(divd - curr, divisor, divisor, 1)
                    print(newq)
                    return ts + newq
                else:
                    return ts
                    
        ans = divide_help(dividend, divisor, divisor, 1)
        return ans
    
    def divide3(self, dividend, divisor):
        
        def d3_help(divd, divs, curr, q):
            if curr == divd:
                return q, 0
            elif curr > divd:
                return q>>1, divd-(curr>>1)
            else:
                return d3_help(divd, divs, curr<<1, q<<1)
        
        sumq=0
        while dividend >= divisor:
            q, r = d3_help(dividend, divisor, divisor, 1)
            sumq += q
            dividend = r
        return sumq
        
s = Solution()

s.divide3(11111111111111111111, 4)

# divide3 complexity is O((logn)^2)?<jupyter_output><empty_output><jupyter_text>30. Substring with Concatenation of All Words------You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.For example, given:s: "barfoothefoobarman"words: ["foo", "bar"]You should return the indices: [0,9].(order does not matter).<jupyter_code>class Solution(object):
    
    def get_trie(words):
        pass
    
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        
        trie, se = self.get_trie(words)
        root = trie
        for i in s:
            if i in root:
                if root[i].next:
                    root = root[i].next
                else:
                    se[root[i]] += 1
                    done = True
                    for key, val in se:
                        if val != 1:
                            done=False
                    if done:
                        pass
            if i in trie:
                pass
 
####
#Soln from https://simpleandstupid.com/2014/10/21/substring-with-concatenation-of-all-words-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/
#Try to think this problem straightforward:
#Say in L there are m strings with length n.
#What string is required to match in S? A length of m*n string start with each position in S.
#What is a match? In the m*n long string, every string in L appear only once.

#So the algorithm is:
#Scan every m*n long string start from each position in S, see if all the strings in L have been appeared only once using Map data structure. If so, store the starting position.

#Yes, do not consider any DP or DFS solutions, just using the hash map and loop.<jupyter_output><empty_output><jupyter_text>class Solution {    public List findSubstring(String s, String[] words) {        final Map counts = new HashMap();        for (final String word : words) {            counts.put(word, counts.getOrDefault(word, 0) + 1);        }        final List indexes = new ArrayList();        final int n = s.length(), num = words.length, len = words[0].length();        for (int i = 0; i < n - num * len + 1; i++) {            final Map seen = new HashMap();            int j = 0;            while (j < num) {                final String word = s.substring(i + j * len, i + (j + 1) * len);                if (counts.containsKey(word)) {                    seen.put(word, seen.getOrDefault(word, 0) + 1);                    if (seen.get(word) > counts.getOrDefault(word, 0)) {                        break;                    }                } else {                    break;                }                j++;            }            if (j == num) {                indexes.add(i);            }        }        return indexes;    }} 97. Interleaving String------Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.For example,Given:s1 = "aabcc",s2 = "dbbca",When s3 = "aadbbcbcac", return true.When s3 = "aadbbbaccc", return false.<jupyter_code>class Solution(object):
    
    def inters(self, s1, s2):
        s = []
        for i in range(len(s1)):
            s.append(s1[i])
            s.append(s2[i])
        return s
    
    def findnpre(self, s1, s2):
        i=0
        while s1[i] == s2[i]:
            i+=1
        return i

    def isInterleaveExact(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        strs = []
        strs.append(self.inters(s1, s2))
        strs.append(self.inters(s2, s1))
            
        npre = self.findnpre(s1, s2)
        curr = 0
        curstr = -1
        for i in range(len(s3)):
            #print curr
            #print i
            #print curstr
            #print s1[curr]
            #print s2[curr]
            #print s3[i]
            if curr < npre:
                if not s3[i] == strs[0][curr]:
                    return False
            elif curr==npre:
                if s3[i] == strs[0][curr]:
                    curstr = 0
                elif s3[i] == strs[1][curr]:
                    curstr = 1
                else:
                    return False
            else:
                if not s3[i] == strs[curstr][curr]:
                    return False
            curr+=1

        if i == len(strs[0]):
            return True
        else:
            return False
        
    def isInterleave0(self, s1, s2, s3):
        curr1=0
        curr2=0
        ns1 = len(s1)
        ns2 = len(s2)
        for i in range(len(s3)):
            #print("-----")
            #print s1[curr1]
            #print s2[curr2]
            #print s3[i]
            
            if curr1 < ns1 and s3[i] == s1[curr1]:
                curr1 += 1
            elif curr2 < ns2 and s3[i] == s2[curr2]:
                curr2 += 1
            else:
                return False

        if curr1 == ns1 and curr2 == ns2:
            return True
        else:
            return False
    
    def isInterleave(self, s1, s2, s3):
        pass
a = "aadbbcbcac"
b = "aadbbbaccc"
s = Solution()
s.isInterleave("aabcc", "dbbca", a)

# use recursion to choose between the two strings for current char match, 
# use memoization cos substring permutations are checked redundantly<jupyter_output><empty_output><jupyter_text>96. Unique Binary Search Trees--------Given n, how many structurally unique BST's (binary search trees) that store values 1...n?For example,Given n = 3, there are a total of 5 unique BST's.   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3<jupyter_code>class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if not n:
            return 1
        
        sumt=0
        for i in range(1, n+1):
            sumt += self.numTrees(i-1) * self.numTrees(n-i)
        return sumt

s = Solution()

s.numTrees(1)

# Memoize the above solution.
# Watchout for base cases and the iteration limits<jupyter_output><empty_output><jupyter_text>95. Unique Binary Search Trees II---------Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.For example,Given n = 3, your program should return all 5 unique BST's shown below.   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3<jupyter_code># Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        return self.generateTrees_help(1, n)
    
    def generateTrees_help(self, m, n):
        #print "--"
        #print m
        #print n
        if m==n:
            return [TreeNode(m)]
        elif m>n: # remember this base case
            return [None]

        trees = []
        for i in range(m, n+1):
            root = TreeNode(i)
            lefts = self.generateTrees_help(m, i-1)
            rights = self.generateTrees_help(i+1, n)
            for j in lefts: 
                root.left = j
                for k in rights:
                    root.right = k
                    trees.append(root)

        return trees

s = Solution()
x = s.generateTrees(3)
#for i in x:
#    print i.val<jupyter_output><empty_output><jupyter_text>78. Subsets----Given a set of distinct integers, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.For example,If nums = [1,2,3], a solution is:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]<jupyter_code>class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        pwset = []
        
        def helper(curr, ind):
            if ind==len(nums):
                pwset.append(curr)
            else:
                new0=curr[:]
                helper(new0, ind+1)
                new1=curr[:]
                new1.append(nums[ind])
                helper(new1, ind+1)
        
        helper([], 0)
        return pwset

s=Solution()
s.subsets([1, 2, 3])<jupyter_output><empty_output><jupyter_text>90. Subsets II-----Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.For example,If nums = [1,2,2], a solution is:[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]<jupyter_code>class Solution(object):
    def __init__(self):
        self.pw = []
    
    def subsetsNoDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        return self.ss_help(nums, 0, [])
        
    def ss_help(self, nums, ind, lis):
        #print(lis)
        #print ind 
        #print nums
        #print(self.pw)
        lns = len(nums)
        if ind == lns:
            #check if alread there using a hash of the subset being inserted
            self.pw.append(lis)
        else:
            new0 = lis[:]
            x=0
            while ind+x+1 < lns and nums[ind+x] == nums[ind+x+1]: 
                x+=1
            #print ind+x
            self.ss_help(nums, ind+x+1, new0)
            
            #if ind+1 == lns or nums[ind] != nums[ind+1]:
            #    self.ss_help(nums, ind+1, new0)
            #else:
            #    x=0
            
            new1 = lis[:]
            #x=0
            #while ind+x+1 < lns and nums[ind+x] == nums[ind+x+1]:
            #    x+=1
            new1.append(nums[ind])
            #print ind+1
            self.ss_help(nums, ind+1, new1)
            
            
            
s = Solution()
s.subsetsNoDup([1, 2, 2, 2])
s.pw


# For repeating elements (say 3), include them in this form
# 0 0 0
# 1 0 0
# 1 1 0
# 1 1 1
# Don't include 1 0 1, 0 0 1, etc which are equivalent to 1 1 0.
# In calc. total number of elements in a power set: 
# factor contributed by a set of repeating numbers is (n+1) instead of 2^n

# An alternate way to do this is to append and not append current element to existing subsets iteratively
# in case of repetition append only to the subsets where the equal element was already appended
# Ex: [1, 2, 2, 2]:
# Power set lists revised in the following order:
# {[]}, {[], [1]}, {[], [1], "[2], [1, 2]"}, 
# {[], [1], [2], [1, 2], "[2, 2], [1, 2, 2]"}, {[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [2, 2, 2], [1, 2, 2, 2]}
# repeating updates on "*" in previous list

#list append and len functions are O(1), so the above complexity is O(2^n)


# Similar to finding permutations:
# Key idea: Sort the nums, when a number has the same value with its previous, 
#           we can use curr num only if previous num is used<jupyter_output><empty_output><jupyter_text>91. Decode Ways-----------A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1'B' -> 2...'Z' -> 26Given an encoded message containing digits, determine the total number of ways to decode it.For example,Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).The number of ways decoding "12" is 2.<jupyter_code>class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        return self.numDecodings_help(s, 0)
        
    def numDecodings_help(self, s, ind):
        
        if ind >= len(s)-1:
            #print ind
            #print len(s)-1
            #print "base"
            return 1
        
        # beware of the types, if you dont convert str to int...lot of problems without compilation error
        if ind < len(s)-1 and ((int(s[ind]) == 2 and int(s[ind+1]) < 7) or int(s[ind]) < 2):
            a =  self.numDecodings_help(s, ind+1) 
            b =  self.numDecodings_help(s, ind+2)
            #print a
            #print b
            #print ("--")
            return a+b
        else:
            #print ind
            #print len(s)-1
            #print s[ind]
            #print s[ind+1]
            #print "other"
            #print ind < len(s)-1
            #print (s[ind] == 2 and s[ind+1] < 7) 
            #print s[ind] < 2
            return self.numDecodings_help(s, ind+1)
        
s = Solution()
s.numDecodings("12")


#solution: Memoize the above solution

# Nice short solution:
#def numDecodings(self, s):
#    v, w, p = 0, int(s>''), ''
#    for d in s:
#        v, w, p = w, (d>'0')*w + (9<int(p+d)<27)*v, d
#    return w<jupyter_output><empty_output><jupyter_text>92. Reverse Linked List II-----Reverse a linked list from position m to n. Do it in-place and in one-pass.For example:Given 1->2->3->4->5->NULL, m = 2 and n = 4,return 1->4->3->2->5->NULL.Note:Given m, n satisfy the following condition:1 ≤ m ≤ n ≤ length of list.<jupyter_code># Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        i=1
        curr = head
        while i < m-1:
            curr = curr.next
            i += 1
        
        revroot = curr
        
        curr = curr.next
        prev = None
        while curr:
            ele = curr
            curr = curr.next
            ele.next = prev
            prev = ele
        
        revroot.next = ele
        
        return head
    
s = Solution()
a = ListNode(1)
a.next = ListNode(2)
a.next.next = ListNode(3)
a.next.next.next = ListNode(4)
a.next.next.next.next = ListNode(5)

s.reverseBetween(a, 3, 4)

print a.val
print a.next.val
print a.next.next.val
print a.next.next.next.val
print a.next.next.next.next.val<jupyter_output>1
2
5
4
3<jupyter_text>93. Restore IP Addresses-----Given a string containing only digits, restore it by returning all possible valid IP address combinations.For example:Given "25525511135",return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)<jupyter_code>class Solution(object):
    
    def __init__(self):
        self.ips = []
    
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ln=len(s)
        def res_help(curr, ind, rem):
            #print("---")
            #print curr
            if not rem and ind==ln:
                self.ips.append(curr)
                return 
            
            if rem and ln-ind-3 >= rem-1 and ln-ind-3 <= 3*(rem-1):
                a = int(s[ind:ind+3])
                #print a
                if a<256:
                    if rem==4:
                        res_help(str(a), ind+3, rem-1)
                    else:
                        res_help(curr + "." + str(a), ind+3, rem-1)

            if rem and ln-ind-2 >= rem-1 and ln-ind-2 <= 3*(rem-1):
                b = int(s[ind:ind+2])       
                #print b
                if rem==4:
                    res_help(str(b), ind+2, rem-1)
                else:
                    res_help(curr + "." + str(b), ind+2, rem-1)

            if rem and ln-ind-1 >= rem-1 and ln-ind-1 <= 3*(rem-1):
                c = int(s[ind:ind+1]) 
                #print c
                if rem==4:
                    res_help(str(c), ind+1, rem-1)
                else:
                    res_help(curr + "." + str(c), ind+1, rem-1)
        
        res_help("", 0, 4)
        return self.ips

s = Solution()
s.restoreIpAddresses("25525511135")<jupyter_output><empty_output><jupyter_text>94. Binary Tree Inorder Traversal-----Given a binary tree, return the inorder traversal of its nodes' values.For example:Given binary tree [1,null,2,3],   1    \     2    /   3return [1,3,2].Note: Recursive solution is trivial, could you do it iteratively?<jupyter_code># Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    
    def __init__(self):
        self.vlist = []
    
    def inorderTraversalRec(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        if root.left:
            self.inorderTraversalRec(root.left)
        self.vlist.append(root.val)
        if root.right:    
            self.inorderTraversalRec(root.right)
        
    def inorderTraversalIter(self, root):
        stack = []
        
        curr = root
        
        #while True:
        #    if not curr:
        #        curr = stack.pop()
        #        self.vlist.append(curr.val)
        #        curr = curr.right
        #    
        #    if curr.right:
        #        stack.append(curr.right)
        #    stack.append(curr)
        #    curr=curr.left
        #    
        #    if curr.left:
        #        
        #    else:
        #        
        #        curr = curr.right
        #
        
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
                
            curr = stack.pop()
            self.vlist.append(curr.val)
            curr = curr.right

    def MorrisInorderTraversal(self, root):
        
        curr = root
        while curr:
            if not curr.left:
                self.vlist.append(curr.val)
                curr=curr.right
            else:
                #find predecessor
                pred = curr.left
                while pred.right!=curr and pred.right:
                    pred = pred.right
                
                if not pred.right:
                    pred.right = curr
                    curr = curr.left
                else:
                    pred.right = None #not really necessary
                    self.vlist.append(curr.val)
                    curr=curr.right
            
        
    
s=Solution()
a = TreeNode(1)
a.right = TreeNode(2)
a.right.left = TreeNode(3)
s.MorrisInorderTraversal(a)
s.vlist


# Use Morris Traversal for O(1) space complexity if not collecting in vlist but just processing (no stack no recursion)

# For preorder and postorder<jupyter_output><empty_output><jupyter_text>144. Binary Tree Preorder Traversal-------Given a binary tree, return the preorder traversal of its nodes' values.For example:Given binary tree [1,null,2,3],   1    \     2    /   3return [1,2,3].Note: Recursive solution is trivial, could you do it iteratively?<jupyter_code># Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    
    def __init__(self):
        self.vlist = []
    
    def preorderTraversalRec(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.vlist.append(root.val)
        if root.left:
            self.preorderTraversalRec(root.left)
        if root.right:
            self.preorderTraversalRec(root.right)
            
    def preorderTraversalIter(self, root):
        
        stack = []
        curr = root
        
        while curr or stack:
            #print("--")
            while curr:
                #print("++")
                self.vlist.append(curr.val)
                if root.right:
                    stack.append(curr.right)
                curr=curr.left
            curr = stack.pop()

    def MorrisPreorderTraversal(self, root):
        
        curr = root
        while curr:
            if not curr.left:
                self.vlist.append(curr.val)
                curr=curr.right
            else:
                #find predecessor
                pred = curr.left
                while pred.right!=curr and pred.right:
                    pred = pred.right
                
                if not pred.right:
                    pred.right = curr
                    self.vlist.append(curr.val)
                    curr = curr.left
                else:
                    pred.right = None #not really necessary
                    curr=curr.right
        
s=Solution()
a = TreeNode(1)
a.right = TreeNode(2)
a.left = TreeNode(3)
#s.preorderTraversalIter(a)
#s.vlist
s.MorrisPreorderTraversal(a)
s.vlist


# Simpler Solution
#def preorderTraversal(self, root):
#    ret = []
#    stack = [root]
#    while stack:
#        node = stack.pop()
#        if node:
#            ret.append(node.val)
#            stack.append(node.right)
#            stack.append(node.left)
#    return ret

# Contrary to inorder, we visit curr when we find the predecessor itself 
# as opposed to after "visit"ing (revisit) the predecessor<jupyter_output><empty_output><jupyter_text>145. Binary Tree Postorder Traversal-----Given a binary tree, return the postorder traversal of its nodes' values.For example:Given binary tree {1,,2,3},   1    \     2    /   3return [3,2,1].Note: Recursive solution is trivial, could you do it iteratively?<jupyter_code># Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    
    def __init__(self):
        self.vlist = []

    def postorderTraversalRec(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root.left:
            self.preorderTraversalRec(root.left)
        if root.right:
            self.preorderTraversalRec(root.right)
        self.vlist.append(root.val)

    def postorderTraversalIter(self, root):
        
        stack = [root]
        curr =  root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            
            curr = stack.pop()
            
            curr = curr.right
            if 
            self.vlist.append(curr.val)
        
        
s=Solution()
a = TreeNode(1)
a.right = TreeNode(2)
a.left = TreeNode(3)
s.preorderTraversalIter(a)
s.vlist<jupyter_output><empty_output><jupyter_text>My solution for any kind of Iterative Traversal - inorder, preorder, postorder-------<jupyter_code>class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class job(object): # Would've been nice if I could have two variants of job and pattern matched on it during exec :P
    def __init__(self, node, exp):
        self.ite = node
        self.explore = exp

class Solution(object):
    
    def __init__(self):
        self.ttype = {"in": lambda left, curr, right: (job(left, True), job(curr, False), job(right, True)), 
                 "pre": lambda left, curr, right: (job(curr, False), job(left, True), job(right, True)), 
                 "post": lambda left, curr, right: (job(left, True), job(right, True), job(curr, False))}
        self.vlist = []
    
    def traversals_iter(self, root, kind):
        stack = [job(root, True)]
        
        while stack:
            curr = stack.pop()
            if curr.explore:
                if curr.ite:
                    l, c, r = self.ttype[kind](curr.ite.left, curr.ite, curr.ite.right)
                    stack.extend([r, c, l])
            else:
                self.vlist.append(curr.ite.val)
                
    def traversals_rec(self, root, kind):
        

s=Solution()
a = TreeNode(1)
a.right = TreeNode(2)
a.left = TreeNode(3)
s.traversals_iter(a, "in")
s.vlist<jupyter_output><empty_output><jupyter_text>Here I summarize the iterative implementation for preorder, inorder, and postorder traverse.Pre Order Traversepublic List preorderTraversal(TreeNode root) {    List result = new ArrayList();    Deque stack = new ArrayDeque();    TreeNode p = root;    while(!stack.isEmpty() || p != null) {        if(p != null) {            stack.push(p);            result.add(p.val);  // Add before going to children            p = p.left;        } else {            TreeNode node = stack.pop();            p = node.right;           }    }    return result;}In Order Traversepublic List inorderTraversal(TreeNode root) {    List result = new ArrayList();    Deque stack = new ArrayDeque();    TreeNode p = root;    while(!stack.isEmpty() || p != null) {        if(p != null) {            stack.push(p);            p = p.left;        } else {            TreeNode node = stack.pop();            result.add(node.val);  // Add after all left children            p = node.right;           }    }    return result;}Post Order Traversepublic List postorderTraversal(TreeNode root) {    LinkedList result = new LinkedList();    Deque stack = new ArrayDeque();    TreeNode p = root;    while(!stack.isEmpty() || p != null) {        if(p != null) {            stack.push(p);            result.addFirst(p.val);  // Reverse the process of preorder            p = p.right;             // Reverse the process of preorder        } else {            TreeNode node = stack.pop();            p = node.left;           // Reverse the process of preorder        }    }    return result;} 31. Next Permutation------Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).The replacement must be in-place, do not allocate extra memory.Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1<jupyter_code>class Solution(object):
    def nextPermutation0(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1, 0, -1):
            if nums[i] > nums[i-1]:
                tmp = nums[i]
                nums[i] = nums[i-1]
                nums[i-1]=tmp
                return nums
        nums.sort()
        return nums
    
    def nextPermutation(self, nums):
        for i in range(len(nums)-1, -1, -1):
            if not i:
                break
            elif nums[i] > nums[i-1]:
                break
            
        if i>=1:
            curr = i-1
            ele = i
            
            for i in range(i, len(nums)):
                if nums[i]>nums[curr] and nums[i]<nums[ele]:
                    ele=i
                    
            tmp = nums[curr]
            nums[curr] = nums[ele]
            nums[ele]=tmp
            nums[curr+1:] = sorted(nums[curr+1:])
            return nums
        else:
            nums.reverse()
            return nums

s=Solution()
a=[4,1,4,2,0]
b=[1, 3, 2]
s.nextPermutation(a)<jupyter_output><empty_output><jupyter_text>32. Longest Valid Parentheses------Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.For "(()", the longest valid parentheses substring is "()", which has length = 2.Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.<jupyter_code>class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        return self.helper(s, 0, len(s)-1)
    
    
    def valid(self, s, i, j):
        counter = 0
        for k in s[i:j+1]:
            if k == "(":
                counter+=1
            else:
                counter-=1
                if counter <0:
                    return False
        if counter:
            return False
        else:
            return True
        
        
    def helper(self, s, i, j):
        
        if i>=j:
            return 0
        
        if self.valid(s, i, j):
            return j-(i-1)
        else:
            return max(self.helper(s, i+1, j), self.helper(s, i, j-1))

s=Solution()
s.longestValidParentheses(")()())")

# For the DP solution:
# (i,j) value depends on (i+1, j) and (i, j-1)....start from diagonal. But this will still be o(n^3)

# Better Solutions:
# DP: O(n) space and time
# Stack based: O(n) space and time <<- intuitive
# Traverse left->right and right->left: O(1) space and O(n) time <<- intuitive 
#          string and reverse string to identify points that invalidate parts to be combined into valid whole
#          ) before a ( invalidates string, similarly ( in the string before ) is identified in the reverse string<jupyter_output><empty_output><jupyter_text>33. Search in Rotated Sorted Array----Suppose an array sorted in ascending order 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).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.<jupyter_code>class Solution(object):
    
    def findstart(self, nums):
        val = nums[0]
        low = 0 
        high = len(nums)-1
        if nums[0] < nums[-1]: return 0 # UPDATE 1: for test case where theres no rotation
        while low<high:
            mid = (high+low)/2
            if nums[mid] > nums[mid+1]:
                return mid+1
            if nums[mid-1] > nums[mid]:
                return mid
            if nums[mid] >= val:
                low = mid+1
            else:
                high = mid-1
        return "error"
    
    def search(self, nums, val):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        start = self.findstart(nums)
        a = self.binsearch(nums, val, start, len(nums)-1)
        b = a if a>-1 else self.binsearch(nums, val, 0, start-1)
        return b
        
    def binsearch(self, nums, val, i, j):
        low = i 
        high = j
        while low <= high:
            mid = (high+low)/2
            if nums[mid] == val:
                return mid
            if nums[mid] > val:
                high = mid-1
            else:
                low = mid+1
        return -1
        
    
s=Solution()
s.search([4, 5, 6, 0, 1, 2], 6)

# We can do this with just one binary search traversal
# There are two sublists which are sorted, keep track of which part mid is in 
# and also of which part w.r.t mid the target is in (reject the rest of the space)<jupyter_output><empty_output><jupyter_text>34. Search for a Range-------Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.Your algorithm's runtime complexity must be in the order of O(log n).If the target is not found in the array, return [-1, -1].For example,Given [5, 7, 7, 8, 8, 10] and target value 8,return [3, 4].<jupyter_code>class Solution(object):
    def searchRange(self, nums, val):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        def findpoint(f, g):
            low = 0 
            high = len(nums)
            while low <= high:
                mid = (high+low)/2
                cond = f(mid)
                if nums[mid] == val and cond:
                    return mid
                elif nums[mid] == val and not cond:
                    low, high = g(low, mid, high)
                elif nums[mid] > val:
                    low, high = low, mid-1
                elif nums[mid] < val:
                    low, high = mid+1, high
            return -1
        
        def lcheck(x): return (x-1<0 or nums[x-1] < val)
        def lupdate(low, mid, high): return low, mid-1
        def rcheck(x): return (x+1>=len(nums) or nums[x+1] > val)
        def rupdate(low, mid, high): return mid+1, high
        
        inter = [None, None]
        inter[0] = findpoint(lcheck, lupdate)
        inter[1] = findpoint(rcheck, rupdate)
        return inter

s=Solution()
s.searchRange([4, 5, 5, 5, 6, 6, 6, 8, 9, 10], 5)<jupyter_output><empty_output><jupyter_text>35. Search Insert Position---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.You may assume no duplicates in the array.Example 1:Input: [1,3,5,6], 5Output: 2Example 2:Input: [1,3,5,6], 2Output: 1Example 3:Input: [1,3,5,6], 7Output: 4Example 1:Input: [1,3,5,6], 0Output: 0<jupyter_code>class Solution(object):
    def searchInsert(self, nums, val):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (high+low)/2
            if nums[mid] == val or ((mid-1 < 0 or nums[mid-1] < val) and nums[mid] > val):
                return mid
            elif nums[mid] > val:
                high = mid-1
            else:
                low = mid+1
        return low
    
s=Solution()  
s.searchInsert([1, 3, 5, 6], -5)<jupyter_output><empty_output><jupyter_text>36. Valid Sudoku----Determine if a Sudoku is validNote:A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.<jupyter_code>from collections import Counter
class Solution(object):
    def isValidSudoku(self, bd):
        """
        :type board: List[List[int]]
        :rtype: bool
        """
        def checkline(start, end, lineind, row):
            
            line = bd[lineind][start:end] if row else \
                        [ bd[i][lineind] for i in range(len(bd)) if i>=start and i<end ]  #bd[:, start:end]
            c = Counter(line)
            #print c
            for ele in c:
                if ele and c[ele]>1:
                    return False
            return True
        
        def checkbox(rind, cind):
            for i in range(3):
                if not checkline(cind, cind+3, rind+i, True):
                    return False
            return True

        lnbd = len(bd)
        for x in [True, False]:
            for ind in range(lnbd):
                if not checkline(0, lnbd, ind,  x):
                    return False
        
        for r in range(0, lnbd, 3):
            for c in range(0, lnbd, 3):
                if not checkbox(r, c):
                    return False
        
        return True
                
brd  = [
            [5, 3, None, None, 7, None, None, None, None],
            [6, None, None, 1, 9, 5, None, None, None, None],
            [None, 9, 8, None, None, None, None, 6, None],
            [8, None, None, None, 6, None, None, None, 3],
            [4, None, None, 8, None, 3, None, None, 1],
            [7, None, None, None, 2, None, None, None, 6],
            [None, 6, None, None, None, None, 2, 8, None],
            [None, None, None, 4, 1, 9, None, None, 5],
            [None ,None, None, None, 8, None, None, 7, 9]
        ]

s = Solution()
s.isValidSudoku(brd)<jupyter_output><empty_output><jupyter_text>37. Sudoku Solver---Write a program to solve a Sudoku puzzle by filling the empty cells.Empty cells are indicated by the character '.'.You may assume that there will be only one unique solution.<jupyter_code>import pprint
class Solution(object):
    def getfirst(self, bd):
        sz = len(bd)
        for i in range(sz):
            for j in range(sz):
                if not bd[i][j]:
                    return [i, j]

    def getbox(self, row, col, bd):
        br = (row//3)*3
        bc = (col//3)*3
        return [ bd[i][j] for i in range(br, br+3) for j in range(bc, bc+3) ]
    
    def solveSudoku(self, bd):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        sz = len(bd)
        nums = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
        
        #pp = pprint.PrettyPrinter(indent=4)
        #pp.pprint(bd)
        stack = []
        last = []
        f = self.getfirst(bd)
        if f:
            row = bd[f[0]]
            col = [bd[i][f[1]] for i in range(sz)]
            box = self.getbox(f[0], f[1], bd)        
            curr = set(row + col + box)
            options = nums-curr
            if options:
                for opt in options:
                    bd[f[0]][f[1]] = opt
                    if not self.solveSudoku(bd):
                        bd[f[0]][f[1]] = None
                    else:
                        return True
            else:
                False
        else:
            return True
            
        
brd  = [
            [5, 3, None, None, 7, None, None, None, None],
            [6, None, None, 1, 9, 5, None, None, None],
            [None, 9, 8, None, None, None, None, 6, None],
            [8, None, None, None, 6, None, None, None, 3],
            [4, None, None, 8, None, 3, None, None, 1],
            [7, None, None, None, 2, None, None, None, 6],
            [None, 6, None, None, None, None, 2, 8, None],
            [None, None, None, 4, 1, 9, None, None, 5],
            [None ,None, None, None, 8, None, None, 7, 9]
        ]

s = Solution()
s.solveSudoku(brd)
brd<jupyter_output><empty_output><jupyter_text>38. Count and Say-------The count-and-say sequence is the sequence of integers with the first five terms as following:1.     12.     113.     214.     12115.     1112211 is read off as "one 1" or 11.11 is read off as "two 1s" or 21.21 is read off as "one 2, then one 1" or 1211.Given an integer n, generate the nth term of the count-and-say sequence.Note: Each term of the sequence of integers will be represented as a string.Example 1:Input: 1Output: "1"Example 2:Input: 4Output: "1211"<jupyter_code>class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        i=1
        say="1"
        while i<=n:
            curr = None
            cnt = 0
            spell = []
            for j in range(len(say)):
                if curr == say[j]:
                    cnt+=1
                else:
                    if curr:
                        spell.append((curr, cnt))
                    cnt=1
                    curr=say[j]
            spell.append((curr, cnt))
            say=""
            for num in spell:
                say += str(num[1]) + str(num[0])
            i+=1
        return say

s=Solution()
s.countAndSay(5)<jupyter_output><empty_output><jupyter_text>39. Combination Sum------Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.The same repeated number may be chosen from C unlimited number of times.Note:All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [  [7],  [2, 2, 3]]<jupyter_code>class Solution(object):
    
    
    def combinationSum(self, nums, val):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        combs = set()
        
        present = set()
        def helper(curr, v):
            
            if v==0:
                #hsh = reduce(lambda acc, x: x*acc, curr, 1)
                hsh = frozenset(curr)
                if hsh not in present:
                    combs.add(tuple(curr))
                    present.add(hsh)
            elif v<0:
                return
            
            for i in nums:
                helper(curr + [i], v-i)
        
        helper([], val)
        return combs

s=Solution()
s.combinationSum([2, 3, 6, 7, 5, 4], 7)

#Since the problem is to get all the possible results, not the best or the number of result, 
#thus we don’t need to consider DP(dynamic programming), recursion is needed to handle it.<jupyter_output><empty_output><jupyter_text>40. Combination Sum II-------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.Each number in C may only be used once in the combination.Note:All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [  [1, 7],  [1, 2, 5],  [2, 6],  [1, 1, 6]]<jupyter_code>class Solution(object):
    
    
    def combinationSum(self, nums, val):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        combs = set()
        
        present = set()
        def helper(curr, ns, v):
            
            if v==0:
                #hsh = reduce(lambda acc, x: x*acc, curr, 1)
                hsh = frozenset(curr)
                if hsh not in present:
                    combs.add(tuple(curr))
                    present.add(hsh)
            elif v<0:
                return
            
            for ind, i  in enumerate(ns):
                send = ns[:ind] + ns[ind+1:]
                helper(curr + [i], send, v-i)
        
        helper([], nums, val)
        return combs

s=Solution()
s.combinationSum([2, 3, 6, 7, 5, 4], 7)<jupyter_output><empty_output><jupyter_text>41. First Missing Positive------Given an unsorted integer array, find the first missing positive integer.For example,Given [1,2,0] return 3,and [3,4,-1,1] return 2.Your algorithm should run in O(n) time and uses constant space.<jupyter_code>class Solution(object):
    def firstMissingPositive0(self, nums): #This is wrong
        """
        :type nums: List[int]
        :rtype: int
        """
        
        hole = [1, float("inf")]
        
        for i in nums:
            if i == hole[0]:
                hole[0]+=1
            elif i>hole[0] and i<hole[1]:
                hole[1] = i
            
        return hole[0]
    
    def firstMissingPositive(self, nums):
        
        ln = len(nums)
        for i in range(ln):
            v=nums[i]
            while v<ln and v>=0 and v!=nums[v-1]:
                tar = nums[v-1]
                nums[v-1]=v
                nums[i]=tar
                v = tar
        #print nums
        for i, v in enumerate(nums):
            if v != nums[v-1]:
                return i+1

        return ln+1

    
s=Solution()
s.firstMissingPositive([4,3,2,1])<jupyter_output><empty_output><jupyter_text>42. Trapping Rain Water-----Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.<jupyter_code>class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        def btw(i, x, y):
            return (i>x and i<y) or (i>y and i<x)
        
        
        hgts=[]
        for ind, h in enumerate(height):
            hgts.append((ind, h))
            
        hts = hgts[:]
        hts.sort(lambda x, y: x[1] - y[1], reverse=True)

        voldt = []
        for i in range(len(hts)):
            if i and not voldt:
                wd = abs(hts[i][0] - hts[i-1][0])-1
                vol = wd*hts[i][1]
                voldt.append([vol, hts[i][0], hts[i-1][0]])
            elif i:
                found=False
                for vl in voldt:
                    if btw(hts[i][0], vl[1], vl[2]):
                        vl[0] -= hts[i][1]
                        found = True 
                if not found:
                    nearest = voldt[0][1]
                    for vl in voldt:
                        if abs(nearest - hts[i][0]) > abs(vl[1] - hts[i][0]):
                            nearest=vl[1]
                        if abs(nearest - hts[i][0]) > abs(vl[2] - hts[i][0]):
                            nearest=vl[2]
                    wd = abs(hts[i][0] - nearest)-1
                    vol = wd*hts[i][1]
                    voldt.append([vol, hts[i][0], nearest])
        
        #print voldt
        totalvol = 0
        for vl in voldt:
            totalvol+=vl[0]
        
        return totalvol
    
    def trap0(self, height):
        ans = 0
        sz=len(height)
        
        for i in range(sz):
            ml=0
            mr=0
            for j in range(i, sz):
                ml = max(ml, height[j])
            for j in range(0, i+1):
                mr = max(mr, height[j])
            
            ans += min(ml, mr) - height[i]
            #print i
            #print height[i]
            #print min(ml, mr)
            
            #print ans
            #print "--"
        return ans
    
    def trapDP(self, height):
        leftvol = [0]*len(height)
        cmax=0
        for i in range(len(height)):
            if height[i] < cmax:
                leftvol[i]=cmax-height[i]
            else:
                cmax=height[i]
                leftvol[i]=0
        
        rightvol = [0]*len(height)
        cmax=0
        for i in range(len(height)-1,-1,-1): # this could be done in the previous loop itself
            if height[i] < cmax:
                rightvol[i]=cmax-height[i]
            else:
                cmax=height[i]
                rightvol[i]=0            
        vol=0
        for i in range(len(height)):
            vol+=min(leftvol[i],rightvol[i])# this could be done in the first loop itself
        
        return vol
    
s=Solution()
s.trapDP([0,1,0,2,1,0,1,3,2,1,2,1])

# Can do the above in O(1) space by accumulating leftvols and rightvols while leftmax<rightmax 
# (until this point leftvols depend only on leftmax and right vols depend only on rightmax)<jupyter_output><empty_output><jupyter_text>43. Multiply Strings----Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.Note:1. The length of both num1 and num2 is < 110.2. Both num1 and num2 contains only digits 0-9.3. Both num1 and num2 does not contain any leading zero.4. You must not use any built-in BigInteger library or convert the inputs to integer directly.<jupyter_code>class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        
        
        def mhelp(ind):
            n = int(num2[ind])
            res=0
            place = 1
            for i in range(len(num1)-1, -1, -1):
                res += int(num1[i])*n*place
                place*=10
            return res
        
        ans=0
        place=1
        for x in range(len(num2)-1, -1, -1):
            ans += mhelp(x)*place
            place*=10
        return str(ans)
            
s=Solution()
s.multiply("111", "12")

#karatsuba or FFT<jupyter_output><empty_output><jupyter_text>44. Wildcard Matching-----Implement wildcard pattern matching with support for '?' and '*'.'?' Matches any single character.'*' Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "\*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?\*") → trueisMatch("aab", "c\*a\*b") → false<jupyter_code>import numpy as np

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        lns = len(s)
        lnp = len(p)
        def match(i, j):
            while i<lns and j<lnp and p[j]!='?' and p[j]!='*' and s[i] == p[j]:
                i+=1
                j+=1
            
            if j==lnp and i<lns:
                return False
            if i==lns and j==lnp:
                return True
            
            if p[j]=='*':
                m = match(i, j+1)
                for ind in range(i+1, lns+1):
                    m |= match(ind, j+1)
                return m
            elif p[j]=='?': # this could just be put in the while loop above
                return match(i+1, j+1)
            else:
                return False
            
        def matchDP2D(i, j):
            M = np.zeros((lns+1, lnp+1), dtype=bool)
            M[lns, lnp] = True

            # invariant lns-x >= lnp-y (more xs can be gobbled by y)
            for y in range(lnp-1,-1,-1):
                for x in range(lns-1,y-1,-1):
                    if p[y] == '?' or s[x]==p[y]:
                        M[x, y] = M[x+1,y+1]
                    elif p[y] == "*":
                        M[x, y] = reduce(lambda x, y: x or y, M[x:, y+1])
                    else:
                        M[x, y] = False
            print M
            return M[0,0]
            
        return matchDP2D(0, 0)

s=Solution()
s.isMatch("caabbbccc", "c*b*c")

# We can see that this 2D matrix can be reduced to 1D as 
# a column only depends on its next column -- filled right to left

# This can be modified to to O(1) space by just keeping track of where the start occured
# since x,y depends on x+1, y+1 or on whether something was matched before the star

# More intuitively:
#For each element in s
#If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
#If p=='*', this is also a match, but one or many chars may be available, 
#            so let us save this *'s position and the matched s position.
#If not match, then we check if there is a * previously showed up,
#       if there is no *,  return false;
#       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position<jupyter_output>[[ True False False False False False]
 [False  True False False False False]
 [False  True False False False False]
 [False  True  True  True False False]
 [False  True  True  True False False]
 [False  True  True  True False False]
 [False False False  True False False]
 [False False False  True False False]
 [False False False  True  True False]
 [False False False False False  True]]<jupyter_text>45. 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.For example:Given array A = [2,3,1,1,4]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.)Note:You can assume that you can always reach the last index.<jupyter_code>class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        last = len(nums)-1
        def helper(ind):

            if ind>=last:
                return 0
            
            minj=last+1
            for i in range(1, nums[ind]+1):
                minj = min(minj, 1+helper(ind+i))
                
            return minj
        
        def helperDP(ind):
            arr = range(last, -1, -1)
            for i in range(last, ind-1, -1):
                if i == last:
                    continue
                for j in range(1, nums[ind]+1):
                    if i+j<=last:
                        arr[i] = min(arr[i], 1+arr[i+j])
                    else:
                        arr[i] = 1
            return arr[0]
        
        def fasthelp(ind):
            
            for i in range(last+1)
                if nums[i]
        return helperDP(0)

s=Solution()
s.jump([2, 3, 1, 1, 4])

# helper time complexity is O(n*(product of all the nums))?
# helperDP time complexity is O(n^2)
# both have space complexity of O(n) either recursion stack or through the list stored 

# In one traversal keep pushing reachability from current position for the current number of jumps:
# int jump(int A[], int n) { //O(N)
#    if(n<2) return 0;
#       int level=0,currentMax=0,i=0,nextMax=0;
# 
#       while(currentMax-i+1>0){ //nodes count of current level>0
#           level++;
#           for(;i<=currentMax;i++){ //traverse current level , and update the max reach of next level
#              nextMax=max(nextMax,A[i]+i);
#              if(nextMax>=n-1) return level;// if last element is in level+1,  then the min jump=level
#           }
#    
#           if(currentMax==nextMax) return INT_MAX; //***cannot move forward from this level
#    
#           currentMax=nextMax;
#       }
#    }<jupyter_output><empty_output><jupyter_text>55. Jump Game-----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.Determine if you are able to reach the last index.For example:A = [2,3,1,1,4], return true.A = [3,2,1,0,4], return false.<jupyter_code># Same as before, but need not keep track of level or no. of jumps, just check the currentmax'es<jupyter_output><empty_output><jupyter_text>46. Permutations------Given a collection of distinct numbers, return all possible permutations.For example,[1,2,3] have the following permutations:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]<jupyter_code>class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        perms = []
        
        def helper(ns, curr):
            if not ns: #or curr is of size len(nums)
                perms.append(curr)

            for i in range(len(ns)):
                newcurr = curr[:] # do this outside the loop and append new char and pop before and after rec. call
                newns = ns[:i] + ns[i+1:] # Use bitmap of used/unused instead of creating this in every recursion step
                helper(newns, newcurr+[ns[i]])
            
        helper(nums, [])
        return perms
    
s=Solution()
s.permute([1, 2, 3])<jupyter_output><empty_output><jupyter_text>47. Permutations II---Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example,[1,1,2] have the following unique permutations:[  [1,1,2],  [1,2,1],  [2,1,1]]<jupyter_code>class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        perms = []
        nums.sort()
        def helper(ns, curr):
            if not ns: #or curr is of size len(nums)
                perms.append(curr)

            for i in range(len(ns)):
                if i>0 and ns[i]==ns[i-1]:
                    continue
                else:
                    newcurr = curr[:] #check suggestions in the previous problem
                    newns = ns[:i] + ns[i+1:]
                    helper(newns, newcurr+[ns[i]])
            
        helper(nums, [])
        return perms
    
s=Solution()
s.permuteUnique([1, 1, 3])
            
# Similar to finding power set:
# Key idea: Sort the nums, when a number has the same value with its previous, 
#           we can use curr num only if previous num is used

# instead of passing the array and using the key idea, 
# we can just maintain a count of each item (takes care of permutations within same element) 
# and decrement it when used

# each stack uses O(n) and there are logn stack frames => O(nlogn) space, but total space required is O(#permutations*n)
# Same is the case with time complexity (could be reduced to O(num_perms) if we use counter and dont clone it)<jupyter_output><empty_output><jupyter_text>48. Rotate Image---You are given an n x n 2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Note:You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.Example 1:Given input matrix = [  [1,2,3],  [4,5,6],  [7,8,9]],rotate the input matrix in-place such that it becomes:[  [7,4,1],  [8,5,2],  [9,6,3]]Example 2:Given input matrix =[  [ 5, 1, 9,11],  [ 2, 4, 8,10],  [13, 3, 6, 7],  [15,14,12,16]], rotate the input matrix in-place such that it becomes:[  [15,13, 2, 5],  [14, 3, 4, 1],  [12, 6, 8, 9],  [16, 7,10,11]]<jupyter_code>class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        
        
        def rotswap(a, b, c, d):
            tmp = matrix[a[0]][a[1]]
            matrix[a[0]][a[1]] = matrix[d[0]][d[1]]
            matrix[d[0]][d[1]] = matrix[c[0]][c[1]]
            matrix[c[0]][c[1]] = matrix[b[0]][b[1]]
            matrix[b[0]][b[1]] = tmp
            
        n=len(matrix)
        def helper(start):
            
            end = n-start-1
            if start>=end:
                return
            for i in range(end-start):
                rotswap([start, start+i], [start+i, end], [end, end-i], [end-i, start])
                
            helper(start+1)
        
        helper(0)
        
s=Solution()

m0 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

m1 = [
    [5, 1, 9, 11],
    [2, 4, 8, 10],
    [13, 3, 6, 7],
    [15, 14, 12, 16]
]
s.rotate(m1)
m1

# Other ways include:
# 1. horizontally flip the image and then transpose
# 2. If blit'ing is allowed use the algorithm shown in Jeff Erikson's text 
# (need to work out how its better time complexity)<jupyter_output><empty_output><jupyter_text>49. Group Anagrams------Given an array of strings, group anagrams together.For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:[  ["ate", "eat","tea"],  ["nat","tan"],  ["bat"]]Note: All inputs will be in lower-case.<jupyter_code>class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        
        def phash(s):
            h = 1
            for j in s:
                f = ord(j) - ord('a')
                h *= pi[f]
            return h
        
        # Note the first 26 primes
        pi = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
              31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
              73, 79, 83, 89, 97, 101]
        
        ph = {}
        for i in strs:
            x = phash(i)
            if x in ph:
                ph[x].append(i)
            else:
                ph[x] = [i]
        
        anas = []
        for key in ph:
            anas.append(ph[key])

        return anas
    
s=Solution()
strings = ["eat", "tea", "tan", "ate", "nat", "bat"]
s.groupAnagrams(strings)

# Time and space complexity O(n*k)
# but this solution may cause type overflow if strings are huge

# Other solutions:
# 1. Hash on sorted strings instead of prime products
#      Time complexity O(n*klogk) and space complexity O(n*k)
# 2. Hash on character counts (which is like char hash in itself) instead of prime products
#      Time and space complexity O(n*k)<jupyter_output><empty_output><jupyter_text>50. Pow(x, n)----Implement pow(x, n).Example 1:Input: 2.00000, 10Output: 1024.00000Example 2:Input: 2.10000, 3Output: 9.26100<jupyter_code>class Solution(object):
    def myPow(self, x0, n0):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        
        def naive(x, n):
            if n==0:
                return 1
            else:
                return x*naive(x, n-1)
            
        def better(x, n): 
            
            if n==1:
                return x
            
            z = (n%2!=0)*(x-1) +1
            y = better(x, n/2)
            ret = (y**2)*z
            return ret
        
            # better(y, 2)*z can't be used as no matter what the y value 
            # better(., 2) will call itself before returning and there's no bound to this
        
        return better(x0, n0)
    
s=Solution()
s.myPow(2.1, 3)

# better() is O(logn) time complexity and space complexity, 
# make it tail recursive for O(1) space or just use while loop<jupyter_output><empty_output><jupyter_text>51. N-Queens--------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.Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.For example,There exist two distinct solutions to the 4-queens puzzle:[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]<jupyter_code>class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        
        brds = []
        
        def valid(b, x, y):
            for p in range(n):
                #if b[x][p] == 'Q': # not needed as we are doing one Q per row anyway
                #    return False
                if b[p][y] == 'Q':
                    return False
                if x+p<n and y+p<n:
                    if b[x+p][y+p] == 'Q':
                        return False
                if x-p>=0 and y-p>=0:
                    if b[x-p][y-p] == 'Q':
                        return False
                if x-p>=0 and y+p<n:
                    if b[x-p][y+p] == 'Q':
                        return False
                if x+p<n and y-p>=0:
                    if b[x+p][y-p] == 'Q':
                        return False
            return True
                
        def solve(curr, nq):
            if not nq:
                board = [j[:] for j in curr]
                brds.append(board)
                return True
            
            for i in range(n): 
                # one Q per line, so check only chars in the kth line for the kth Q
                if valid(curr, nq-1, i):
                    curr[nq-1][i] = 'Q'
                    solve(curr, nq-1)
                    curr[nq-1][i] = '.'
                    
        current = []
        for i in range(n):
            current.append(['.']*n)
        solve(current, n)
        return brds

s=Solution()
s.solveNQueens(4)<jupyter_output><empty_output><jupyter_text>52. N-Queens II------Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions.<jupyter_code>class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        pass

# No need to have the board and place queen on the board etc., just count
# keep track of the used 45/135 diags and columns with a hash set or bitmask

# Need clarification on what distinct solutions means (are rotations of board equivalent?)<jupyter_output><empty_output><jupyter_text>53. Maximum Subarray-------Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4,-1,2,1] has the largest sum = 6.More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.<jupyter_code>class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start=0
        curmax=0
        cum=0
        for ind, i in enumerate(nums):
            cum+=i
            if cum<0:
                cum=0
                start=ind+1
            else:
                if cum>curmax:
                    curmax = cum
                    curtup = (start, ind)
            
        return curmax, curtup
                
        
s=Solution()
s.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])

# Key idea: anytime cumsum goes negative start over :P

# Divide and conquer...<jupyter_output><empty_output><jupyter_text>54. Spiral Matrix----Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.For example,Given the following matrix:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]You should return [1,2,3,6,9,8,7,4,5].<jupyter_code>class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        
        n=len(matrix)
        def helper(start):
            end = n-start-1
            
            if start==end:
                return [matrix[start][start]]
            elif start>end:
                return []
            top=[]
            right=[]
            bottom=[]
            left=[]

            for i in range(start, end):
                top.append(matrix[start][start+i])
                right.append(matrix[start+i][end])
                bottom.append(matrix[end][end-i])
                left.append(matrix[end-i][start])
                
            return top + right + bottom + left + helper(start+1)
        
        return helper(0)
        
s=Solution()
m0 = [
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
m1 = [
 [ 1, 2],
 [ 4, 5]
]
s.spiralOrder(m1)<jupyter_output><empty_output><jupyter_text>56. Merge Intervals------Given a collection of intervals, merge all overlapping intervals.For example,Given [1,3],[2,6],[8,10],[15,18],return [1,6],[8,10],[15,18].<jupyter_code># Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        
        intervals.sort(lambda x, y: x.start - y.start)
        lni = len(intervals)
        i=1
        while i<lni:
            if intervals[i-1].end > intervals[i].start:
                intervals[i].start = intervals[i-1].start
                del intervals[i-1]
                lni-=1
            else:
                i+=1
        return intervals

s=Solution()
inter = [Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15, 18)]
ans=s.merge(inter)<jupyter_output><empty_output><jupyter_text>57. Insert Interval-----Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).You may assume that the intervals were initially sorted according to their start times.Example 1:Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].Example 2:Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].<jupyter_code># Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e
        
class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        intervals.sort(lambda x, y: x.start - y.start)
        lni = len(intervals)
        i=0
        startbefore=None #starting before start
        endbefore=None # ending before an end
        st=None
        nd=None
        largemerge=False
        while i<lni:
            if (i==0 or newInterval.start > intervals[i-1].end) and newInterval.start < intervals[i].start:
                if newInterval.end < intervals[i].start:
                    intervals.insert(i, newInterval)
                    break
                elif newInterval.end <= intervals[i].end:
                    intervals[i].start = newInterval.start
                    break
                else:
                    largemerge=True
                    st=i
                    startbefore=True
            elif newInterval.start >= intervals[i].start and newInterval.start <= intervals[i].end:
                if i==lni or newInterval.end < intervals[i+1].start and newInterval.end > intervals[i].end:
                    intervals[i].end = newInterval.end
                    break
                elif newInterval.end <= intervals[i].end:
                    break
                else:
                    largemerge=True
                    st=i
                    startbefore=False
            elif newInterval.end > intervals[i].start and newInterval.end <= intervals[i].end:
                nd=i
                largemerge=True
                endbefore=True
            elif newInterval.end > intervals[i].end and (i==lni or newInterval.end < intervals[i+1].start):
                nd=i
                largemerge=True
                endbefore=False
            i+=1
                
        if largemerge:
            if startbefore:
                if endbefore:
                    intervals[nd].start=newInterval.start
                    del intervals[st:nd]
                else:
                    del intervals[st:(nd+1)]
                    intervals.insert(st, newInterval)
            else:
                if endbefore:
                    intervals[st].end=intervals[nd].end
                    del intervals[st+1:nd+1]
                else:
                    intervals[st].end=newInterval.end
                    del intervals[st+1:nd+1]
        return intervals
    
s=Solution()
inter = [Interval(1, 2), Interval(3, 5), Interval(6, 7), Interval(8, 10), Interval(12, 16)]
ins = Interval(4, 9)
x=s.insert(inter, ins)

# Could improve the above code by just tracking st and nd for all the cases :P<jupyter_output><empty_output><jupyter_text>58. Length of Last Word----Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.If the last word does not exist, return 0.Note: A word is defined as a character sequence consists of non-space characters only.Example:Input: "Hello World"Output: 5<jupyter_code>class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        ln = len(s)
        skipword = False
        
        i=ln-1
        llw = 0
        while i>=0:
            if skipword and s[i] == ' ':
                skipword=False
            elif skipword:
                pass
            else:
                while i>=0 and s[i].isalpha():
                    llw+=1
                    i-=1
                if i>0 and s[i] != ' ':
                    llw=0
                    skipword=True
                else:
                    break
            i-=1
        
        if skipword:
            return 0
        else:
            return llw
        
s=Solution()
s.lengthOfLastWord("Hi World1")<jupyter_output><empty_output><jupyter_text>59. Spiral Matrix II----Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.For example,Given n = 3,You should return the following matrix:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]<jupyter_code>class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        
        mat = []
        for i in range(n):
            mat.append([0]*n)
        
        def helper(start, v):
            
            end = n-start-1
            if start==end:
                mat[start][start]=v
            elif start>end:
                return
            else:
                ln = end-start
                for i in range(ln):
                    mat[start][start+i] = v
                    mat[start+i][end] = ln + v
                    mat[end][end-i] = 2*ln + v
                    mat[end-i][start] = 3*ln + v
                    v+=1
                
                helper(start+1, 3*ln + v)
                
        helper(0, 1)
        return mat

s=Solution()
s.generateMatrix(4)<jupyter_output><empty_output><jupyter_text>60. Permutation Sequence----The set [1,2,3,…,n] contains a total of n! unique permutations.By listing and labeling all of the permutations in order,we get the following sequence (ie, for n = 3):1. "123"2. "132"3. "213"4. "231"5. "312"6. "321"Given n and k, return the kth permutation sequence.Note: Given n will be between 1 and 9 inclusive.<jupyter_code>class Solution(object):
    
    def __init__(self):
        self.perm=""
    
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """

        def factorial(acc, m):
            if m==1:
                return acc
            
            return factorial(acc*m, m-1) 

        # perm = "", closure semantics are bad in Python :P
        def helper(nums, p, q, r):
            if len(self.perm)==n:
                return
            
            rfact = q/r
            sth = p/rfact
            curr = nums[sth]
            self.perm += str(curr) # use linked list to perform this in O(1)
            del nums[sth]          # can't get better than O(n) with deleting sth item as well as getting sth item
            helper(nums, (p-(rfact*sth)), rfact, r-1)
            
        helper(range(1, n+1), k-1, factorial(1, n), n)
        return self.perm

s=Solution()
s.getPermutation(4, 7)


# Brute Force: start with all numbers sorted (1st permutation),
#              keep iterating using nextPermutation (Problem 31), till kth permuttion

# Better soln.: first (n-1)! numbers start with lowest number i.e 1, next (n-1)
# iteratively divide n! by n to get next range of values. This is O(n) space and O(n^2) time complexity

# Both fns are tail-recursive, so can be optimized to save stack space<jupyter_output><empty_output><jupyter_text>61. Rotate List-----Given a list, rotate the list to the right by k places, where k is non-negative.Example:Given 1->2->3->4->5->NULL and k = 2,return 4->5->1->2->3->NULL.<jupyter_code># Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        
        curr=head
        n=1
        while curr.next:
            n+=1
            curr=curr.next
        
        modk = k%n
        if not modk:
            return head
        
        tail = curr        
        curr = head
        ln = n-modk-1
        while ln:
            ln-=1
            curr=curr.next
            
        newhead = curr.next
        curr.next = None
        tail.next = head
        
        return newhead

s=Solution()
rot = ListNode(1)
rot.next = ListNode(2)
rot.next.next = ListNode(3)
rot.next.next.next = ListNode(4)
rot.next.next.next.next = ListNode(5)

y=s.rotateRight(rot, 2)
x=y
while x:
    print x.val
    x=x.next<jupyter_output>4
5
1
2
3<jupyter_text>62. Unique Paths-----A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).How many possible unique paths are there?Note: m and n will be at most 100.<jupyter_code>class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        
        def factorial(acc, p):
            if p==1:
                return acc
            return factorial(acc*p, p-1)
        
        steps = m+n
        return factorial(1, steps)/(factorial(1, m)*factorial(1, n))

s=Solution()
s.uniquePaths(3, 5)

# 2**((m-1)*(n-1)) This is not right as this need not form a path!<jupyter_output><empty_output><jupyter_text>63. Unique Paths II----Follow up for "Unique Paths":Now consider if some obstacles are added to the grids. How many unique paths would there be?An obstacle and empty space is marked as 1 and 0 respectively in the grid.For example,There is one obstacle in the middle of a 3x3 grid as illustrated below.[  [0,0,0],  [0,1,0],  [0,0,0]]The total number of unique paths is 2.Note: m and n will be at most 100.<jupyter_code>class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        
        def helper(i, j):
            if i==0 and j==0:
                return 1
            elif (i==0 or obstacleGrid[i-1][j]) and j>0:
                return helper(i, j-1)
            elif (j==0 or obstacleGrid[i][j-1]) and i>0:
                return helper(i-1, j)
            elif i>0 and j>0:
                return helper(i-1, j) + helper(i, j-1)
            
        lnx=len(grd)
        lny=len(grd[0])
        return helper(lnx-1, lny-1)

s=Solution()
grd = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 0]
]
s.uniquePathsWithObstacles(grd)

# The advantage here is that because theres only left and up actions, this becomes a tree of possibilities
# Otherwise its a graph and we might have to care about going in circles (infinite paths essentially)

# Memoization optimizations:
# i, j depends on i-1, j and i, j-1, 
# so instead of O(m*n) space complexity, we can do this in O(m+n) excluding input grid space
# we can store only (i-1)th row and (j-1)th column and fill ith row and jth column 
# and then throw away (i-1)th row and (j-1)th column

#Actually further reduce by filling rowwise(left to right)/coumnwise(top to bottom) to O(min(m, n)) space<jupyter_output><empty_output><jupyter_text>64. Minimum Path Sum----Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at any point in time.Example 1:[[1,3,1], [1,5,1], [4,2,1]]Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.<jupyter_code>class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        
        def helper(i, j):
            if i==0 and j==0:
                return grid[i][j]
            if i==0 and j>0:
                return grid[i][j] + helper(i, j-1)
            if j==0 and i>0:
                return grid[i][j] + helper(i-1, j)
            if i>0 and j>0:
                return grid[i][j] + min(helper(i, j-1), helper(i-1, j))
        
        lnx = len(grid)
        lny = len(grid[0])
        return helper(lnx-1, lny-1)

s=Solution()
g=[
    [1,3,1],
    [1,5,1],
    [4,2,1]
]
s.minPathSum(g)

# Memoise and fill rowwise(left to right)/coumnwise(top to bottom) resulting in O(min(m,n)) space
# If the grid is vandalizable, use it and fill cumulative min sums<jupyter_output><empty_output><jupyter_text>65. Valid Number----Validate if a given string is numeric.Some examples:"0" => true" 0.1 " => true"abc" => false"1 a" => false"2e10" => trueNote: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.<jupyter_code>class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """

# For base36, we have all string with any alpanumeric chars acceptable,
# Work with interviewer to obtain the spec. for definition of "valid number"<jupyter_output><empty_output><jupyter_text>66. Plus One----Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.You may assume the integer do not contain any leading zero, except the number 0 itself.The digits are stored such that the most significant digit is at the head of the list.<jupyter_code>class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        
        ln = len(digits)
        
        for i in range(ln-1, -1, -1):
            if digits[i]<9:
                digits[i]+=1
                return digits
            else:
                digits[i]=0
                
        newdigits = [1] + digits[:]
        return newdigits
    
s=Solution()
s.plusOne([9,9,9,9])<jupyter_output><empty_output><jupyter_text>67. Add Binary---Given two binary strings, return their sum (also a binary string).For example,a = "11"b = "1"Return "100".<jupyter_code>class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        
        lna = len(a)
        lnb = len(b)
        smaln, bign, sn, bn = (a, b, lna, lnb) if lna<lnb else (b, a, lnb, lna)
        
        dif = bn-sn
        carry=0
        res=[]
        for i in range(sn-1, -1, -1):
            if smaln[i]=='1' and bign[i+dif]=='1':
                if carry:
                    res.append('1')
                else:
                    res.append('0')
                    carry=1
            elif smaln[i]=='0' and bign[i+dif]=='0':
                if carry:
                    res.append('1')
                    carry=0
                else:
                    res.append('0')
            else:
                if carry:
                    res.append('0')
                else:
                    res.append('1')

        for i in range(dif-1, -1, -1):
            if carry and bign[i]=='1':
                res.append('0')
            else:
                res.append('1')
                carry=0
            
        if carry:
            res.append('1')
        
        newbits=""
        for i in range(len(res)-1, -1, -1):
            newbits += res[i]
            
        return newbits
    
s=Solution()
s.addBinary('110', '1')<jupyter_output><empty_output><jupyter_text>68. Text Justification----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.You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.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 more spaces than the slots on the right.For the last line of text, it should be left justified and no extra space is inserted between words.For example,words: ["This", "is", "an", "example", "of", "text", "justification."]L: 16.Return the formatted lines as:[   "This    is    an",   "example  of text",   "justification.  "]Note: Each word is guaranteed not to exceed L in length.Corner Cases:A line other than the last line might contain only one word. What should you do in this case?In this case, that line should be left-justified.<jupyter_code>class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        lines = []
        
        def tailrec(ind):
            
            cum=len(words[ind])
            curr = [words[ind]]
            moreleft=False
            for i in words[ind+1:]:
                if len(i) + 1 + cum <= maxWidth:
                    cum += len(i) + 1
                    curr.append(i)
                else:
                    moreleft=True
                    break

            spaces = maxWidth - cum + len(curr) - 1
            if moreleft:
                if len(curr) > 1:
                    btw = len(curr)-1

                    quo = spaces/btw
                    rem = spaces%btw
                    i=0
                    line = curr[0]
                    for wrd in curr[1:]:
                        if i < rem:
                            line+= " "*(quo+1)
                        else:
                            line+= " "*quo
                        line+=wrd
                        i+=1
                else:
                    line = curr[0]
                    line+=" "*(spaces)
    
                lines.append(line)
                tailrec(ind+len(curr))
            else:
                line = curr[0]
                for wrd in curr[1:]:
                    line+=" "
                    line+=wrd

                line+=" "*(spaces)
                lines.append(line)

        tailrec(0)
        return lines

s=Solution()
words = ["This", "is", "an", "example", "of", "text", "justification."]
L = 16
s.fullJustify(words, L)<jupyter_output><empty_output><jupyter_text>69. Sqrt(x)----Implement int sqrt(int x).Compute and return the square root of x.x is guaranteed to be a non-negative integer.Example 1:Input: 4Output: 2Example 2:Input: 8Output: 2Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.<jupyter_code>class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        
        
        def helper(low, high):
            mid = (high+low)/2
            
            if (mid)**2 <= x and (mid+1)**2 > x:
                return mid
            elif (mid+1)**2 <= x:
                return helper(mid, high)
            elif (mid)**2 > x:
                return helper(low, mid)
            
        return helper(0, x)

s=Solution()
s.mySqrt(0)<jupyter_output><empty_output><jupyter_text>70. Climbing Stairs---You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Note: Given n will be a positive integer.Example 1:Input: 2Output:  2Explanation:  There are two ways to climb to the top.1. 1 step + 1 step2. 2 stepsExample 2:Input: 3Output:  3Explanation:  There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 2 steps + 1 step<jupyter_code>class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if n==0:
            return 1
        elif n<0:
            return 0
        return self.climbStairs(n-1) + self.climbStairs(n-2)

s=Solution()
s.climbStairs(3)

#Memoize this solution: This is equivalent to fibonacci and done with O(1) space and O(n) time
#Fibonacci can also be converted to tail call recursive by having two accumulators  (fib a, b, n = fib b, a+b, n-1)

# Can achieve O(logn) time by matrix exponentiation [[1, 1], [1, 0]]^n gives nth fib on right to left diag
# exponentiation is O(logn) as seen in problem 50 (implement pow), and the marix is of constant 2*2 size

# Generating fns! A std. way to solve such recursion formulas: assume F_n = a^n
# Then, a^{n+2}= a^{n+1}+ a^n; divide the entire equation by a^n we arrive at a^2 = a + 1
# This requires exponentiation and hence O(logn)<jupyter_output><empty_output><jupyter_text>71. Simplify Path-----Given an absolute path for a file (Unix-style), simplify it.For example,path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"Corner Cases:Did you consider the case where path = "/../"?In this case, you should return "/".Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".In this case, you should ignore redundant slashes and return "/home/foo".<jupyter_code>class Solution(object):
    def simplifyPath(self, p):
        """
        :type path: str
        :rtype: str
        """
        path = list(p) # Use Linkedlist for O(n) time and space
        
        i=0
        while i<len(path):
            if path[i]=='.' and (not path[i+1]=='.' or i==len(path)-1):
                del path[i-1]
                del path[i-1]
                i-=1
            elif i+2<len(path) and path[i] == '.' and path[i+1] == '.' and path[i+2] == '.':
                while path[i] == '.':
                    i+=1
            elif i+1<len(path) and path[i] == '.' and path[i+1] == '.':
                if i-2>=0:
                    curr = i-2
                else:
                    curr=0
                while path[curr] != '/':
                    curr-=1
                curr+=1
                
                #stillfile = True if path[curr]!='/' else False # to handle "/.../.." or "..../.." -- better use stack
                while not (path[curr] == '.' and path[curr+1] == '.'):
                    del path[curr]
                    #stillfile = True if path[curr]!='/' else False 
                del path[curr]
                del path[curr]
                if curr<len(path) and path[curr] == '/':
                    del path[curr]
                i=curr
            elif i+1<len(path) and path[i] == '/' and path[i+1] == '/':
                del path[i]
            else:
                i+=1
                
        if path[-1]=='/':
            del path[-1]
        
        return "".join(path)
    
s=Solution()
s.simplifyPath("/home/")
s.simplifyPath("/a/./b/../../c/")
                    
# Use Linkedlist for O(n) time and space
# A cleaner way to do this is to split on '/' and use stack and in the end join with '/'
# so we would be considering filenames atomic tokens:
# this is needed to handle cases where filenames could be '...' etc. which is not handled above :(<jupyter_output><empty_output><jupyter_text>72. Edit Distance----Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a word:a) Insert a characterb) Delete a characterc) Replace a character<jupyter_code>class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        
        def helperRec(i, j):
            if i==len(word1) or j==len(word2):
                return max(len(word1)-i, len(word2)-j)
            if word1[i] == word2[j]:
                return helperRec(i+1, j+1)
            else:
                # del jth char or del ith char or replace ith or jth char
                return 1 + min(helperRec(i, j+1), helperRec(i+1, j), helperRec(i+1, j+1))

    
        def helperDP_opt():
            ln1 = len(word1)
            ln2 = len(word2)
            
            sln, bln, sw, bw = (ln1, ln2, word1, word2) if ln1<ln2 else (ln2, ln1, word2, word1)
            
            prev = [0]*(sln+1)
            val = 0
            for i in range(sln, -1, -1):
                prev[i]=val
                val+=1
            
            curr = [0]*(sln+1)
            for j in range(bln-1, -1, -1):
                curr[sln]=bln-j
                for i in range(sln-1, -1, -1):
                    if sw[i] == bw[j]:
                        curr[i] = prev[i+1]
                    else:
                        curr[i] = 1 + min(prev[i], curr[i+1], prev[i+1])
                        
                prev = curr[:]

            return curr[0]
        
        return helperDP_opt()

s=Solution()
s.minDistance("hello world", "hell world")

# O(min(len1, len2)) space complexity and O(len1*len2) time complexity<jupyter_output><empty_output><jupyter_text>Edit distance for Search------Returns close matches within a Levenshtein distance from the given word from a set of words O([max word length] \* [number of nodes in the trie])  vs. O([number of words] \* [max word length]^2)<jupyter_code>#!/usr/bin/python
#By <NAME>, 2011. Released to the public domain
import time
import sys

DICTIONARY = ["pea", "pet", "animal", "dog", "dust", "den", "man", "human", "superman", "batman", "amazer", "plea"] #"/usr/share/dict/words";
TARGET = "pot" #sys.argv[1]
MAX_COST = 2 #int(sys.argv[2])

# Keep some interesting statistics
NodeCount = 0
WordCount = 0

# The Trie data structure keeps a set of words, organized with one node for
# each letter. Each node has a branch for each letter that may follow it in the
# set of words.
class TrieNode:
    def __init__(self):
        self.word = None
        self.children = {}

        global NodeCount
        NodeCount += 1

    def insert( self, word ):
        node = self
        for letter in word:
            if letter not in node.children: 
                node.children[letter] = TrieNode()

            node = node.children[letter]

        node.word = word

# read dictionary file into a trie
trie = TrieNode()
for word in DICTIONARY: #open(DICTIONARY, "rt").read().split():
    WordCount += 1
    trie.insert( word )

print "Read %d words into %d nodes" % (WordCount, NodeCount)

# The search function returns a list of all words that are less than the given
# maximum distance from the target word
def search( word, maxCost ):

    # build first row
    currentRow = range( len(word) + 1 )

    results = []

    # recursively search each branch of the trie
    for letter in trie.children:
        searchRecursive( trie.children[letter], letter, word, currentRow, 
            results, maxCost )

    return results

# This recursive helper is used by the search function above. It assumes that
# the previousRow has been filled in already.
def searchRecursive( node, letter, word, previousRow, results, maxCost ):

    columns = len( word ) + 1
    currentRow = [ previousRow[0] + 1 ]

    # Build one row for the letter, with a column for each letter in the target
    # word, plus one for the empty string at column 0
    for column in xrange( 1, columns ):

        insertCost = currentRow[column - 1] + 1
        deleteCost = previousRow[column] + 1

        if word[column - 1] != letter:
            replaceCost = previousRow[ column - 1 ] + 1
        else:                
            replaceCost = previousRow[ column - 1 ]

        currentRow.append( min( insertCost, deleteCost, replaceCost ) )

    # if the last entry in the row indicates the optimal cost is less than the
    # maximum cost, and there is a word in this trie node, then add it.
    if currentRow[-1] <= maxCost and node.word != None:
        results.append( (node.word, currentRow[-1] ) )

    # if any entries in the row are less than the maximum cost, then 
    # recursively search each branch of the trie
    if min( currentRow ) <= maxCost:
        for letter in node.children:
            searchRecursive( node.children[letter], letter, word, currentRow, 
                results, maxCost )

start = time.time()
results = search( TARGET, MAX_COST )
end = time.time()

for result in results: print result        

print "Search took %g s" % (end - start)<jupyter_output>Read 12 words into 49 nodes
('dog', 2)
('pea', 2)
('pet', 1)
Search took 0.000190973 s<jupyter_text>73. Set Matrix Zeroes----Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.Follow up:Did you use extra space?A straight forward solution using O(mn) space is probably a bad idea.A simple improvement uses O(m + n) space, but still not the best solution.Could you devise a constant space solution?<jupyter_code>class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        row = set()
        col = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if not matrix[i][j]:
                    row.add(i)
                    col.add(j)

        for i in row:
            for j in range(len(matrix[0])):
                matrix[i][j]=0

        for j in col:
            for i in range(len(matrix)):
                matrix[i][j]=0
                
        return matrix
    
s=Solution()
m = [
    [1, 2, 3, 4, 5, 6],
    [4, 0, 6, 7, 8, 9],
    [7, 8, 0, 10, 11, 12],
    [7, 8, 12, 10, 11, 12],
    [7, 8, 12, 10, 0, 13],
    [7, 8, 11, 10, 11, 12]
    
]
s.setZeroes(m)

# The above solution takes O(m+n) space, we could do this without taking extra space 
# by indicating whether to erase a row or column at the first column or row respectively
# and using two vars to indicate whether to erase first row and first column<jupyter_output><empty_output><jupyter_text>74. Search a 2D Matrix----Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of the previous row.For example,Consider the following matrix:[  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]Given target = 3, return true.<jupyter_code>class Solution(object):
    def searchMatrix(self, matrix, val):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        def bins_row(low, high): # tail recursive
            mid = (low+high)/2
            if matrix[mid][0]<=val and (mid+1 == len(matrix) or val<matrix[mid+1][0]):
                return (True, mid)
            elif val<matrix[mid][0] and mid==0:
                return (False, 0)
            elif val<matrix[mid][0]:
                return bins_row(low, mid-1)
            elif mid+1 == len(matrix) or val>=matrix[mid+1][0]:
                return bins_row(mid+1, high)
            
        def bins_col(low, high, r):
            if low>high:
                return False
            
            mid = (low+high)/2
            if matrix[r][mid]==val:
                return True
            elif matrix[r][mid]<val:
                return bins_col(mid+1, high, r)
            elif matrix[r][mid]>val:
                return bins_col(low, mid-1, r)
            
        found, row = bins_row(0, len(matrix)-1)
        if found:
            return bins_col(0, len(matrix[0])-1, row)
        else:
            return False
        
s=Solution()
m = [
    [1,   3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

s.searchMatrix(m, 10)
            
# bin search for specific row in first column and then bin search on that row --> O(logm + logn)
# Lesser Code: if the matrix 2D is just thought of as a single sorted list, then O(log(m*n))
# start with l=0 and r=m*n-1 (but m*n may cause multiplicaton overflow -- careful!)
# mid = (l + r)/2 and check the number matrix[mid/m][mid%m]

# Both have same complexity<jupyter_output><empty_output><jupyter_text>75. Sort Colors----Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, 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.Note:You are not suppose to use the library's sort function for this problem.Follow up:A rather straight forward solution is a two-pass algorithm using counting sort.First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.Could you come up with an one-pass algorithm using only constant space?<jupyter_code>class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        def quickhelper (l, r):  # just for fractice :P
            
            if l>=r:
                return
            curr = nums[l]
            lp = l+1
            rp = r
            while lp<=rp:
                if nums[lp]<=curr:
                    lp+=1
                elif nums[rp]>=curr:
                    rp-=1
                else:
                    tmp = nums[lp]
                    nums[lp] = nums[rp]
                    nums[rp] = tmp
            tmp = nums[lp-1]
            nums[lp-1] = curr
            nums[l]=tmp
            
            quickhelper(l, lp-2)
            quickhelper(lp, r)
        
        #quickhelper(0, len(nums)-1)
        
        def counts():
            zers = 0
            ones = 0
            twos = 0
            for i in nums:
                if i==0:
                    zers+=1
                elif i==1:
                    ones+=1
                elif i==2:
                    twos+=1
                else:
                    return "Err"
            
            for i in range(len(nums)):
                if zers:
                    nums[i]=0
                    zers-=1
                elif ones:
                    nums[i]=1
                    ones-=1
                elif twos:
                    nums[i]=2
                    twos-=1
        
        def better():
            zerp = 0
            twop = len(nums)-1
            
            i=0
            while i<twop:
                if nums[i]==0:
                    if i==zerp:
                        zerp+=1
                        i+=1
                    else:
                        nums[i]=nums[zerp]
                        nums[zerp]=0
                        zerp+=1
                elif nums[i]==2:
                    while nums[twop]==2:
                        twop-=1
                    nums[i] = nums[twop]
                    nums[twop]=2
                    twop-=1
                else:
                    i+=1      
        
        better()
        return nums

s=Solution()
s.sortColors([2, 1, 0, 2, 2, 2, 2, 1, 1, 1, 0, 0, 2, 0, 2, 0, 1, 2, 0, 2, 1])

# It seems like you'll need 3 variables atleast!

# The key idea is to use either Lomuto's or Hoare's partition scheme used as part of QuickSort
# Lomuto preforms relatively poorly when there is a high percentage of duplicate values 
# ( i.e. where say more than 2/3rds the array is the same value )
# Lomuto requires 3 times more number of swaps on average if input is uniform random dist.
# https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

# History: This problem introduced by Dijkstra as the Dutch National Flag problem 
# Motiv: to design sorting aglos -- variants of quick sort that is robust to repeated elements
# needing need a three-way partitioning function that groups items 
# less than a given key (red), equal to the key (white) and greater than the key (blue)<jupyter_output><empty_output><jupyter_text>The Dutch National Flag Problem============Pedagogical Dimension-----Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting:“Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's and sketched some code to make his point; I stopped looking after I found two bugs.”Performance Dimension-----For practical use, ease of implementation might be sacrificed for the sake of efficiency. On a theoretical basis, we can determine the number of element comparisons and swaps to compare performance. Additionally, actual running time will be influenced by other factors, such as caching performance and branch mispredictions.As shown below, the algorithms behave very similar on random permutations except for the number of swaps. There Lomuto needs thrice as many as Hoare!Number of ComparisonsBoth methods can be implemented using n−1n−1 comparisons to partition an array of length nn. This is essentially optimal, since we need to compare every element to the pivot for deciding where to put it.Number of SwapsThe number of swaps is random for both algorithms, depending on the elements in the array. If we assume random permutations, i.e. all elements are distinct and every permutation of the elements is equally likely, we can analyze the expected number of swaps.As only relative order counts, we assume that the elements are the numbers 1,…,n1,…,n. That makes the discussion below easier since the rank of an element and its value coincide.Lomuto's Method-----The index variable jj scans the whole array and whenever we find an element A[j]A[j] smaller than pivot xx, we do a swap. Among the elements 1,…,n1,…,n, exactly x−1x−1 ones are smaller than xx, so we get x−1x−1 swaps if the pivot is xx.The overall expectation then results by averaging over all pivots. Each value in {1,…,n}{1,…,n} is equally likely to become pivot (namely with prob. 1n1n), so we have$$\frac1n \sum_{x=1}^n (x-1) = \frac n2 - \frac12\;.$$swaps on average to partition an array of length nn with Lomuto's method.Hoare's Method-----Here, the analysis is slightly more tricky: Even fixing pivot xx, the number of swaps remains random.More precisely: The indices ii and jj run towards each other until they cross, which always happens at xx (by correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by ii and a right part scanned by jj.Now, a swap is done exactly for every pair of “misplaced” elements, i.e. a large element (larger than xx, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part. Note that this pair forming always works out, i.e. there the number of small elements initially in the right part equals the number of large elements in the left part.One can show that the number of these pairs is hypergeometrically Hyp(n−1,n−x,x−1) distributed: For the n−xn−x large elements we randomly draw their positions in the array and have x−1x−1 positions in the left part. Accordingly, the expected number of pairs is (n−x)(x−1)/(n−1) given that the pivot is xx.Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning:$$\frac1n \sum_{x=1}^n \frac{(n-x)(x-1)}{n-1} = \frac n6 - \frac13\;.$$(A more detailed description can be found in my master's thesis, page 29.)Memory Access PatternBoth algorithms use two pointers into the array that scan it sequentially. Therefore both behave almost optimal w.r.t. caching.Equal Elements and Already Sorted ListsAs already mentioned by Wandering Logic, the performance of the algorithms differs more drastically for lists that are not random permutations.On an array that is already sorted, Hoare's method never swaps, as there are no misplaced pairs (see above), whereas Lomuto's method still does its roughly n/2 swaps!The presence of equal elements requires special care in Quicksort. (I stepped into this trap myself; see my master's thesis, page 36, for a “Tale on Premature Optimization”) Consider as extreme example an array which filled with 0s. On such an array, Hoare's method performs a swap for every pair of elements - which is the worst case for Hoare's partitioning - but ii and jj always meet in the middle of the array. Thus, we have optimal partitioning and the total running time remains in O(nlog⁡n).Lomuto's method behaves much more stupidly on the all 0 array: The comparison A[j] <= x will always be true, so we do a swap for every single element! But even worse: After the loop, we always have i=ni=n, so we observe the worst case partitioning, making the overall performance degrade to Θ(n2)!ConclusionLomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.From  reference  76. Minimum Window Substring-----Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).For example,S = "ADOBECODEBANC"T = "ABC"Minimum window is "BANC".Note: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.<jupyter_code>import sys
class LinkedList(object):
    def __init__(self, i, v):
        self.ind=i
        self.val=v
        self.next=None


class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """

        req = set(t) # if t can have repetitions, use counter and decrement if found in s
        pospre = {}
        currmin = (len(s)+1, "")
        head=None
        tail=None
        for ind, val in enumerate(s):
            if val in req:
                req.remove(val)
                if not head:
                    head=LinkedList(ind, val)
                    tail=head
                    pospre[val]=None
                else:
                    tail.next=LinkedList(ind, val)
                    pospre[val]=tail
                    tail=tail.next
            elif val in pospre:
                if pospre[val]:
                    if pospre[val].next == tail:
                        tail=pospre[val]
                    else:
                        pospre[val].next = pospre[val].next.next
                else:
                    head=head.next
                    pospre[head.val]=None
                    
                tail.next=LinkedList(ind, val)
                pospre[val]=tail
                tail=tail.next
                
            if not req:
                ln = tail.ind-head.ind
                if currmin[0] > ln:
                    currmin=(ln, s[head.ind:tail.ind+1])
            #print currmin
            #cur=head
            #while cur:
            #    sys.stdout.write(str(cur.val)+", ")
            #    cur=cur.next
            #print ""
        
        return currmin[1]
                
s=Solution()
S = "ADOBECODEBANC"
T = "ABC"
s.minWindow(S, T)

# Key: use hash to a linkedlist to maintain curr start and update recent elements and a set to check when done<jupyter_output><empty_output><jupyter_text>Similar Problems:------------Minimum Window Substring, Longest Substring with At Most Two Distinct Characters, Longest Substring Without Repeating CharactersAlgo:1. Use two pointers: start and end to represent a window.2. Move end to find a valid window.3. When a valid window is found, move start to find a smaller window. 77. Combinations----Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.For example,If n = 4 and k = 2, a solution is:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]<jupyter_code>class Solution(object):
    
    def __init__(self):
        self.combs = []
        
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        
        def helper(curr, ind):
            if len(curr) == k:
                self.combs.append(curr)
                return
            
            for i in range(ind, n+1):
                helper(curr+[i], i+1)

                
        helper([], 1)
        return self.combs
    
s=Solution()
s.combine(6, 4)<jupyter_output><empty_output><jupyter_text>Similar problems:----------Combinations, Permutations, Subsets (w/ dupes), Valid parentheses/brackets, etc 79. Word Search----Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.For example,Given board =[  ['A','B','C','E'],  ['S','F','C','S'],  ['A','D','E','E']]word = "ABCCED", -> returns true,word = "SEE", -> returns true,word = "ABCB", -> returns false.<jupyter_code>class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        
        lni = len(board)
        lnj = len(board[0])

        def find_0():
            firsts = []
            for i in range(lni):
                for j in range(lnj):
                    if board[i][j] == word[0]:
                        firsts.append((i, j))
            return firsts
        
        def nexts(i, j):
            return ((i-1, j), (i+1, j), (i, j-1), (i, j+1))
        
        def validnxt(i, j):
            if (i, j) not in visited and i>=0 and j>=0 and i<lni and j<lnj:
                return True
            else:
                return False

        def run(ind, x, y):
            if ind == len(word):
                return True
            elif board[x][y] == word[ind]:
                if ind == len(word)-1:
                    return True
                found = False
                for pos in nexts(x, y): 
                    if validnxt(pos[0], pos[1]):
                        visited.add(pos)
                        found |= run(ind+1, pos[0], pos[1])
                        visited.remove(pos)
                return found
            else:
                return False
        
        found = False        
        for pos in find_0():
            visited = set()
            visited.add(pos)
            found |= run(0, pos[0], pos[1])
            visited.remove(pos)
        return found
            
s=Solution()

b = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]

s.exist(b, "ABCCEDFSA")

# Wrap around could be introduced by using mods: instead of i-1, use (i-1)%lni

# Time complexity is O(m*n*4^k) and space complexity is O(m*n)<jupyter_output><empty_output><jupyter_text>212. Word Search II (Boggle)---Given a 2D board and a list of words from the dictionary, find all words in the board.Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.For example,Given words = ["oath","pea","eat","rain"] and board =[  ['o','a','a','n'],  ['e','t','a','e'],  ['i','h','k','r'],  ['i','f','l','v']]Return ["eat","oath"].Note:You may assume that all inputs are consist of lowercase letters a-z.<jupyter_code>#class TrieNode:
#    def __init__(self):
#        self.word = None
#        self.children = {}
#
#        global NodeCount
#        NodeCount += 1
#
#    def insert( self, word ):
#        node = self
#        for letter in word:
#            if letter not in node.children: 
#                node.children[letter] = TrieNode()
#
#            node = node.children[letter]
#
#        node.word = word

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """

        lni = len(board)
        lnj = len(board[0])
        
        # Trie implementation:
        head={}
        for wrd in words:
            curr = head
            for i in wrd:
                #if not i in curr:
                #    curr[i] = {}
                #curr = curr[i]
                curr = curr.setdefault(i, {}) # equivalent to the above
            curr["*end*"] = "*end*" # if you don't have this any subset of a wrd can be part of the set
                                    # the value here could capture counts etc.
        print head
        def nexts(i, j):
            return ((i-1, j), (i+1, j), (i, j-1), (i, j+1))
        
        def validnxt(i, j):
            if (i, j) not in visited and i>=0 and j>=0 and i<lni and j<lnj:
                return True
            else:
                return False


        present=set()
        visited = set()
        def run(x, y, curtrie, curstr):
            if board[x][y] in curtrie:
                curtrie = curtrie[board[x][y]]
                if "*end*" in curtrie:
                    present.add(curstr+board[x][y])
                else:
                    for pos in nexts(x, y):
                        if validnxt(pos[0], pos[1]):
                            visited.add(pos)
                            run(pos[0], pos[1], curtrie, curstr+board[x][y])
                            visited.remove(pos)
        

        for x in range(lni):
            for y in range(lnj):
                run(x, y, head, "")

        return present

s=Solution()
w = ["oath","pea","eat","rain"]
b = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['n','h','k','p'],
  ['i','a','x','v']
]
s.findWords(b, w)

# Time complexity is O(m*n*4^maxlen)
# without the trie and using the previous Word Search I solution, 
# Time complexity is O(p*m*n*4^maxlen), p=#words<jupyter_output>{'p': {'e': {'a': {'*end*': '*end*'}}}, 'r': {'a': {'i': {'n': {'*end*': '*end*'}}}}, 'e': {'a': {'t': {'*end*': '*end*'}}}, 'o': {'a': {'t': {'h': {'*end*': '*end*'}}}}}<jupyter_text>80. Remove Duplicates from Sorted Array II-----Follow up for "Remove Duplicates":What if duplicates are allowed at most twice?For example,Given sorted array nums = [1,1,1,2,2,3],Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.<jupyter_code>class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        i = 1
        j = 1
        currcnt = 1
        prev = nums[0]
        while i<len(nums):
            if nums[i] == prev and currcnt<2:
                currcnt+=1
            elif nums[i] == prev and currcnt==2:
                while i<len(nums) and nums[i] == prev:
                    i+=1
                if i == len(nums):
                    break
                prev=nums[i]
                currcnt=1
            elif nums[i]!=prev:
                prev=nums[i]
                currcnt=1                
            nums[j]=nums[i]
            i+=1
            j+=1
        return j
s=Solution()
n=[1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9]
s.removeDuplicates(n)

# Quicker solution:
#    i = 0
#    for n in nums:
#        if i < 2 or n > nums[i-2]: 
#        # i.e. if n==n[i-2] skip it, 
#        # because its sorted it'll be greater if we are to include
#            nums[i] = n
#            i += 1

# Change all the 2's to k's above, to generalize to k repetitions<jupyter_output><empty_output><jupyter_text>81. Search in Rotated Sorted Array II------Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?Would this affect the run-time complexity? How and why?Suppose an array sorted in ascending order 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).Write a function to determine if a given target is in the array.The array may contain duplicates.<jupyter_code># My previous solution works with the same complexities of O(logn), why not...
# No, the search for the pivot degrades to O(n) now!

#tricky because sometimes we cannot decide whether to go to the left side or right side => linear probe

class Solution(object):
    
    def findstart(self, nums):
        val = nums[0]
        low = 0 
        high = len(nums)-1
        prev = nums[low]
        while low<high and nums[low] == nums[high] and nums[high] == prev:
            low+=1
            high-=1
        if nums[low] == nums[high]:
            if prev>num[low]:
                return low
            else:
                return high
        if low == high:
            return 0
        elif nums[low] < nums[high]:
            return low
        else:

            while low<high:
                assert(nums[low] > nums[high])
                mid = (high+low)/2
                
                if nums[mid] > nums[mid+1]:
                    return mid+1
                if nums[mid-1] > nums[mid]:
                    return mid
                # because of the structure of rotated list: 
                # when comparing values of nums at mid,  low and high
                # <mid can be here> nums[high] <mid cannot be here> nums[low] <mid can be here>
                if nums[mid] < nums[low] and nums[mid] <= nums[high]:   
                    high=mid-1
                elif nums[mid] >= nums[low] and nums[mid] > nums[high]:
                    low=mid+1
                #elif nums[mid] >= val:
                #    low = mid+1
                #else:
                #    high = mid-1
                else:
                    return "error"
            return "error"
    
    def search(self, nums, val):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        start = self.findstart(nums)
        a = self.binsearch(nums, val, start, len(nums)-1)
        b = a if a>-1 else self.binsearch(nums, val, 0, start-1)
        return b
        
    def binsearch(self, nums, val, i, j):
        low = i 
        high = j
        while low <= high:
            mid = (high+low)/2
            if nums[mid] == val:
                return mid
            if nums[mid] > val:
                high = mid-1
            else:
                low = mid+1
        return -1
        
    
s=Solution()
s.search([5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 1, 2, 4, 4, 4, 5, 5, 5, 5], 2)

# We can do this with just one binary search traversal
# There are two sublists which are sorted, keep track of which part mid is in 
# and also of which part w.r.t mid the target is in (reject the rest of the space)
# if (nums[left] == nums[mid]) and (nums[right] == nums[mid]): left+=1, right-=1<jupyter_output><empty_output><jupyter_text>82. Remove Duplicates from Sorted List II----Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.For example,Given 1->2->3->3->4->4->5, return 1->2->5.Given 1->1->1->2->3, return 2->3.<jupyter_code># Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

def lprint(curr):        
    while curr:
        sys.stdout.write(str(curr.val)+" ")
        curr=curr.next
    print ""
    
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        curr=head
        dupe=False
        currprev=None
        while curr:
            prev=None
            while curr.next and curr.val == curr.next.val:
                prev=curr
                curr=curr.next
            if prev and prev.val==curr.val:
                if not currprev:
                    head=curr.next
                else:
                    currprev.next=curr.next
                    currprev=curr
            else:
                currprev=curr
                #print currhead.val
                #lprint(head)
            curr=curr.next
        return head
    
s=Solution()
a=ListNode(1)
a.next=ListNode(2)
a.next.next=ListNode(2)
a.next.next.next=ListNode(3)
a.next.next.next.next=ListNode(4)
h=s.deleteDuplicates(a)
lprint(h)<jupyter_output>1 3 4<jupyter_text>83. Remove Duplicates from Sorted List----Given a sorted linked list, delete all duplicates such that each element appear only once.For example,Given 1->1->2, return 1->2.Given 1->1->2->3->3, return 1->2->3<jupyter_code>#use set (hash) :P<jupyter_output><empty_output><jupyter_text>84. Largest Rectangle in Histogram-----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.Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area = 10 unit.For example,Given heights = [2,1,5,6,2,3],return 10.<jupyter_code># same as Containing most water (problem 11)?
# No!!<jupyter_output><empty_output><jupyter_text>85. 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.For example, given the following matrix:1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Return 6.<jupyter_code>import pprint
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        n=len(matrix)
        m=len(matrix[0])

        def helperDP2():
            pass
            M1 = [[0]*(m+1) for i in range(n+1)]
            for i in range(1, n):
                for j in range(1, m):
                    M1[i, j] = M1[i, j-1] + 1 if matrix[i][j] else 0
                    
            for j in range(1, m):
                curr=0
                mini=float("+infinity")
                for i in range(1, n):
                    if not M1[i, j]:
                        curr=0
                        mini=float("+infinity")
                    else:
                        curr+=1
                        if mini>M1[i, j]:
                            mini=M1[i, j]
                        
                    max(curr*mini, M1[i, j])
                    M1[i, j] =  if matrix[i][j] else 0
                
        def helperDP():
            pass
            M = [[0]*(m+1) for i in range(n+1)]
            
            for j in range(m+1):
                M[0][j] = (0, (0, 0))
            for i in range(n+1):
                M[i][0] = (0, (0, 0))
              
            max_rect = (0, None)
            for i in range(1, n):
                for j in range(1, m):
                    #pprint.pprint(M)
                    if matrix[i][j]:
                        if matrix[i-1][j]:
                            k=j-1
                            while k>-1 and matrix[i][k]:
                                k-=1
                            maxj = max(M[i-1][j][1][1], k+1)
                            A = ((i-M[i-1][j][1][0])*(j-maxj), (M[i-1][j][1][0], maxj))
                        else:
                            A = (1, (i, j))
                        if matrix[i][j-1]:
                            k=i-1
                            while k>-1 and matrix[k][j]:
                                k-=1
                            maxi = max(M[i][j-1][1][0], k+1)
                            B = ((i-maxi)*(j-M[i][j-1][1][1]), (maxi, M[i][j-1][1][1]))  
                        else:
                            B = (1, (i, j))
                        M[i][j] = A if A[0]>B[0] else B
                    else:
                        M[i][j] = (0, (i, j))
                    if M[i][j][0]>max_rect[0]:
                        max_rect=M[i][j]
                                       
            return max_rect[0]
        return helperDP()

s=Solution()
m = [
        [1, 0, 1, 0, 0],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ]
s.maximalRectangle(m)

# expand curr rect -- up, down, left, right
# use DP/memoization to prevent recalculations

#Expand current rectangle by iterating i, j in two nexted loops and capture the current rect areas at every i, j


# Screw all the above complicated solutions, check this:
# Find max rectangle in histogram for each row (or column), updating maxest rectange along<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11425240454677936, 'fraction_numerical': 0.021752884389817376, 'mean_word_length': 1.7679896105940458, 'pattern_counts': {'":': 8, '<': 439, '<?xml version=': 0, '>': 492, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '80', 'dir': 'jupyter-structured-clean-dedup', 'id': '337044', 'license': 'MIT', 'n_tokens_mistral': 45292, 'n_tokens_neox': 42482, 'n_words': 14386, 'path': 'LeetCodeSolutions_1-100.ipynb', 'repo_name': 'nishanthprakash/MuscleMemory', 'size': '140676'}