[Leetcode Solution] Remove Nth Node From End of List

[Leetcode Solution] Divide Two Integers

[Leetcode Solution] Sudoku Solver

[Leetcode Solution] Find Minimum in Rotated Sorted Array I && II

It's pretty straightforward that this is a binary search problem.

The key part of binary search is how to decrease the searching scale. There are two types of scale down strategy based on the different scale down factor.

Let find(num,x,p,q) denote that find the target x in the range from num[p] to num[q]. Thus the first step we need to make sure is that whether target is located within this range. An important point needed to mind is that (p,q) denotes the target is located in range (p,q) inclusively and thus each step we decrease the range, the statement that the target is located in the range is always held.

Two things about binary search

1. Terminate condition
2. How to decrease range

Based on different types of above method, two types of implementation emerged.

1. Find out the mid element. Decrease the range (p,q) to (p,mid) or (mid,q). Thus the problem is that  the procedure might be endless because p could be always not equal to q. Hence the terminate condition is that (if p==mid) return the target which is the case that p==q or p==q-1
2. Find out the mid element. Decrease the range (p,q) to (p,mid-1) or (mid+1,q). This can make sure  that binary search procedure will sure terminate by p==q. However the thing needed to do for this method is that you must make sure if mid is the target because each time of decrease range you always eliminate the mid from next searching range.

Now let's consider the Problem "Find Minimum in Rotated Sorted Array"

1. Use first type of binary search
2. Use second type of binary search

Now let's consider the Problem  "Find Minimum in Rotated Sorted Array II"

Because duplicated elements exist. Thus it is hard to check whether mid element is the target. So we can use the first method to implement the binary search easilier.

[Leetcode Solution] Path Sum

[Leetcode Solution] Path Sum II

[Leetcode Solution] Flatten Binary Tree to Linked List

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Populating Next Right Pointers in Each Node

[Leetcod Solution] Pascal's Triangle II .cpp

[Leetcode Solution] Triangle

[Leetcode Solution] Valid Palindrome

[Leetcode Solution] Maximum Product Subarray

Analysis 

• First idea came in mind is dynamic programming which would be fine if it is required to calculate the maximum sum subarray. However after short thinking it's easy to find out this is a greedy algorithm 
• Assume there is no Zero in the array, we can divide the problem into two sub problems
• If the number of negative elements in the array is even, the maximum product is multiple all the elements together
• If the number of negative elements in the array is odd, we calculate the two products of elements in which the first is from left to the last negative element and the second is from the first negative element to the last element. Then return the bigger one.
• Take zero element into consideration. If we multiple zero into product, the result is always equals to zero. So the solution is divide original array into multiple subarrays delimited by the zero. Then calculate the maximum product within each sub array. Last return the biggest one.

Note

Divide an array by given delimiter and perform calculation on each sub array. Code Template can be found here 
http://fmarss.blogspot.com/2014/10/divide-array-into-sub-arrays.html 

Code

[Leetcode Solution] Merge k Sorted Lists

Analysis 

• This is a problem not hard but interesting. Here we go and have a look.
• In order to merge k sort lists, there are many solutions.Time complexity analysed based on a simplified situation that that are n lists and each of them contains m elements.
• The first one came into mind is do it just like how to merge two lists in the merge sort. Each time compare the current element of all the lists. Find out the smallest one and insert it into result list. However this solution could be really slow because it is O(m^(n*m)) time complexity.
• Another solution is each time merge two lists, and then merge the result list with another one until no list. If so the time complexity is O(n*n*m). However if use binary merge that first we merge all the original lists into n/2 lists and then merge these n/2 lists into n/4 and so forth until only one list left. This could be more efficient.
• One straightforward solution is just store all the elements in a vector, and then sort them. It's simple but works with O((n*m)*log(n*m)).
• A good solution in theoretical perspective is that we can maintain a priority queue with m elements. Each time we pop up the smallest element in the priority queue in O(1) time and then push in the element which is the next node of the popped one in O(log(m)) time. The overall time complexity is O((n*m)*log(m)). It should be faster then the above algorithm however in fact it is a little slower then the above one which may because it has a bigger coefficient.

Note 

• The signature of priority_queue constructor in C++ STL found here

• The difference between comparison parameter for priority_queue and for sort found here

• operator () found here
• const qualifier found here

Code

[Leetcode Solution] Swap Nodes in Pairs

Analysis 

• Each time swap the following two nodes

Note

Code

[Leetcode Solution] Reverse Nodes in k-Group

Analysis 

• Each time reverse one group of nodes
• Use pre_last denote the last node of previous group
• Use cur_first denote the first node of current group
• Each time after reversing, make pre_last->next=cur_first
• Adding a auxiliary node ahead of the head to avoid the specific situation of the first node

Note

Code

[Leetcode Solution] Remove Duplicates from Sorted Array

Analysis 

• 
  

Note

Code

[Leetcode Solution] Remove Element

Analysis 

• Use two pointers. One points to the current element. The other points to the current position where to store the next unique element.

Note

Code

[Leetcode Solution] Implement strStr()

Analysis 

• 
  

Note

Code

[Leetcode Solution] Substring with Concatenation of All Words

Analysis 

• Brutal force search

Note

Code

[Leetcode Solution] Next Permutation

Analysis 

Let's consider a simpler situation. Given n integers [1..n] and a permutation generated by these n integers. How to find the next permutation.

It seems easy right. If we treat the permutation as a integer number, our purpose is to increase value of this number to the nearest one by reorder the integers.

Say the permutation is like this [a(1),a(2),...,a(n)]. if i<j and a(i) < a(j). If we swap ai and aj the value of permutation will increase. In order to get the nearest bigger number, we would like to increase a bit in least significant bit by swap it with a bit at more least significant direction. So the solution is find the first a(i) that there is an a(j) that a(i) < a(j) and i<j. After that we swap the value of a(i) and a(j) then resort the integers from a(i+1) to a(n) in order to change it to the smallest one.

Now consider the given scenario. There are different integers in the permutation and duplicates.

• First we can just treat different integers as the sequence of 1 .. n because they share the same order. Only order makes a difference rather then the value.
• Second if duplicates exist, we will only update the part which finds the first a(i).

Note

Code