LeetCode Q89: Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Rnd3 Sol:
No extra space used. Based on an observation that if two adjacent numbers are different by only 1 bit, than adding 1 to same 0 bit position of the two numbers should result in gray code too.

LeetCode Q86: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

LeetCode Q85: Maximal Rectangle (hard)

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area

The idea is to scan the matrix row by row. In this row, we calculate a histogram of 1's that are directly continuously above the row. Then we could solve the maximal area of histogram using  "Largest Rectangle in Histogram". Then entire algorithm takes O(n^2) time.

LeetCode Q84: 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.

Solution 1: O(N^2)


Solution 2: Divide and Conque
Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (not include min value)
b) Maximum area in right side of minimum value (not include min value)
c) Number of bars multiplied by minimum value.


Solution 3: Using stack

For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively.

We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.

Round 2 solution:

LeetCode Q83: 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.

Round 2 solution:

LeetCode Q82: 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.

Solution 1 (Non-recursive)

Compare value of current node and next node. Be careful to check if next node is NULL ahead. Also, be careful of some corner case such as:

[1, 1, 2]: Need to create a new head  node in front of the first node.

[1, 1]: Need to create a new head  node in front of the first node.

[1]: Need to create a new head  node in front of the first node.

[1, 2, 2, 3, 3]: when duplicate numbers are one after another, need to double check whether the first non identical number is a new start of next group of duplicate numbers.

Round 2 solution:

LeetCode Q81: 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?

Write a function to determine if a given target is in the array.

LeetCode Q78: Subsets *

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

Note:

• Elements in a subset must be in non-descending order.
• 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],
  []
]

Solution 1:

Solution 2
Solution 3 (recursion)
Solution 4 (Bit manipulation)

Round 2 solution:
Idea is simple, similar to Q77, don't wait until the last to save the result, instead we save intermediate results in every recursion.

LeetCode Q79: 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.


Solution:
My solution is very conventional that I use two array to track which entries are already on the path and how many neighbors (up, down, left, right) are already accessed.




Round 2 solution:

LeetCode Q77: 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],
]

Solution 1: Recusion

Solution 2: Non-recursion
Round 2 solution

LeetCode Q76: Minimum Window Substring (hard*)

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.

This is a typical "substring" problem. People gave many beautiful solutions. 

Solution 1

1. Initialize a vector called remaining, which contains the needed matching numbers of each character in s.
2. If there are still characters needed to be contained (increment i in this case), decrease the matching number of that character and check if it is still non-negative. If it is, then it is the character in t, so decrease the total required number required.
3. If there is no more characters required (increment start in this case), record min andleft if a smaller length is found. Recover the number of this character in the remainingand if it is a character in t increase required.

Solution 2 (Similar to solution 1, but more concise.)
Template that can solve almost all substring problems
The code of solving Longest Substring with At Most Two Distinct Characters is below:
The code of solving Longest Substring Without Repeating Characters is below:

LeetCode Q75: 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.

click to show follow up.

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?

There are four difference solutions, thanks for shichaotan's post on LeetCode:

LeetCode Q74: 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.

Solution 1:
Binary search, but at the end, you need to search two rows before making a decision. Time complexity O(logm + logn).

Solution 2:
Start from up right corner, if larger than move down, if smaller than move left. Time complexity O(m+n)

LeetCode Q73: Set Matrix Zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

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?

Solution:

Use first row and column to save rows and cols having zeros. But need to check whether the first row and first column initially containing zeros. When filling the matrix, starting from the second row and second column. When finish, back to fill the first row and the first column if they initially contain any zero.

LeetCode Q72: Edit Distance (hard)

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

A classic DP problem.

Suppose DP[ i ][ j ] save the steps needed by converting word1[ 0 : i ] to word2[ 0 : j ]. Let's consider the very last step needed before word1[ 0 : i ] can be converted to word2[ 0 : j ].

If the step is DELETE, means word1[ 0 : i-1 ] = word2[ 0 : j ]. Thus DP[ i ][ j ] = DP[ i -1 ][ j ] + 1.

If the step is INSERT,  means word1[ 0 : i ] = word2[ 0 : j-1]. Thus DP[ i ][ j ] = DP[ i ][ j-1 ] + 1.

if the step is REPLACE, there could be two possibilities.

    First, if word1[ i ] = word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ].

    Second, if word[ i ] != word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ] + 1.

So, by taking minimum of these three possibilities, we get the value of DP[ i ][ j ].

To, initialize the boundary case, from above examples we know, to get DP[ i ][ j ], we basically, need to solve the values on it up left, left, and up. So, we only need to initialize the first row and the first column of the table DP. 

LeetCode Q71: Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"







LeetCode Q69: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Easy question at the first glimpse, however, some corner cases can stop you for a long time. Apparently, should solve it using binary search. However, need to change a bit in a few places than normal binary search. For example, in following code, from line 4 -- line 9, we don't wait until l>=h to stop recursion, because, in that case, we may miss a few right solutions. Also, in line 17 and line 19, we don't increase low bound by one or decrease upper bound by one to ensure the middle position is still included in the next recursion. 

Round 2 solution:
Using Newton's method, for details, refer to this post:

LeetCode Q65: Valid Number (hard)

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.

My solution is tedious, and I consider three possibilities separately.

A relatively simple solution is given by someone's post on LeetCode's forum:

LeetCode Q64: 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.

Round 2 solution:

LeetCode Q63: 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.

LeetCode Q62: 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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Recursion, memoization.

LeetCode Q61: 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.

LeetCode Q60: 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.

    I didn't end up with this solution myself again, sigh... But, my idea is almost there as similar as the code I show below. The idea is not to do the swapping or insertion to the string. Instead, we can directly "compute" the string by looking at how many permutations are available for each given number n. Say, if n=4, and in total it will give 24 permutations, and we are going to pick the k=10 string. To decide which number we should use for the most significant bit, we should look at how many permutations are there for digits that are after the most significant digit. In this example, there 3 digits after the most significant one, and with 3 digits, there will be 6 possible permutations. So, we know the significant digit can not be 1, because there are only 6 possible string in form of 1XXX. Thus, the most signification digit has to be 2, because, 2XXX has another groups of 6 permutations which must contain our target one.

    So on so forth,  we can compute the digit from significant digit to least significant digit.

LeetCode Q58: 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.

For example,
Given s = "Hello World",
return 5.

Straightforward solution, just take care of continuous training empty signs.

Round 2 Solution:

LeetCode Q57: 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].

One consideration is, the i-place method maybe slower than using extra space for the new vector. So I create a new vector res for result returned.

Linear scan, and keep updating newInterval until intervals[i].start is larger than newInterval.end.

LeetCode Q54: 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].

LeetCode Q56: 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].

Nothing hard, but need to be careful when using vector::erase.

For example, when erase elements from i to j in A. 

When j>i, to remove [A[i], A[j]]:

erase(a.begin()+i, a.begin()+j+1)

because, erase(A.begin()+i, A.begin()+j), actually only remove [i, j) from A.

When j==i, to remove A[i]:

erase(A.begin()+i)

Round 2 solution:

LeetCode Q55: 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.

Different than Jump game II, this one only need to determine whether can reach the end. The situation where it can not reach the end is because all jumps stops at some cell with 0 possible steps. I use linear scan to solve the question. During scanning, keep updating the furthest  position can reach. Return false when the furthest position stop updating.

Round 2 Solution:
Check whether current location can be reached by previous steps.

Calculating the output size of each layer in CNN based on filter parameter

A general formula for this is:

(D+2P-F)/S +1

where D is the input size of one dimension (assuming the input is a D by D matrix), P is the padding, F is the filter size, and S is the stride. Padding is extra pixels outside each side of boundary, stride is the number of pixels skips by filter when scanning the image.

LeetCode Q53: 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.

A neater solution:



Round 2 solution:
This solution will take into account a case where all numbers are negative.

An overview of gradient descent optimization algorithms

Recently, a post that summarize almost every gradient descent optimization algorithms used in deep neural network has been created by Sebastian Ruder at:
http://sebastianruder.com/optimizing-gradient-descent/
Thanks for his effort, it is helpful.

LeetCode Q49: 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"]
]

Use sort and hash. The key used in hash is in format C1X1C2X2... where C is a character, X is the number of C showing up in the string.

LeetCode Q50: Pow(x, n)

Iplement pow(x, n)

Easy question can sometimes be very hard and this question is typically belongs to this family. x is integer, n is double. As usual, you should come up with an idea of solving it using recursion. Further, you may want to use memoization when you aware your solution can hardly finish running itself in required time. By this point, I tried to use vector to record the value of every possible pow(x, n) for n starting from 1 to n. However, this fails when n is very very large, say INT_MAX. Because the size is excess the maximum size that is allowed to allocate memory for vector. So, looks like we have to dynamically allocate memory for each subsolution which leads to an idea of using unordered_map and BOOM~, we are done.

Round 2 Solution: Be careful of negative power and overflow. I am also suppressed by how much I improve my code by comparing this solution with my previous one. Practice makes perfect!!!