Understanding DFS Recursion Tree ( 1 )

           All Valid Subsets & Permutation & Parentheses 

                                                                                                   

  There are some questions will require you to list all possible subsets of certain characters, or all permutations of some random number. It seems very hard to deal with it when the characters or numbers are in a large scale. For example if let you find all subsets of "ABC", the answer set will only contain 2^3 = 8 elements. However if it become "ABCDEFGHIG" , then we will have 2^10 = 1024 elements in our result set, which is almost impossible to do it manually. That is why this kind of question become very interesting. As a software engineer, we need be able to let computer to do this tedious work for us and it will do it quick & without any mistake. Besides, more importantly, after we write some recursive code, we need to understand how the recursive tree will look like. It is , indeed, a part of the charming of programming. 

-- All Subsets 1 

Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

• There are no duplicate characters in the original set.

​Examples

• Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]
• Set = "", all the subsets are [""]
• Set = null, all the subsets are []

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

We could use backtrack algorithm( we actually discussed this algorithm before ) to solve this easily. 

Here is a solution in JAVA: 

Note, if this backing code is somewhat mysterious to you, then you may want to use pen and paper to draw some call stacks of a simple example like "abc", which will help you to understand what is going on under the hood. ( Here some call stacks I traced ) 

1. Base case determines recursive tree's height 

2. # of times it call itself  in the method body determines the branch factor 

-- All Subsets 2 

How about a almost identical problem with possible duplication of letters ?
 Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

• There could be duplicate characters in the original set.

​Examples

• Set = "abc", all the subsets are ["", "a", "ab", "abc", "ac", "b", "bc", "c"]
• Set = "abb", all the subsets are ["", "a", "ab", "abb", "b", "bb"]
• Set = "", all the subsets are [""]
• Set = null, all the subsets are []

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

Well since it is almost identical to the subsets 1, except it may contains some duplicate letters, so only thing we need to add into the solution of the first one is de-duplication steps. 

We added line 9 --> Let same character be in adjacent positions
                 line 22 --> After add this character into final solution we skip all the possible duplications

-- All Permutation 1

Given a string with no duplicate characters, return a list with all permutations of the characters.

Examples

• Set = “abc”, all permutations are [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]
• Set = "", all permutations are [""]
• Set = null, all permutations are []

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

Do you feel that all permutation problem is somewhat related to the all subsets problem ? 

Actually are related and we will use the same approach trying to solve it, but remember for all subsets problem we have 2^N cases, which means for any random letter we either add into final solution, or not. 

However, for all permutation problem we will have N * (N-1) * (N-2)* ... *1 = N! cases. 

Here is a working solution in JAVA: 

Notes: the for loop from 17 - 20 was full of mysterious to me at the beginning 

What it will do is start from a position and swap every upcoming position with this one. 

Here are some call stacks. 

--All Permutation 2

So what we gonna do when there are some duplicate letters  -_-   ?

Again we need to de-duplication and the way we do is to keep a set for every branch, and do not swap with a upcoming letter if we already meat it before ( swap two same letter will make no difference in the result ). 



Line 16 and 18 will do the de-duplication job.

-- All Parentheses 1

Given N pairs of parentheses “()”, return a list with all the valid permutations.

Assumptions

• N >= 0

Examples

• N = 1, all valid permutations are ["()"]
• N = 3, all valid permutations are ["((()))", "(()())", "(())()", "()(())", "()()()"]
• N = 0, all valid permutations are [""]

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

You actually can consider this question as follows: suppose you have k parentheses to use, which means the string length will be 2k ( k left paren + k right paren ). Then suppose you have a 2k length char array, for every position you may have 2 choose : either put '('  or ')'. But wait a second, do we really have 2 choose for every position ?  Definitely not, for example the very first position can not put a ')'. So that is a important point  that this question need to consider.



As you can see from the comment, when considering what to add at current position(index) 
there are 2 possible cases
1. if we still have left paren left, then we could add left paren 
2. if left paren is used more then right paren then we could add right paren at this position. 

if we consider how this recursive tree will look like , First, we will have a 6 level tree ( height is determined by the base case), and for each level, if not considering cutting any branch out, will have 2 branches. Therefore, Time complexity  --> O(2^6) , Space Complexity --> O(6) 


There will be another blog concerning the understanding the recursive tree coming, I hope we all enjoy it.

Happy Coding :-)
Ye Jiang

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 

Substring Problems

                                 SubString Problems 

-- Overview 

    This substring topic is very related to two pointer technique, which is also a topic that may need to utilize sliding window problem. So Let's dive in those problem and, hopefully, get comfortable with many examples.

-- Examples 

1. Determine If One String Is Another's Substring 

Determine if a small string is a substring of another large string.

Return the index of the first occurrence of the small string in the large string.

Return -1 if the small string is not a substring of the large string.

Assumptions

• Both large and small are not null
• If small is empty string, return 0

Examples

• “ab” is a substring of “bcabc”, return 2
• “bcd” is not a substring of “bcabc”, return -1
• "" is substring of "abc", return 0

Note: two loop with 3 base cases: 
        1. if we reach the end of needle, then return the index in big string. 
        2. if we reach the end of big string, but still not find any match, we return -1, meaning not exist. 
        3. Else we check the current position to big, and small string, see if we have a match, if not we break this inner loop. 

2.  Longest Substring Without Repeating Characters

Given a string, find the longest substring without any repeating characters and return the length of it. The input string is guaranteed to be not null.

For example, the longest substring without repeating letters for "bcdfbd" is "bcdf", we should return 4 in this case.

Note: It is a typical, classic, Sliding window algorithm applied to a subString problem. 

3.1 : Longest SubString with at most 2 distinct 

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Note: If you really understand example 2, and this 3.1 example, you may find out that the only difference of this two problem, when we use sliding window algorithm to solve it, is how we move our start pointer to let the substring in our window size is a valid substring according to the question requirement. 

3.2 : Longest SubString with at most K distinct 

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

Note: Compare 3.1 and 3.2, we only need to change the condition when we should shrink our window. 

Also, notice from line 17 - 19, we only decrement the count of distinct value, if we gonna decrement on a value 1 char on our map, but for every char start pointer is passing, we do need to decrement its map value. 

4. Longest palindrome subString 

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Note: It is little abstract if you are not that familiar with DP, but here is a diagram to explain the man flow of the idea:

 


The read arrow in the cell means we will look the previous dp[i+1][j-1] to determine the value of this current cell. and if dp[i][j] = true,  means the substring start at index i, ends at index j , is a valid palindrome. 

5. Find all Anagrams in one String 

Find all occurrence of anagrams of a given string s in a given string l. Return the list of starting indices.

Assumptions

• s is not null or empty.
• l is not null.

Examples

• l = "abcbac", s = "ab", return [0, 3] since the substring with length 2 starting from index 0/3 are all anagrams of "ab" ("ab", "ba").

Note:In this problem, we keep our window size = s.length(), and after ( i >= window size ) every time we move forward one character , we also take care of the one that was at end of our window size. Notice that the condition that we do ( match++, or math-- ), is the same as we did in Example 3.

      --  Only if we will decrement on a count number = 1 --> match++ 

      --  Only if we will increment on a count number = 0  -->  match-- 

Hope you get some experience to deal with other similar substring problems.

Happy Coding -_-
Ye Jiang

The power of Slow and Fast Pointer Technique -_-

                             The Power of Two Pointer 

-- OverView 

    The are lots of algorithm problems that can be solved by the two (slow & fast) pointer technique. What's more, we could use this technique to in place deal with many String manipulation problem in O(n) time, which requires a programmer have solid coding skills and deep impression about the physical meaning of two pointer in each problem. 

-- Examples 

1. First, Let's look at a pretty basic problem: The partition method we used when we perform quick sort. There are lots of different way to write the code for partition, but with this two pointer technique, I was just impressed. How clear the code will be ! 

By choosing a random pivot value, we partition the given array, from left to right, that all the value that smaller than pivot value be in the left of array, and or the value that is bigger or equal to pivot value sit right hand side of pivot. Finally we return the pivot index value as out put. 

private int partition(int[] a, int left, int right){

    

    }

 

2.1: The First Occurrence 

Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.

Assumptions

• There can be duplicate elements in the array.

Examples

• A = {1, 2, 3}, T = 2, return 1
• A = {1, 2, 3}, T = 4, return -1
• A = {1, 2, 2, 2, 3}, T = 2, return 1

Corner Cases

• What if A is null or A of zero length? We should return -1 in this case.

2.2. The Last Occurrence 

Given a target integer T and an integer array A sorted in ascending order, find the index of the last occurrence of T in A or return -1 if there is no such index.

Assumptions

• There can be duplicate elements in the array.

Examples

• A = {1, 2, 3}, T = 2, return 1
• A = {1, 2, 3}, T = 4, return -1
• A = {1, 2, 2, 2, 3}, T = 2, return 3

Corner Cases

• What if A is null or A is array of zero length? We should return -1 in this case.

Note: The only difference of 2.1 and 2.2, is the 2 place I made comment in the code above. 

2.3.The Closest Occurrence

Given a target integer T and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to T.

Assumptions

• There can be duplicate elements in the array, and we can return any of the indices with same value.

Examples

• A = {1, 2, 3}, T = 2, return 1
• A = {1, 4, 6}, T = 3, return 1
• A = {1, 4, 6}, T = 5, return 1 or 2
• A = {1, 3, 3, 4}, T = 2, return 0 or 1 or 2

Corner Cases

• What if A is null or A is of zero length? We should return -1 in this case.

3.  Remove Extra White Space 

Given a string, remove all leading/trailing/duplicated empty spaces.

Assumptions:

• The given string is not null.

Examples:

• “  a” --> “a”
• “   I        love DP     ” --> “I love DP”

Note: People may find various of ways to solve this problem, but the following solution that used slow and fast pointer is the most elegant one that I found so far. 

In this example the i is the fast pointer and the slow value is the slow pointer, the physical meaning is: the result are at left side of slow pointer 

4.  Remove Adjacent Repeated Characters

4.1: 

Remove adjacent, repeated characters in a given string, leaving only one character for each group of such characters.

Assumptions

• Try to do it in place.

Examples

• “aaaabbbc” is transferred to “abc”

Corner Cases

• If the given string is null, we do not need to do anything.

Note: We will still use two pinter here, "end" pointer here is the slow pointer and it also will act like the top of a "Virtual Stack", where when we move the i, the fast pointer here, we constantly look at the top of our stack, see if there is a duplication happen. 

4.2: 

Repeatedly remove all adjacent, repeated characters in a given string from left to right.

No adjacent characters should be identified in the final string.

Examples

• "abbbaaccz" → "aaaccz" → "ccz" → "z"
• "aabccdc" → "bccdc" → "bdc"

Note: I comment the only difference between 4.1 and 4.2, For 4.2, if there is a duplication we do not preserve any of them, so we pop off from our stack whenever we find there is adjacent duplication. 

5.   String Abbreviation Matching

Word “book” can be abbreviated to 4, b3, b2k, etc. Given a string and an abbreviation, return if the string matches the abbreviation.

Assumptions:

• The original string only contains alphabetic characters.
• Both input and pattern are not null.

Examples:

• pattern “s11d” matches input “sophisticated” since “11” matches eleven chars “ophisticate”.

Note: If someone still remember we discussed Wild card matching before, then you will find that it is a easy version of wild card matching and also could use recursive method to solve it ( as we did in Regular Expression matching)  

 Basically, we will keep one pointer for input , and the other for pattern. and if they will reach end at the same time, we had a successful matching ! 

-- End: 

Actually, if you would like to add sliding window algorithm into two pointer technique, which is also make sense. I hope you enjoy this basic but very powerful tool that we could use. Thanks. 

Happy Coding -_- 

Ye Jiang