Leetcode (python): 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 ]
]

Solution:

class Solution:
    # @return a list of lists of integer
    def generateMatrix(self, n):
        matrix=[];
        for i in range(0,n):
            matrix.append([])
            for j in range(0,n):
                matrix[i].append(0)
        
        direction = "right"
        row = 0
        col = 0
        for count in range(1,n*n+1):
            matrix[row][col] = count
            if direction == "right":
                col = col + 1;
                if col >= n-1 or matrix[row][col+1] != 0:
                    direction = "down"
            elif direction == "down":
                row = row + 1;
                if row >= n-1 or matrix[row+1][col] != 0:
                    direction = "left"
            elif direction == "left":
                col = col - 1;
                if col <= 0 or matrix[row][col-1] != 0:
                    direction = "up"
            elif direction == "up":
                row = row - 1;
                if row <= 0 or matrix[row-1][col] != 0:
                    direction = "right"
        return matrix

LeetCode (Python): Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution:

Stack 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 nothing, do it in place
    def flatten(self, root):
       if root == None:
           return
       stack = []
       stack.append(root)
       while len(stack) > 0:
           actual = stack.pop();
           if actual.right != None:
               stack.append(actual.right)
           if actual.left != None:
               stack.append(actual.left)
           if len(stack) > 0:
               actual.right = stack[len(stack)-1]
           actual.left = None

Inplace 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 nothing, do it in place
    def flatten(self, root):
        while root != None:
            if root.left != None:
                pre = root.left
                while pre.right != None:
                    pre = pre.right
                pre.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

Leetcode: 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 height = [2,1,5,6,2,3],
return 10.

Solution:

We use a stack we keep the positions of increasing height, we also have to ensure that there is no element smaller in the histogram in between.  

For instance, when we are processing the 4th element in the example the stack will be (4,3,2) and when we process the 5th element we pop two elements before pushing the processing element, becoming the stack (5, 2).

When we pop an element ($tp$)  we can calculate the maximum rectangle with the this element as height as follows: $height[tp] *  (i-stack.peek()-1)$

public class Solution {
    public int largestRectangleArea(int[] height) {
        if(height.length == 0)
            return 0;
        Deque stack = new ArrayDeque();
        
        int maxArea=0;
        int i = 0;
        while (i < height.length)
        {
            if(stack.isEmpty() || height[i] >= height[stack.peek()] )
                stack.push(i++);
            else
            {
                int tp = stack.pop();  
                
                int area = height[tp] * (stack.isEmpty() ? i : i - stack.peek() - 1);
 
                if (maxArea < area)
                    maxArea = area;
            }
        } 
        
        while (!stack.isEmpty())
        {
                int tp = stack.pop();  
                
                int area = height[tp] * (stack.isEmpty() ? i : i-1 - stack.peek());
 
                if (maxArea < area)
                    maxArea = area;
        }
 
        return maxArea;
    }
}

Leetcode: Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:

public class Solution {
    public int maxProfit(int[] prices) {
        int maxBenefit = 0;
        int prevMin = Integer.MAX_VALUE;
        for(int i=0; i < prices.length; i++)
        {
            if (prices[i] < prevMin)
                prevMin = prices[i];
            if (maxBenefit < prices[i]- prevMin)
                maxBenefit = prices[i]- prevMin;
        }
        return maxBenefit;
    }
}

Leetcode (Python): Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        minValue = float("inf")
        maxBenefit = 0
        for price  in prices:
            if minValue > price:
                minValue = price
            if maxBenefit < price - minValue:
                maxBenefit = price - minValue
        return maxBenefit

Leetcode: Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Solution:

We use a top-down dynamic approach where we need a 3D array to keep the information, hence the memory complexity is $O(n^3)$.

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length()!=s2.length())
            return false;
        Boolean[][][] isScramble= new Boolean [s1.length()][s1.length()][s1.length()];
        return isScramble(s1,s2,0,0,s1.length()-1, isScramble);
    }
    
    private boolean isScramble(String s1, String s2, int index1, int index2, int len, Boolean[][][] isScramble)
    {
        if(isScramble[index1][index2][len] != null)
            return isScramble[index1][index2][len];
        if(len==0)
            isScramble[index1][index2][len] = s1.charAt(index1)==s2.charAt(index2);
        else
        {
            boolean value = false;
            for (int i=0; i<len; i++)
            {
                value = value ||  (isScramble(s1,s2,index1, index2, i, isScramble) && isScramble(s1,s2, index1+i+1,index2+i+1,len-i-1, isScramble)) ||  (isScramble(s1,s2,index1,index2+len-i, i, isScramble) && isScramble(s1,s2,index1+i+1,index2,len-i-1, isScramble));
            }
            isScramble[index1][index2][len] = value;
        }
        return isScramble[index1][index2][len]; 
    }
}

Leetcode: Wildcard Matching

'?' 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") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Solution:

Using a "greedy" approach, where we try to reach the end of p, saving the last occurrence of '*' but  match an * by the empty string. In the case that we arrive to a state we cannot go on, we retrieve the saved state and we make the * to match one character more each than the previous time.

public class Solution {
    public boolean isMatch(String s, String p) {
        int si = 0, pi = 0;
        int ss=-1, pp =-1;
        while(si<s.length())
        {
            if(si<s.length() && pi<p.length() && s.charAt(si)==p.charAt(pi)){si++; pi++; continue;}
            if(si<s.length() && pi<p.length() && p.charAt(pi)=='?'){si++; pi++; continue;}
            if(si<s.length() && pi<p.length() && p.charAt(pi)=='*'){ss=si; pp=pi++; continue;}
            if(pp!=-1 && pp <p.length()){si =ss++; pi=pp +1; continue;}
            return false;
        }
        while (pi<p.length() && p.charAt(pi)=='*'){pi++;}
        return pi==p.length();
    }
}