[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]Combination Sum II

Analysis 

• DFS

Note

Code

[Leetcode Solution]Combination Sum

Analysis 

• DFS

Note

Code

[Leetcode Solution] Permutations II

Analysis 

• Instead of treating duplicates as different elements, treat them as the same element with different number
• Then each element is not at the state of used or not used. Instead, it is how many times can be still used.

Note

Code

[Leetcode Solution]Permutations

Analysis 

• Depth first search

Note

Code

[Leetcode Solution] N-Queens II

Analysis 

Note

Code

[Leetcode Solution]N-Queens

Analysis 

The problem itself is simply just using a dfs could get the result

Note

•  The interesting thing happened from the valid check part. It is about the C++ data type conversion of unsigned int, details can be found here

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Sqrt(x)

Analysis 

• Use binary search to find the square root

Note

• Just like calculate the average of two integer, it should use mid = low + (high - low)/2
• because of needing calculating mid * mid, mid should be defined as long long
• Each calculation must consider the overflow

Code

UPDATED AT 2ND PASS

[Leetcode Solution] Search a 2D Matrix

Analysis 

• Use binary search two times. First search the right row and second search the right column
• Search for the biggest element that smaller then target
• Search the exact element equals to target

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Word Search

Analysis

• Iterate each node in the matrix to do the DFS and find if the word exist

Note

Code

[Leetcode Solution] Search in Rotated Sorted Array II

Analysis

• Almost the same as Search in Rotated Sorted Array
• The only difference resulting from the duplicates is we cannot judge if a sequence is rotated by compare the first and last element of the sequence.
• So the solution is when the first and last elements are the same, we just move backward of the first index, and do recursively.
• So the complexity of the worst case is O(n) now 

Note

Code

[Leetcode Solution] Search in Rotated Sorted Array

Analysis

• Pretty interesting a problem 
• Binary search is still available however modification should be added when update the edge at the recursion timing.
• There are several conditions needed to be handled separately (Let st,ed,mid denote the start, end and mid index)
• If target = A[mid], find it
• If A[st] <= A[ed], this is a ordered sequence
• if target < A[mid], ed=mid-1;
• if target > A[mid], st=mid+1;
• If A[st] > A[ed] means this is a rotated sequence
• If A[st] < A[mid], all of the first half sequence is the bigger part
• If target < A[mid], there are two sub-sequence might contain the target because the first half is the bigger one
• If target < A[st], st=mid+1
• If target > A[st], ed=mid-1
• If target > A[mid], st=mid+1;
• If A[st] > A[mid] means that although the sequence is rotated into two part, but the mid element is belong to the original smaller part
• If target < A[mid], ed=mid-1
• If target > A[mid], there are two sub-sequence might contain the target because the first half is the bigger one
• If target < A[ed], st=mid+1;
• if target > A[ed], ed=mid-1

Note

• Dealing with the binary search, decision whether to use < or <=, > or >= must be very very careful. Like in the termination condition while sentence and condition if sentence. The condition of two variables are equal mush be considered and decide whether to use =.

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Subsets II

Analysis

• Two methods applied both of which are pretty straightforward
• (1) Sort the original array and extract a new array without duplicates but count the number of each element. Then use DFS all possible subset and in each search step, iterate to insert the current element from 0 times to the number of that element times.
• (2) Sort the original array and extract a new array without duplicates but count the number of each element. Generate the possible subsets iteratively. At each step, copy all of the previous generated results and insert the current element at the end of each results
• Seems that iterative way should faster then recursive way however the running results are opposite.

Note

Code

DFS

Iteration

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Binary Tree Inorder Traversal

Analysis

• It's pretty simply by using recursive way to do in-order traversal of the binary tree
• There are two ways to do it iteratively
• First, using a stack dfs with a state variable for each node to indicate if the left child has been visited. If it is ,then visit this node and then visit the right child sub tree. Else if the left child sub tree has not been visited, set the state variable as visited, and then visit left child sub tree first
• Second traversal iteratively with constant space by using Morris in-order traversal which is a pretty tricky solution. It maintains the traversal order by delicate modify the tree and recover the tree back after traverse. The details can be found here

Note

• If using a stack to store the traversal sequence of DFS, attention should be paid if the back of stack if frequently modified. Because after pop_back or push_back, the stack.back() might not the ones you expected

Code

[Leetcode Solution] Validate Binary Search Tree

Analysis

• Idea is straightforward by using the property that inorder traversal of binary search tree is an ascending sequence 

Note

• Attention should be paid that when we use INT_MIN as the smallest element as s specific value, some element in the input might be INT_MIN

Code

[Leetcode Solution] Recover Binary Search Tree

GOOD PROBLEM

Analysis

• A inorder traversal of binary search tree results into a ascending order sequence
• Thus a solution using O(n)space is straightforward. By performing inorder traversal and getting the ascending order sequence, it would be quite easy to find out the swapped elements
• A solution using constant space is quite tricky because whether using recursion, the normal inorder traversal needs at least O(logn) space to store the searching status
• The trick is constant inorder traversal found here call Morris In-order Traversal using Threading
• After having constant space traversal method, we check each element while traversal if it is in a correct ascending order
• Another trick is how to deal with the situation that the swapped two elements are adjacent ones

Note

• In-order traversal binary tree in constant space

Code

[Leetcode Solution] Symmetric Tree

Analysis

• Using BFS search each layer of binary tree from the root to leaf 
• Validate if elements in each layer is symmetric
• If all the layers are symmetric, then so is the tree

Note

Code