Leetcode (Python): Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution:

We first preprocess the needle, in such a way that we obtain the equivalent states, for instance:

   a a b a a b c
   0 0 1 0 1 2 3

That means that if we are have found aabaab, we have also found aab. When we process the haystack, when we arrive to a state that we cannot go on, we change to its previous equivalent state.

class Solution:
    # @param haystack, a string
    # @param needle, a string
    # @return a string or None
    def strStr(self, haystack, needle):
        if len(needle)==0:
            return haystack
        equivalentState=[0]
        previousState = 0;
        for i in range(1,len(needle)):
            equivalentState.append(previousState)
            if needle[previousState] == needle [i]:
                previousState += 1
            else:
                previousState = 0
        position = 0
        state = 0
        while position < len(haystack):
            if haystack[position] == needle[state]:
                position += 1
                state += 1
                if state == len(needle):
                    return haystack[position-state:]
            else:
                if state == 0:
                    position +=1
                else:
                    state = equivalentState[state]
        return None

LeetCode (Python): 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 in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Solution:

class Solution:
    # @param a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        if len(A)==0:
            return 0
        end = 0;
        for i in range(1,len(A)):
            if A[i] != A[end]:
                end += 1
                self.swap(A,i,end)
        return end + 1
                
            
            
    def swap(self, A, pos1, pos2):
        temp = A[pos1]
        A[pos1] = A[pos2]
        A[pos2] = temp

LeetCode (Python): Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Solution

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        stack = []
        node = root
        solution = []
        while node!= None or len(stack)>0:
            if node != None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                solution.append(node.val)
                node = node.right
        return solution

Other solution:

This solution needs more space but is easier to understand.

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        stack = []
        if root != None:
            stack.append(root)
        solution = []
        used = set()
        while len(stack)>0:
            node = stack.pop()
            if node in used:
                solution.append(node.val)
            else:
                used.add(node)
                if node.right != None:
                    stack.append(node.right)
                stack.append(node)
                if node.left != None:
                    stack.append(node.left)
        return solution

LeetCode (Python): Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 

Solution

We can calculate the solution to the problem for 1 transaction, so we use dynamic programming calculating the solution to which is the maximum benefit prior and posterior to certain day, afterwards we just have to iterate through the sum of both arrays finding the maximum.

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        previousMin = float("infinity")
        nextMax = float("-infinity")
        maxProfitSellBefore = [0]
        maxProfitBuyAfter = [0] 
        for i in range(0,len(prices)):
            previousMin = min(previousMin, prices[i])
            if i>0:
                maxProfitSellBefore.append(max(maxProfitSellBefore[i-1], prices[i]-previousMin))
        for i in range(len(prices)-1,-1,-1):
            nextMax = max(nextMax, prices[i])
            if i<len(prices)-1:
                maxProfitBuyAfter.insert(0,max(maxProfitBuyAfter[0], nextMax-prices[i]))
        maxBenefit = 0
        for i in range(0,len(prices)):
            maxBenefit = max(maxBenefit, maxProfitSellBefore[i] + maxProfitBuyAfter[i])
        return maxBenefit

LeetCode (Python): Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Divide and Conquer solution

We merge lists by pairs till we have only one list. The complexity is $O(n log(k))$.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        if len(lists)==0:
            return None
        while len(lists)>1:
            nextLists = []
            for i in range(0,len(lists)-1,2):
                nextLists.append(self.mergeLists(lists[i],lists[i+1]))
            if len(lists)%2==1:
                nextLists.append(lists[len(lists)-1])
            lists = nextLists
        return lists[0]
        
    def mergeLists(self, list1, list2):
        dummy = ListNode(0)
        list = dummy
        while list1 != None and list2 != None:
            if list1.val < list2.val:
                list.next = list1
                list1 = list1.next
            else:
                list.next = list2
                list2 = list2.next
            list = list.next
        if list1 == None:
            list.next = list2
        else:
            list.next = list1
        return dummy.next

LeetCode: Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        List<Integer> solution = new ArrayList<Integer>();
        TreeNode node = root;
        while(!stack.isEmpty() || node !=null)
        {
            if (node != null)
            {
                stack.push(node);
                node = node.left;
            }
            else
            {
                node = stack.pop();
                solution.add(node.val);
                node = node.right;
            }
        }
        return solution;
    }
}

Other solution:

This solution needs more space but is easier to understand.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        List<Integer> solution = new ArrayList<Integer>();
        HashSet<TreeNode> used = new HashSet<TreeNode>();
        if(root!=null)
            stack.push(root);
        while(!stack.isEmpty())
        {
            TreeNode temp = stack.pop();
            if(used.contains(temp))
            {
                solution.add(temp.val);
                continue;
            }
            used.add(temp);
            if (temp.right != null)
                stack.push(temp.right);
            stack.push(temp);
            if (temp.left != null)
                stack.push(temp.left);
        }
        return solution;
    }
}

LeetCode (Python): Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

Solution:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def levelOrderBottom(self, root):
        solution = []
        thisLevel = []
        if root != None:
            thisLevel.append(root)
        while len(thisLevel)>0:
            levelNumbers = []
            nextLevel = []
            for node in thisLevel:
                levelNumbers.append(node.val)
                if node.left != None:
                    nextLevel.append(node.left)
                if node.right != None:
                    nextLevel.append(node.right)
            solution.insert(0,levelNumbers)
            thisLevel = nextLevel
        return solution