[More] Intersection of Two Linked List

Problem

There are two singly linked lists in a system. By some programming error the end node of one of the linked list got linked into the second list, forming a inverted Y shaped list. Write a program to get the point where two linked list merge.

Image

Follow up:
Given two lists, determine if they are intersected ? In O(n) time and O(1) space, and do it in one iteration.

Algorithm

Let L1 = length of list 1, and L2 = length of list 2. Let L = min(L1, L2). Start from Lth last node of list 1 and list 2, compare each node. If node 1 == node 2, it is the first intersection of two lists. 

Code

[Leetcode] Binary Tree Maximum Path Sum

Problem

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Algorithm

Use a helper class PathSum with two fields to store the intermediate result. The startRoot stores the path sum start with root, and the crossRoot stores the path sum cross the root. Since the left subtree may have negative start wit root path sum, we need to compare it with zero when compute the max path sum start with root. 

Code

[Leetcode] Valid Number

Problem

Validate if a given string is numeric. Some examples:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Algorithm

A valid number can contain, 0 ~ 9, at most one sign "+" or "-", at most one "." and at most "e" or "E". 

Some rules

• No "." after e
• "." must be adjacent to at least one number

[Leetcode] Binary Tree Zigzag Level Order Traversal

Problem

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

Compare this problem with iterative solution of Symmetric Tree.

Code

[Leetcode] Tree Preorder, In-order and Postorder Traversal

Problem

Given a binary tree, return the preorder, in order and postorder traversal of its nodes' values.
Note: Recursive solution is trivial, could you do it iteratively ?

Algorithm

Recursive solution is easy. 

Iterative solution can be treated in a same format.

Code

[Leetcode] ZigZag Conversion

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Algorithm

Using an array of StringBuilders to build each row. For odd column, sequentially append each letter from s to each row's string builder. For even column, do this reversely, and omit the last and first row. 

Code

[Leetcode] Word Search

Problem

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.

Algorithm

A simple DFS algorithm works. Use a 2D visited array to record those visited letters. 

I misunderstood the question for a long time.
"adjacent" cells are those horizontally or vertically neighboring"
For a 3*3 array, element [0,0] is not a neighbor of element [0,2]. Why I made it so completed !

Code

[Leetcode] Word Ladder II

Problem

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) 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"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Algorithm

The shorted transformation sequences might be more than 1, but they all have the same length to start word.

Build a hash map <key, value> = <String, List<String>> , where List<String> is the transformation sequence from start to key. 

Put start and the path to start to the map. 

For each word in curLevel curStr

     For each transformed word nextStr

          if(nextStr in dict) 

               if(nextStr Not in map)

                       put<nextStr, path to nextStr> to map

               else

                       update nextStr' path

Above algorithm can pass small test case in OJ of Leetcode. However, it gets Time Exceed Limit for large test cases. 

         

Consider a path from start to end, for each intermediate word, we stored a sequence. Therefore, we used O(n^2) space to store the sequence in this path. There are many paths when we do BFS, so we waste a lot time to create and update the sequences. 

Previous Pointer

A path from start to end can be represented by previous pointers. Since there might be many path to end, we need an array of previous pointers for each word. Create a Node class, which has a label to store the word it represents, and an array of Nodes to store its previous pointers. The main structure of the code is the same as above, except for we update the previous pointers instead of the sequence of strings. 

Code

WordLadderII_Test cannot pass large dataset, resulting in TEL. 

[Leetcode] Word Ladder

Problem

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.

Algorithm

1. 

At first glance, we can build a graph and use BFS to solve this problem. 

• Each node has a label, indicating the word it represents, and a distance to the source (start) word. We can iterate the dict in O(n) time to create O(n) nodes. 
• For each pair of node u and v, if their words only differed by one character, they are connected, i.e. there is an edge between them. Building the edges takes O(n^2) time. 

Then, we start from the source node, doing BFS until found the destination node. The BFS takes O(n) time. So, the total algorithm takes O(n^2) time, limited by the graph construction. 

Why not DFS ? Since DFS may search very deep in the wrong direction, while the shortest distance to in another direction and 1 step away from the source word. 

2. 

Normally, the dictionary has very large size. Therefore, the construction of graph is very time consuming. 

Observation 1: Each letter of an English words only has 26 choices,

Observation 2: Assume the length of the source word is K, there are 26*k transformations of a word. For n words in the dict, there are O(26 * k * n) transformations. 

Since the average length of English words is constant, there are only O(n) transformations for all words in the given dict. 

Build a hash map <key, value> = <word, distance>

Start from source word, 

Put <source, 0> to hash map. 

Put the source word to curLevel of BFS

while(current level is not empty && not found destination word){

         word = curLevel.remove()

         For each t = transformation of word
                 If t is destination
                    return word.distance + 1 

                 if(t is not visited)

                      put(t, word.distance + 1)            

}

Code

[Leetcode] Word Break II

Problem

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Algorithm

Subproblem structure: 

Let result[i] be the all possible solutions to break the s.substring(0, i). 

                                   result[i] = result[j] + s.substring(j,i), for all s.substring(j,i) in dict. 

For some extreme cases provided by the OJ of Leetcode, the algorithm above will exceed time limit. 

For example, s = "aaaaaaaaab", dict = ["a","aa"]. 

In this case, we can quickly determine whether it is breakable in O(n^2) using DP in Word Break I. If it is breakable then build the result. 

Code

[Leetcode] Word Break

Problem

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Algorithm

Let dp[i] indicates whether s.substring(0,i) can be separated. For the s.substring(0,i), it can be broke at position j, such that s.substring(j,i) is a word in the dictionary, 0 <= j < i. We have the recurrence

                                     dp[i] = OR(dp[j] And s.substring(j,i) is in dict), 0 <= j < i.

Code

[Leetcode] Valid Parentheses

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Algorithm

Maintain a stack, and push all left parentheses into the stack. Whenever see a right parentheses, peek the top element of the stack. If they does not match, return false. Finally, if the stack is not empty, return false. Remember to check empty stack before peek.

Code

[Leetcode] Validate Binary Search Tree

Problem

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.

Algorithm

Pass the [min,  max] range that the tree should fall in from root to each node. If any node falls out of the passed range, return false. Else return true. 

Code

[Leetcode] Valid Palindrome

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note: have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

Algorithm

s.toLowerCase() first to ignore cases. 

Write a helping method isAlphaNumeric to reduce code. 

Write two helping methods to find the next and previous alphanumeric character's index, which is easier to read. 

Code

[Leetcode] Unique Path

Problem

1.  A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

2. Follow up, 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. The total number of unique paths is 2.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

Algorithm

Dynamical Programming

Let dp[i][j] be the number of ways to reach A[i][j]. 

dp[i][j]  =  0                               if A[i][j] is blocked

                  d[i-1][j] + dp[i][j-1], if no blocks

             

Code

[Leetcode] Unique Binary Search Trees II

Problem

Given 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

Code

[Leetcode] Unique Binary Search Trees

Problem

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

Algorithm

Recursive

Given values from L to R, we can select K as the root. Then recursively solve the subproblems L to K-1, and K+1 to R, K goes from L(inclusive) to R (inclusive). 

        Number of subtrees rooted with K = Number of left subtrees * Number of right subtrees. 

Sum over all. 

DP 

We can use DP to solve this problem. Note the number of unique trees only depends on the number of  values available. For example, BST containing values [1,2,3] has the same number of unique trees as BST containing values [4,5,6]. Let dp[i] be the number of unique trees using i values. dp[0] = 1, dp[1] = 1. Using one value as the root, we have (i-1) options to distribute the rest (i-1) values to left subtree and right subtree. Let k = number of values distributed to left subtree, and k can goes from 0 to i-1. 

Code

[Leetcode] Triangle

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Algorithm

Let dp[i][j] be the minimal path sum to element j in level i. 

dp[i][j] = min(dp[i-1][j],dp[i-1][j+1]) + A[i][j].

Since computing each level only needs the result of previous level, we can reduce the  space to O(n).

Code

[Leetcode] Trapping Rain Water

Problem

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.

This Figure comes from Leetcode.

Algorithm

At any location in A, the trapped water has a water level, i.e. the height of the water. The water level is determined by the left bar and the right bar, whichever is shorter. How to find the left bar and right bar for a given location ?

Left bar is the closest peak on its left side (wrong)

Counter Example
                                               A = [5, 0, 2, 1, 5],
where the left bar  of 1 is not 2, but 5.

Left bar is the highest bar on its left, and right bar is the highest bar on its right. 
With this rule in mind, we can easily devise a O(n^3) algorithm. For each location in the array, scan left to find the highest bar on left, and scan right to find the highest bar on right. Then compute the water trapped at this location.

We can do better by scan from left to right, and store the highest left bar so far. At each location, scan the right highest bar. This algorithm only needs O(n^2) time.

We can do even better, using the "Double-Scan" Technique. Using two arrays lBar[i] and rBar[i] to store the highest left bar and highest right bar on i's left and right, not including i itself. The scan can be done in O(n). Then we can easily compute the water trapped with another iteration. So the total running time is O(n).

This technique was used in the problem Candy and the following problem.

Given an array of integers A, return another array B, where B[i] = the product of all elements except A[i]. You cannot use divide operator.

Using two helper arrays, leftProduct and rightProduct. Scan from left to right, compute the left product so far, excluding the ith element. Then scan from right to left, compute the right product so far. Finally, multiply the two arrays at each location, which is the product excluding A[i].

Code

[Leetcode] Text Justification

Problem

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.

Algorithm

We need to pack as many words as possible in each, until 

                                                wordLength + (nWords-1) + word[end] > L

There are three types of lines:

• Only one word, append word then append enough spaces, e.g. "justification "
• Last line, append word + " " for each word, except for the last word, then append enough spaces, e.g. "justification. "
• Other lines more than one words, append word + x spaces except for the last word, then append the last word, e.g.  "example of text"

Code

[Leetcode] Symmetric Tree

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note: Bonus points if you could solve it both recursively and iteratively.

Algorithm

Recursive

A tree is symmetric, 

• if it is null, 
• else if it has not children
• else if root.left.val = root.right.val,  and both subtrees are symmetric

Iterative

If each level of the tree are symmetric, the tree is symmetric. 

Using the iterative level order traversal of tree algorithm, we can check if the tree is symmetric in each level. The curLevel  stores the nodes from left to right, as usual. While the curLevelRev stores the nodes from right to left, in reversed order. Each time, we remove the first node n of curLevel and the first node r of curLevelRev, where n and r form a pair of mirrored nodes.

• If they have different value, return false. 
• Else if they have asymmetric structure, return false
• Else, add n.left to curLevel, r.right to curLevelRev, if not null, add n.right to curLevel, r.left to curLevelRev, if not null. 

Code

[Leetcode] Swap Nodes in Pairs

Problem

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.

Code

[Leetcode] Surrounded Regions

Problem

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Algorithm

If an "O"  is on the boundary of board, we call it boundary "O". 

For an "O", if there is a path containing only "O" to a boundary "O", we call it "live" "O". 

If an "O" is not "live", it must be surrounded by "X", and we need to flip it. 

Consider the 2D matrix as a graph, where "O"s are nodes. Adjacent "O"s are connected. We can perform a BFS starting from each "O" on the boundary, to find all "live" "O"s. Once we found all "live" "O"s, the rest need to be flipped. 

Note, recursive DFS may result in stack overflow for large matrix.

Code

[Leetcode] Sum Root to Leaf Numbers

Problem

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Algorithm

Let pathNumber be a number represented by the path from root to current node. Since this node's value is the new least significant digit of this number 

                                        pathNumber = pathNumber*10 + cur.val. 

If current node is a leaf node, pathNumber is a root-to-leaf number. Adding all these root-to-leaf numbers, we get the final result. 

Code

[Leetcode] Sudoku Solver

Problem

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.

                             

Algorithm

Whenever we see a ".", guess a value from 1 to 9 and check if it violates the current row, column and sub-block. If it does not violate, guess next element. If all 9 numbers are tried and failed, this board cannot be solved. We need to roll back to previous position, therefore set current to be "." after iteration. 

Code

[Leetcode] Valid Sudoku

Problem

Determine if a Sudoku is valid, i.e. each row, column and 3*3 sub-block can only have one number from 1 to 9. 

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

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

Code

[LeetCode] Substring with Concatenation of All Words

Problem

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Algorithm

Use a hash table to count the occurrence of strings in list L. Scan S from left to right. Start from any index in S, if the substring S.substring(index, index + L.length()) is a concatenation of words in L, we are done. 

This problem is smilier to Longest Substring without Repeating Characters, which maintained a window and using a hash table to count the occurrence of characters. 

Code

[Leetcode] Subsets I and II

Problem

1. Given a set of distinct integers, S, return all possible subsets.

2. Given a collection of integers that might contain duplicates, S, return all possible subsets.

1. For example, if S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

2. For example, if S = [1,2,2], a solution is:

  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

Code