The Practice to Become Lazy -- Leave your work to subproblems

                         Leave your work to subproblems 

                                                                    --The idea of recursive approach  

  When I had entry level of data structure class in my freshman year, the most elegant and also somewhat mysterious way to write code is using recursive approach.  I still remember, we compared the iterative and the recursive way to reverse  a LinkedList and I was impressed by we could just use 4 line of code to solve this problem.  

     Well,  To appreciate, then understand what is really happened behind scenes, then able to create some recursive code , Finally, know when to use recursive code to solve problem, are 4 different levels that we may go through when we go deep into this interesting way to solve problems. Here are some practice that you may want to train yourself in order to get more clear picture of how recursive function works.  

     To sum up this idea : Lever your work to small problems -- be "Lazy". 

1. Reverse LinkedList 

   Reverse a singly-linked list.

Examples

• L = null, return null
• L = 1 -> null, return 1 -> null
• L = 1 -> 2 -> 3 -> null, return 3 -> 2 -> 1 -> null

--------------------------------------------------------

It is a very old fashion problem and we could certainly do it use iterative and recursive way. But what I am focus on right now is the pattern of ways that we can solve a problem using recursion. 

Here is a very helpful graph that can illustrate the idea:  

 

Before we reverse the LinkedList, we have Node 1 --> Node 2 .... --> Node n. 

-- For a recursive approach, we only need to take care of one base case, which is how to reverse the very first Node 1 , when we already have Node2 .... Node n already reversed. 

   So what we need to do ? 

   1. Let Node2  point to Node 1 

   2. Let Node1 point to Null 

   3. Return the newHead, which is the Node n. (we do not know which node is node n, but we could leave it to the subproblem. 

 After we figured out those 3 steps we need to do, we, therefore, could come up a elegant recursive code: 

Notice that we do not know which one will be return as newHead, so we leave the work for our subproblem which is the dotted line above. 

2.  Reverse LinkedList in Pairs 

Reverse pairs of elements in a singly-linked list.

Examples

• L = null, after reverse is null
• L = 1 -> null, after reverse is 1 -> null
• L = 1 -> 2 -> null, after reverse is 2 -> 1 -> null
• L = 1 -> 2 -> 3 -> null, after reverse is 2 -> 1 -> 3 -> null

---------------------------------------------------------------------------

Here we have a very little requirement change on original problem, but if you would like to try it in a iterative way, the code will become messy and lots of corner cases need to deal with. Here is a graph that could help us to visualize what we need to accomplish: 

So we only need to reverse Node 1 and Node 2  at current level, by assuming that we already down the job in dotted line box, and we will, again, leave that subproblem to further recursive call. That is the the whole idea of being "Lazy". 

  At current level we just need to : 

    1. Let Node 2 point to Node 1

    2. Let Node 1 point to the subproblem, which is the rest of reversed list 

    3. The newHead will be Node 2 in this case, so we return Node 2 as newHead. 

Just like what we said: 

With base case and return newHead, totally 5 line of code !  Can you believe that ^^ 

3.  How to get a deep copy of graph with possible cycles ?  

There are two ways to do this: 1. BFS copy graph, 2. DFS copy graph. 

The second way DFS is related to this "Lazy" topic, but we will also cover the BFS way also. 

------------------------------------------------------------------------------------------

Notice: We only actually cloned one node: 

      1. Create this clone of this node 

      2. Put this copy into graph 

      3. Add all its neighbors into neighbors list 

What about other node ? Well we leave it to our recursive call when add other neighbors in this node.

            

4 . Delete From Binary Search Tree 

Delete the target key K in the given binary search tree if the binary search tree contains K. Return the root of the binary search tree.

Find your own way to delete the node from the binary search tree, after deletion the binary search tree's property should be maintained.

Assumptions

• There are no duplicate keys in the binary search tree

The function signature is  :  Public TreeNode delete(TreeNode root, int key ) 

which will represent as the root of the subtree that already complete deleted the node that contains key. 

Notice we had three recursive call when : 

 1. current node.key < key 

 2. current node.key > key 

 3. when node.key  == key 

You may find various code to delete a node in BST, but this way is the most elegant one that I found. 

One more last thing: Notice that if this node have two child, we cloud substitute this node with its min node on right sub-tree or the max node in left sub-tree. In this code we find the min in its right sub-tree to do it. 

Hope you enjoyed ! 

Happy Coding ^^ 

Ye Jiang  

Choosing a suitable Data Structure to solve Problems

               Choosing Suitable Data Structures

        Most problems we encountered so far are about to manipulate data and , then, find some  special values. Sometimes a suitable data structure can greatly help us to simplify a problem. For example if your algorithm is a greedy algorithm and want to have the same performance as a recursive function, then you may want to use a stack. If you would like to check weather a given value is already in your data structure, you may want to use hash map to improve your contains query

..etc.

       Here are few great examples that can show the power of various data structures :)

1.  Letter Combinations of a Photo Number

--------------------------------------------------------------------------------------------------------------------------

Analyze: It looks like a easy question that you just want to have some nested loops to get the final results. However do you know how many loop you will have ?  Cause the input size will change, so the nested loop approach will not gonna work.  However, a good data structure like queue can help us to achieve the same goal. 

 

 2.  Flatten Nested List Iterator 

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Given the list [1,[4,[6]]],

 * // This is the interface that allows for creating nested lists.

 * // You should not implement it, or speculate about its implementation

 * public interface NestedInteger {

 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.

 *     public boolean isInteger();

 *     // @return the single integer that this NestedInteger holds, if it holds a single integer

 *     // Return null if this NestedInteger holds a nested list

 *     public Integer getInteger();

 *     // @return the nested list that this NestedInteger holds, if it holds a nested list

 *     // Return null if this NestedInteger holds a single integer

 *     public List<NestedInteger> getList();

-----------------------------------------------------------------------------------------------------------------------------------------------

Analyze: Many people do not know how to approach this problem at the first time. However,
 if you are not constrained by programming language, how will you approach this problem in general ?
 You may say something like " Keep iterating through the input, until we find the first integer. 
Then put it into output list ". That is very good intuitive idea. So what kind of technique you may use
 to implement that idea ?   Keep doing....  Until.. gives me strong feeling about greedy algorithms
and the perfect data structure for a greedy algorithm will be a stack ^^ . 

Notice that we have a stack and a reference called nextInt that will store the next Integer object in

nested list. 

3. K-th Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

-------------------------------------------------------------------

Discuss: Using PriorityQueue -- a min heap,  is a very easy solution that you may come up with. So 
we have a working solution which is push all the elements into priorityQueue, then do pop out k times.
What will be the Time and Space complexity ?  Time : O( K * log(mn))  .  Space( k ). 

Actually we could do better !  Here is a way ( so called , Best First Search) that can do it in Time: K * log(k). 

Here is the Java solution:
Notice that we only do (k-1) times poll operation on minHeap, then peek the top element value.

The simple Cell class we used above:


Note: the motivation we use Cell class is we want to know not only what is next min value, we also
interested about where this min come from.

Hope it helps.
Happy Coding ^^
4/12/2017
Ye Jiang