Leetcode (Python): Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL

Solution

First, we clarify that k can be larger than the number of elements in the list, so we have to take this into account.
We use two pointers that are separated by k elements.

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

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def rotateRight(self, head, k):
        if head == None:
            return None
        temp = head
        for i in range(0,k):
            if temp.next == None:
                temp = head
            else:
                temp = temp.next
        newLast = head
        while temp.next != None:
            temp = temp.next
            newLast = newLast.next
        temp.next = head
        newHead = newLast.next
        newLast.next = None
        return newHead

LeetCode (Python): Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are mand n respectively.

Solution:

If we start adding the elements from the end to the beginning, once an element is inserted it does not have to be moved

class Solution:
    # @param A  a list of integers
    # @param m  an integer, length of A
    # @param B  a list of integers
    # @param n  an integer, length of B
    # @return nothing
    def merge(self, A, m, B, n):
        indexA = m-1;
        indexB = n-1;
        while indexA >=0 and indexB>=0:
            if A[indexA] > B[indexB]:
                A[indexA+indexB+1] = A[indexA]
                indexA -= 1
            else:
                A[indexA+indexB+1] = B[indexB]
                indexB -= 1
        while indexB >= 0:
             A[indexB] = B[indexB]
             indexB -= 1

Leetcode: Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are mand n respectively.

Solution:

If we start adding the elements from the end to the beginning, once an element is inserted it does not have to be moved

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int indexA = m;
        int indexB = n;
        while(indexA>0 && indexB>0)
        {
            if(A[indexA-1]>B[indexB-1])
                A[indexA+indexB-1] = A[--indexA];
            else
                A[indexA+indexB-1] = B[--indexB];
        }
        while(indexB>0)
        {
            A[indexB-1]= B[--indexB];
        }
    }
}

LeetCode (Python): JumpGame

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.

Solution:

class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        maxReach = 0
        for i in range(0,len(A)):
            if i>maxReach:
                return False
            if maxReach < i+A[i]:
                maxReach = i +A[i]
        return True

Leetcode (Python): Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Solution:

Python does not have the overflowing problem as whenever an integer overflows it promotes it to long values, that have arbitrary precision

class Solution:
    # @return an integer
    def reverse(self, x):
        if x<0:
            return -1*self.reverse(-x)
        sol = 0
        while x != 0:
            sol = sol*10 + x % 10
            x = x // 10
        return int(sol)

Leetcode: Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Solution:

We keep the overflow checking in a comment as leetcode does not accept throwing exceptions, but in a real implementation this needs to be done

public class Solution {
    public int reverse(int x) {
        int sol = 0;
        while(x!=0)
        {
            //if (sol>=((Integer.MAX_VALUE-x%10)/10))
            //    throw new Exception("The number overflows");
            sol = sol * 10 + x % 10;
            x = x/10;
        }
        return sol;
    }
}

Leetcode (Python): 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 =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution:

Using a backtracking algorithm, we could use an extra grid O($n^2$) to mark the used cells so far.
If we were ensured that a certain symbol would not appear in the grid, we could change the cells to mark that have been used, making the algorithm to use constant space. For instance, to pass the leetcode test, the symbol '$' was tried and it did work as shown in the following code.

class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
        solution = False
        for i in range(0,len(board)):
            for j in range(0, len(board[0])):
                solution = solution or self.existRec(board, word, i, j, 0)
        return solution
        
    def existRec(self, board, word, row, col, index):
        if row < 0 or row>=len(board) or col<0 or col>=len(board[0]) or  board[row][col]!=word[index]:
            return False
        if index==len(word)-1:
            return True
        board[row][col] = "$"
        solution = self.existRec(board, word, row-1, col, index+1) or self.existRec(board, word, row+1, col, index+1) or self.existRec(board, word, row, col-1, index+1) or self.existRec(board, word, row, col+1, index+1)
        board[row][col] = word[index]
        return solution

Leetcode (Python): 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.

Solution:

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

class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        dummy = ListNode(0)
        dummy.next = head
        
        previous = dummy
        while previous.next != None and previous.next.next:
            node1 = previous.next
            node2 = previous.next.next
            previous.next = node2
            node1.next = node2.next
            node2.next = node1
            previous = node1
        
        return dummy.next

Leetcode (Python): Pow(x,n)

Implement pow(x, n)

Solution:

We can do this problem in O(log n) by applying $X^n =X^{n/2}\cdot X^{n/2}$ or if $n$ is odd $X^n =X^{(n-1)/2}\cdot X^{(n-1)/2} \cdot X$.

class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        if x==0 or x==1 or n==1:
            return x # We have the problem of 0^0 (that is not 
                     # well-defined), we choose to return 0
        if x==-1:
            if n%2 ==0:
                return 1
            else:
                return -1
        if n==0:
            return 1
        if n<0:
            return 1/self.pow(x,-n)
        val = self.pow(x,n//2)
        if n%2 ==0:
            return val*val
        return val*val*x

Leetcode: Pow(x,n)

Implement pow(x, n)

Solution:

We can do this problem in O(log n) by applying $X^n =X^{n/2}\cdot X^{n/2}$ or $X^n =X^{(n-1)/2}\cdot X^{(n-1)/2} \cdot X$ if $n$ is odd.

public class Solution {
    public double pow(double x, int n) {
        if(x==1 || x==0)
            return x;
        if(x==-1)
            return (n%2)==0?1:-1;
        if (n==0)
            return 1;
        if (n==1)
            return x;
        if(n<0)
            return 1/pow(x,-n);
        double val = pow(x,n/2);
        return (n%2)==0 ? val*val  : val*val*x;
    }
}

Leetcode (Python): Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution:

class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        solution = [""]
        for i in range(0,len(digits)):
            tempList =[];
            for string in solution:
                if digits[i]=='2':
                    tempList.append(string+"a")
                    tempList.append(string+"b")
                    tempList.append(string+"c")
                elif digits[i]=='3':
                    tempList.append(string+"d")
                    tempList.append(string+"e")
                    tempList.append(string+"f")
                elif digits[i]=='4':
                    tempList.append(string+"g")
                    tempList.append(string+"h")
                    tempList.append(string+"i")
                elif digits[i]=='5':
                    tempList.append(string+"j")
                    tempList.append(string+"k")
                    tempList.append(string+"l")
                elif digits[i]=='6':
                    tempList.append(string+"m")
                    tempList.append(string+"n")
                    tempList.append(string+"o")
                elif digits[i]=='7':
                    tempList.append(string+"p")
                    tempList.append(string+"q")
                    tempList.append(string+"r")
                    tempList.append(string+"s")
                elif digits[i]=='8':
                    tempList.append(string+"t")
                    tempList.append(string+"u")
                    tempList.append(string+"v")
                elif digits[i]=='9':
                    tempList.append(string+"w")
                    tempList.append(string+"x")
                    tempList.append(string+"y")
                    tempList.append(string+"z")
            solution = tempList
        return solution

Leetcode (Python): Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given 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.

Solution:

Notice that the number of ways of decoding a string till the ith character is the number of ways of deciding till the previous one (if the ith character is not '0') plus the number of ways to decode till two before (if the last two characters make a valid letter coding, i.e. from 10 till 26).

class Solution:
    # @param s, a string
    # @return an integer
    def numDecodings(self, s):
        if len(s) == 0:
            return 0
        previous = 0
        actual = 1
        for i in range(0,len(s)):
            if not s[i].isdigit():
                return 0
            temp = 0
            if s[i]!='0':
                temp = actual
            if i>0 and s[i-1]!= '0' and int(s[i-1:i+1])<27:
                temp += previous
            previous = actual
            actual = temp
        return actual

Leetcode (Python): Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Solution:

If the circuit is possible, i.e. $\sum \text{gas}\geq \sum \text{cost}$. Then once computed the minimum extra gas needed for the circular route, the minimum extra gas if we start on the next position is the same but not counting the previous position.

class Solution:
    # @param gas, a list of integers
    # @param cost, a list of integers
    # @return an integer
    def canCompleteCircuit(self, gas, cost):
        minVal = float("inf")
        minPos = -1
        gasTillNow = 0
        for i in range(0, len(gas)):
            gasTillNow += gas[i] - cost[i]
            if gasTillNow < minVal:
                minVal = gasTillNow
                minPos = i
        if gasTillNow >=0:
            return (minPos + 1) % len(gas)
        return -1

Leetcode: Word Ladder

 Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:

We first preprocess the dictionary creating a hashmap that contains the list of neighbor words for each one.
Then we apply BFS keeping a set of the nodes already visited.

public class Solution {
    public int ladderLength(String start, String end, 
        HashSet<String> dict) 
    {
        HashMap<String, ArrayList<String>> neighbors = 
            new HashMap<String, ArrayList<String>>();
        for(String word: dict)
        {
            ArrayList<String> listNeighbors = new ArrayList<String>();
            StringBuilder attempt = new StringBuilder(word);
            for(int i=0; i<word.length(); i++)
            {
                for(char letter='a'; letter<='z'; letter++)
                {
                    if(word.charAt(i)==letter)
                        continue;
                    attempt.setCharAt(i,letter);
                    if(dict.contains(attempt.toString()))
                        listNeighbors.add(attempt.toString());
                }
                attempt.setCharAt(i,word.charAt(i));
            }
            neighbors.put(word,listNeighbors);
        }
        
        final String newLevel = "#";
        ArrayDeque<String> queue = new ArrayDeque<String>();
        HashSet<String> usedWords = new HashSet<String>();
        queue.add(start);
        queue.add(newLevel);
        usedWords.add(start);
        int levels = 1;
        while(!queue.isEmpty())
        {
            String actual = queue.remove();
            if(actual.equals(end))
                return levels;
            if(actual.equals(newLevel))
            {
                if(queue.isEmpty() || queue.peek().equals(newLevel))
                    return 0;
                queue.add(newLevel);
                levels++;
            }
            else
            {
                for(String neighbor: neighbors.get(actual))
                {
                    if(!usedWords.contains(neighbor))
                    {
                        queue.add(neighbor);
                        usedWords.add(neighbor);
                    }
                }
            }
        }
        return 0;
    }
}

Leetcode (python): Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution:

class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        
        for i in range(0,9):
            row = []
            col = []
            square = []
            for j in range(0,9):
                row.append(False)
                col.append(False)
                square.append(False)
            for j  in range(0,9):
                if board[i][j] != '.':
                    if board[i][j].isdigit() and int(board[i][j])>0 and int(board[i][j])<=9 and not row[int(board[i][j])-1]:
                        row[int(board[i][j])-1] = True
                    else:
                        return False
                if board[j][i] != '.':
                    if board[j][i].isdigit() and int(board[j][i])>0 and int(board[j][i])<=9 and not col[int(board[j][i])-1]:
                        col[int(board[j][i])-1] = True
                    else:
                        return False
                rowSquare = int(i / 3)*3 + int(j / 3);
                colSquare = (i % 3)*3 + j % 3;
                if board[rowSquare][colSquare] != '.':
                    if board[rowSquare][colSquare].isdigit() and int(board[rowSquare][colSquare])>0 and int(board[rowSquare][colSquare])<=9 and not square[int(board[rowSquare][colSquare])-1]:
                        square[int(board[rowSquare][colSquare])-1] = True
                    else:
                        return False
        return True

Leetcode: Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        for(int i=0; i<9; i++)
        {
            boolean[] row = new boolean[9];
            boolean[] col = new boolean[9];
            boolean[] square = new boolean[9];
            for(int j=0; j<9; j++)
            {
                if(board[i][j] != '.')    
                {
                    if(Character.isDigit(board[i][j]) && !row[board[i][j]-'1']  )
                        row[board[i][j]-'1'] = true;
                    else 
                        return false;
                }
                
                if(board[j][i] != '.')    
                {
                    if(Character.isDigit(board[j][i]) && !col[board[j][i]-'1']  )
                        col[board[j][i]-'1'] = true;
                    else 
                        return false;
                }
                int colS = (i%3)*3+ j%3;
                int rowS = (i/3)*3 + j/3;
                if(board[rowS][colS] != '.')    
                {
                    if(Character.isDigit(board[rowS][colS]) && !square[board[rowS][colS]-'1'] )
                        square[board[rowS][colS]-'1'] = true;
                    else 
                        return false;
                }
            }
        }
        return true;
    }
}

LeetCode (Python): Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

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 an integer
    def minDepth(self, root):
        if root == None:
            return 0
        if root.left == None:
            return self.minDepth(root.right) + 1
        if root.right == None:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left),self.minDepth(root.right))+1

Leetcode: Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        if (root.right == null)
            return minDepth(root.left) + 1;
        if (root.left == null)
            return minDepth(root.right) + 1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

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

Solution:

class Solution:
    # @return an integer
    def numTrees(self, n):
        return self.numTrees2(1, n)
        
    def numTrees2(self, minV, maxV):
        if minV >= maxV:
            return 1
        val = 0
        for i in range(minV,maxV+1):
            val = val + self.numTrees2(minV, i-1)*self.numTrees2(i+1, maxV)
        return val

Leetcode: 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

Solution:

public class Solution {
    public int numTrees(int n) 
    {
        return numTrees(1, n);
    }
    
    public int numTrees(int min, int max) 
    {
        if(min>=max)
            return 1;
        int val = 0;
        for (int i=min; i<=max; i++)
        {
            val += numTrees(min, i-1) *numTrees(i+1, max);
        }
        return val;
    }
}

Leetcode (Python): Recover Binary Search Tree

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?

Solution

If we traverse the tree inorder, we just need to identify the 2 elements that are misplaced and swap their values. We also keep a third pointer that points to the previous element as it is needed to identify when an element is misplaced.

# 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 tree node
    
    def recoverTree(self, root):
        self.pre = None
        self.node1 = None
        self.node2 = None
        self.inOrder(root)
        val = self.node1.val
        self.node1.val = self.node2.val
        self.node2.val = val
        return root
        
    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.left)
        if self.pre == None:
            self.pre = root
        if self.node1 == None and self.pre.val > root.val:
            self.node1 = self.pre
            self.node2 = root
        elif self.pre.val > root.val:
            self.node2 = root
        self.pre = root;
        self.inOrder(root.right)
        return

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();
    }
}

Leetcode: 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 emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

We first preprocess T to obtain an array with the number of apperarances of each character, then we traverse S keeping the minimum window that contains all the letters of T.

public class Solution {
    public String minWindow(String S, String T) {
        int[] tProcessed = new int['z'-'A'+1];
        for(int i=0; i<T.length();i++)
            tProcessed[T.charAt(i)-'A']++;
        int begin = 0;
        int lettersFound = 0;
        int end = 0;
        int minWindow = Integer.MAX_VALUE;
        int startMinWindow = -1;
        int[] window = new int['z'-'A'+1];
        while(end<S.length())
        {
            window[S.charAt(end)-'A']++;
            if (window[S.charAt(end)-'A']<=tProcessed[S.charAt(end)-'A'])
                lettersFound++;
            if (lettersFound>=T.length())
            {
                while(window[S.charAt(begin)-'A']>tProcessed[S.charAt(begin)-'A'])
                {
                    window[S.charAt(begin)-'A']--;
                    begin++;
                }
                if(end+1-begin<minWindow)
                {
                    startMinWindow = begin;
                    minWindow = end+1-begin;
                }
            }
            end++;
        }
        if (startMinWindow == -1)
            return "";
        return S.substring(startMinWindow,startMinWindow+minWindow);
    }
}

Leetcode: 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 character
b) Delete a character
c) Replace a character

Solution:

We can use dynamic programming storing in a matrix how many steps are needed to get from word1.substring(0,i) to word2.substring(0,j). Then the element i,j can be calculated as follows: 

$M(i,j) = min( M(i-1,j) +1, M(i,j-1) +1, M(i-1,j-1)+ C)$, 

where $C= \begin{cases}  0 & \text{if word1[i]==word2[j]} \\ 1 & \text{in other case}\end{cases}$.

public class Solution {

    public int minDistance(String word1, String word2) {

        if(word1.length()==0)

            return word2.length();

        if(word2.length()==0)

            return word1.length();

        int[][] steps = new int[word1.length()+1][word2.length()+1];

        for(int i=0; i<=word1.length(); i++)

            steps[i][0]=i;

        for(int j=0; j<=word2.length(); j++)

            steps[0][j]=j;

        for(int j=1; j<=word2.length(); j++)

        {

            for(int i=1; i<=word1.length(); i++)

            {

                steps[i][j] = steps[i-1][j]<steps[i][j-1] ? steps[i-1][j] +1 : steps[i][j-1]+1; //Adding a letter

                if(word1.charAt(i-1) == word2.charAt(j-1))

                    steps[i][j] = steps[i][j] > steps[i-1][j-1] ? steps[i-1][j-1] : steps[i][j];

                else

                    steps[i][j] = steps[i][j] > steps[i-1][j-1]+1 ? steps[i-1][j-1]+1 : steps[i][j];

            }

                

        }

        return steps[word1.length()][word2.length()];

    }

}

Leetcode: Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution:

public class Solution {
    public int numDistinct(String S, String T) {
        int[] numberOfSubsequences = new int[T.length()+1];
        numberOfSubsequences[0]=1;
        HashMap<Character,ArrayList<Integer>> positions = new HashMap<Character,ArrayList<Integer>>();
        for(int i=T.length()-1; i>=0; i--)
        {
            if (!positions.containsKey(T.charAt(i)))
                positions.put(T.charAt(i), new ArrayList<Integer>());
            positions.get(T.charAt(i)).add(i);
        }
        for(int i=0; i<S.length(); i++)
        {
            if(positions.containsKey(S.charAt(i)))
            {
                for(Integer pos: positions.get(S.charAt(i)))
                {
                    numberOfSubsequences[pos+1] += numberOfSubsequences[pos];
                }
            }
        }
        return numberOfSubsequences[T.length()];
    }
}

Leetcode: Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:

We use dynamic programming twice, first we obtain the matrix that indicates if an element is palindrome (cf. Palindrome Partioning I). Then, we calculate the minCut till the element i, as follows:

•  If isPalindrome(0,i) then minCut[i]=0
• else minCut[i] = min( minCut[j]+1 && isPalindrome(i,j))

public class Solution {
    public int minCut(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for(int length=0; length<s.length(); length++)
        {
            for(int start=0; start<s.length()-length; start++)
            {
                if(length==0)
                    isPalindrome[start][start] = true;
                else if(length==1)
                    isPalindrome[start][start+length] = s.charAt(start)==s.charAt(start+length);
                else
                    isPalindrome[start][start+length] = isPalindrome[start+1][start+length-1] && s.charAt(start)==s.charAt(start+length);
            }
        }
        
        int[] numberOfPalindromes = new int[s.length()];
        for(int i=0; i<s.length(); i++)
        {
            numberOfPalindromes[i] = isPalindrome[0][i] ? 0 : numberOfPalindromes[i-1]+1;
            for (int j=0; j<i; j++)
            {
                if(isPalindrome[j+1][i])
                    numberOfPalindromes[i] = Math.min(numberOfPalindromes[j]+1, numberOfPalindromes[i]);
            }
        }
        return numberOfPalindromes[s.length()-1];
    }
}