Search in Graph

                            Search in Dictionary 

   To search a specific target in a graph, which in other words to traversal a graph, we mainly have two ways to do it.  Namely, DFS and BFS. Both of them are well-know algorithms, if you do not know the basic idea of them, you can easily find a tutorial online regarding this two basic algorithms.

   Here are something I want to point out before we dig into some specific examples about them.

1. Because both algorithm will visit every node in a graph exactly once. So to traversal a whole graph, BFS and DFS have same time complexity, which is O(N).

2. In terms of optimal solution, BFS is guarantee to give you the optimal solution( the closest path), while DFS may give you a suboptimal solution.

3. BFS, in general, will use more memory(space complexity) than BFS, especially when brach factor of a graph become big.

               Example 1: Word Ladder  

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

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

Analyze:  A easy approach will be using dictionary to build a graph, where  two adjacent words have one difference in letter. Then we using BFS to find the shortest path from start word to end word, which will then give us its length.   

      However, under this approach,if we have a big size dictionary, we will waste tons of time to build the graph before we even start to search.  Besides, note that if the question asking you to return the length of path, in order to come up with a relatively efficient algorithm to solve this problem, you are gonna to only care about the length. What I mean by saying that is, if you go find the optimal path, which, then, will cost you more than you should, because we only care about its length, not exactly the path. 

     Hence, we  1. Not gonna build  a graph before we search. 

                        2. Not gonna remember the exactly path, while only care the distance. 

   It seems easy that we only will care about the distance, but how about not build a graph before we start to search ?  The solution will be we finding all possible next steps( the word have one difference with current word) of current step in dictionary then see if our target is in our next reachable words. So we actually only care about the part of graph we gonna step into. 

 Here is a solution based on those thoughts:  
  

      

 How about the getNext( s, dic ) method in Line 12 ? 

It has a interesting approach that try to change every position of this word into character from 'a' to 'z', then see do we have this word in our dictionary. 

 Here is the implementation: 

Notice Line 15, we remove visited word from dictionary to avoid re-visiting. 

         Example 2: Word Search  

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
--------------------------------------------------------------------------------------------------------------------------

Analyze : Notice that 1. We do have many duplicate characters in dictionary. For example, two 'A' , three 'E' are exist in example board.

                2.  Re-visiting is not allowed. That is why word" ABCB" should return false .

 If we set a data structure to remember every 'A' position, every 'B' position ... We will, again wast lots of time before start and also many extra space is needed.

 Besides, in order to avoid re-visiting, creating a another board to record the position we have visited is totally fine, but we do have a better approach, which will not cost extra memory !

 How we gonna do that ?
       1 . No position memory -- > We try every position as a possible start point.
       2 . No step to trying find next valid move --> try all possible 4 position.
       3.  No visited[][] record board --> We use bit mask modify this visited pos make it invalid.

After those step to simplify our code, here is a very elegant solution: 


Do you find the code style in Line 18, and 25 somewhat similar ?  

Yes, you may say it is very similar to backtracking algorithm, where you remove locally added element from the list after recursive call return. 

 Example 3: Add Search Word - Data structure design 

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A .means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

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

Analyze: If you do not know Trie, which also known as Prefix Tree, you should go and find a tutorial to learn what is a prefix tree and how to implement it.  Trie is great data structure that allow us to store and search words in a convenient way. 

   After we know about the prefix tree, the only question on this problem is how to search a word in prefix tree when the word have '.' in it.  

   This only problem could then solved by using a approach very close to DFS. 

Here is the Node class of prefix tree: 

   
 How we add words into this data structure: 

which is really the same thing we will doing to implement an ordinary Trie

Finally, How to search with '.'


Note that from Line 39, we start to deal with the '.' case in our search. The way is we trying to search through all possible words in our Trie from that point and recursive call enable us to do it  with very concise code.


Hope it helps you deal with some search problems. 


Enjoy Coding ^^
Ye Jiang

We Want Kth Element

          Kth Largest(smallest) Element Problems 

     Finding the largest or smallest element in a data structure may be trivial. But how about finding the Kth element?  Some times we can even do better than O(N) depending on the data structure given to us.
          Here are 3 interesting examples that about  finding the Kth element.

          Example 1: Kth Largest Element in an Array 

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

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

Analyze: There are lot of approaches to this problem. So go head and come up one by yourself ! 

1. The Simplest one will be sort the array and access the Kth largest element by its index. 

    --> This approach uses O(n*log(n)) running time and O(1) memory. 

2.  The second approach will be maintaining a Min Priority Queue that have size K. 

     --> this approach will run in O(n* log(k)) time and use O(k) memory. 

 

3. The optimal solution will be the one using quick select algorithm, which is very similar to partition method in quick sort. 

    --> This approach runs in average O(n) time and no extra memory cost. 

 *Note: There is also a improvement for quickSelect that can make sure we run in O(n) time. We could shuffle the input array to avoid the case that it is sorted in reverse order. Here is the code after add shuffle improvement. 

 

       Example 2: Kth Smallest Element in a BST 

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

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

Analyze: if you noticed that we are given a BST and make full use of its property, you may come up with a very elegant solution ! 

 So the idea is by counting how many node is in this current node's left subtree, we can figure out how many node's value in this tree is smallest than current node's value. 

Notice that the countNum method is very similar to the Height method in BST. 

    Example 3: Kth largest element in a stream 

Given an infinite stream of integers, find the k’th largest element at any point of time.

Example:

Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3

Output:    {_,   _, 10, 11, 20, 40, 50,  50, ...}

Extra space allowed is O(k).

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

Analyze: A solution will be keep a array of size k in sorted order, but the running time for insert a new number will be O(k). 

 The most efficient way to solve this problem is to maintain a Min Heap of size K, which will let us find the Kth largest in O(1) time and O(logk) time to process a new number. 

Here is the code for building and updating a Min Heap in JAVA: 

If I find out there are some other interesting problem related to this topic, I may update this blog :0 

Hope it helps. 

Enjoy Coding^^ 

Ye Jiang 

Backtracking Algorithm

           Backtracking Algorithm & Examples

  Backtracking is a general way to try all possible solutions(combinations)  in a problem. It recursively add next element into current list and remove this element when tried every possible combination with this element( after recursive call return ). It is a very useful to tool to let us try every possible solution with few lines of code and works pretty well in general case.  However, the drawback of this algorithm is time complexity. It usually have O(2^N) or O(N!) time complexity depending on different problems, which,again, mostly because it will try every possible combination.

Here are 4 examples that you may consider use backtracking approach to solve them.

        Example 1 :  Subsets 1 

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[  

[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] 

]

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

Analyze: This is a classic backtracking problem, where the power of backtracking may be fullly enbodyed. Besides it is also a little hard to come up with another solution.



Explain: If this is the first time you see a backtracking algorithm code, above code may seems a little weird to you. But it is actually very straightforward and common backtracking code. Here is few things I want to point out:
                      1. At line 11, we add current temp list into final results without any checking, because we need every possible combination as a part of answer in this problem. We may need to check certain properties before we add it into result list in other harder problems.
                   
                      2. At line 15, notice the for loop start from s ( start point) to end of the list, otherwise we will have many duplicate subsets. Besides, every recursive branch will have a different start point.
         
                     3.  Line 21 is a very crucial line of code, which make this algorithm works properly. This line of code will remove local added element from temp list and let it try other possible combination. For example for the example [ 1 , 2 , 3 ] above, after had [], [1], [1, 2], [1,2,3], recursive call will return, and this line of code will remove 3, then 2 from the list,which then we could try [ 1, 3] and have it in our results. ( It is very helpful that using pen and paper to trace what actually happened after recursive call return).

           Example 2: Subsets 2 

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[

[2],[1],[1,2,2],[2,2],[1,2],[]

]

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

Analyze: Just one change compare to the first example, so go ahead and try it by your self !

To deal with there may have duplicate one in our input array, we could:
      1. Sort the array and let possible duplicate one are adjacent to each other
      2. In the for loop if this element is same with previous one, we could then skip this one.

Here is the solution with those two changes:

         Example 3: Combination Sum 

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 

[
  [7],
  [2, 2, 3]
]

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

Analyze: This example is a upgrade from the previous backtracking problem, where it requires the subsets of candidate set that will have a certain  property ( add up together to target value in this case).
So we would like to :
                     1. Remember the total sum of current temp list, and how many value we are away from the target value.
                    2. Check if temp list have this property before add it into our result list.

Here is what a solution may look like:

     Example 4: Remove Invalid Parentheses 

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

--------------------------------------------------------------------------------------------------------------------------
Analyze: This is a advanced example to use backtracking strategy that we need to keep our final result are all optimal and this string is valid parentheses all the time. But the whole idea is that a '(' or ')' is either exist or not exist in our final result.

  Here is the solution using backtracking:



Explain: I do want to point out that:

    1. From line 3 - 10, we are counting how may Left or Right parentheses are extra in our input array , and we use this value to test weather a solution is optimal.

    2. We also keep a filed called open, which will make sure at any given time we do not have Right parentheses more than Left one.

    3. Line 26 and 27 ( or 29, 30) is the idea that we either add this parentheses or we do not add it, which is a typical backtracking approach.

    4. Line 34, could remove the last element we added into this StringBuilder, which is the same as list remove method in previous examples.


Hope it helps you to understand backtracking algorithm. 


Enjoy Coding^^

Ye Jiang

Interesting Intervals

                        Problems about Intervals 

   Always feel interested when deal with problems about intervals.  May be the feeling that you could visualize them in a 2D coordinates make me like them. Besides, after had few of them, you may feel they are not hard at all.

 Here is 4 examples about Intervals. Previous two are straightforward intervals, while the last two are more implicit.

           Example 1: Merge Intervals 

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

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

Analyze: Think about how you gonna approach this problem in general ( without any coding) ?

We probably will look through the whole input list and compare every adjacent two intervals, if they can be merged together then we merge them and look at next interval, or if can not be merged, we know that we will have this interval in our final output.

Two things need to notice before we start to implementing this idea:
  1. This idea only works when input intervals are in a sorted order.
  2. What we mean by saying " two intervals can be merged " ?

After figured out those two things, we may come up with a solution like below:

             Example 2 : Insert Intervals 

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

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

Analyze: Compare to the merge intervals question, this question provide already sorted interval for us, but one more interval will be insert into those sorted interval. We may come up with a very easy approach based on we already know how to solve problems like example 1.

Basically we could : 1. Insert while keep intervals sorted.
                                  2. Loop through the list, merge if necessary.




  Or if you like concise code

 

           Example 3: Meeting Rooms 1 

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

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

Analyze: If you already go through previous 2 examples, this is a piece of cake for you !

The whole idea will be: if there is a meeting room start before a meeting even ended, then it is impossible to attend them all.

      Example 4: Meeting Room 2 

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

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

Analyze: In the example 3, we stop when we find one conflict ( start time early than end time) then stop. In this example, we could then translate this question into a another question where ask us how may conflict we have on those intervals. So try it out ! 

Update: 
 After you ever come up with this solution ? 

which is a little bit modification of meeting room 1 and we are really accounting how many conflict there are in the input.  However, there is one fact that if previous meeting is ended. We could then reuse the previous room !  Hence, that is why we need also sort the end time to know when we will get a previous room free to use. Here is the code with some explanation comments: 

Hope those 4 questions may help you to deal with Interval questions ! 

Happy Coding^^ 

Ye Jiang 

Breaking Down Strategy

                    Breaking Down Big Problems 

   Some "big" problem looks very scary at the beginning. However, after we carefully analyze the problem, we may find that it is not the case, which simply because the "big" problem actually is composed by few relatively easy parts.  We could, therefore, solve them one by one. ^^ 

 Here is 3 examples that you may find out breaking down into sub-parts is very helpful to solve them. 

           Example 1: One Edit Distance 

Given two strings S and T, determine if they are both one edit distance apart.

Explain: two string is one distance apart when they only have one place be different. For example: "xyz" with "xy" ;   "abc" with "abd" ; " zero" with " fero". 

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

Analyze: There are lots of way to solving this problem. For example, you may use dynamic programming, or you may try to find first place they being different and made that change see if the resulting two string is the same. But, to me, the most straightforward  and clear solution is breaking down this problem in to two cases, which are deleting one character, or modifying one character. What's more, from the length of two input string we could easily find out which case we should put them into. ( if length are same, we consider one modifying case, else consider one deleting case). 

Here is  a solution based on the idea discussed above: 

           Example 2:  Regular Expression Matching 

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

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

Analyze: This is a very classic problem that many people do no know how to deal with at the beginning. But if we break down this problem into 3 sub-problems, you may find a relatively easy way to solve it.  

                                      1. There is "*" at next position. 

                                      2. There is "."  at next position. 

                                      3. There is a regular character at next position.   

  ---------------Now try it, see if you could solve it recursively based on those 3 cases ! -------------------

Here is a recursive solution: 

(Note that we reduce the input size every recursive call, until we reach the base case). 

Update( 7 / 23 / 2017 ) 
Recursive approach will cost up to O(4^m) time complexity where m is the length of the pattern. Here is the DP approach which only cost O(n*m), where n , m is the size of string and pattern ~. 

      Example 3: Wildcard Matching  

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Notice: The difference between Wildcard Matching and Regular Expression is not only about transform '?' to  '.' , but also '*' in Wildcard can exist independently mach any single or more sequence, while '*' in regular expression could only extend previous character. 

Analyze: Again, we could breaking down this problem into 3 sub-problems: 

                                                               1. if we get '*' in next position. 

                                                               2. if we get '?' 

                                                               3. or if we get  regular character 

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

Here is a solution using two pinter to scan two string: 

Notice: Although there is detail explanation in the comment of above code, just want to mention that  if we meet '*' before, then (NIndex will != -1) so we can keep entering the case 3 in above code, which represent '*' can represent any single or more sequence in wildcard matching. 

Hope this idea to solve problem could help you ! 

Enjoy Coding^^ 

Ye Jiang