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