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 

Left and Right Part Approach

                                Left & Right Approach 

        Some seems hard sequence problems can be solved by using this Left & Right approach, which simply break the sequence into left and right two parts and solve it accordingly. 

   Here is two example that can demonstrate this idea: 

         Example 1: Product of Array Except Self 

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Suggestion: Try it before you look at the analyze below. 

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

Analyze:  It is easy to come up with a simple 0(n^2) solution, and solve it by using division in 0(n) seems also not that hard. However, notice that if there is a 0 in our input array the division approach will not work properly and the question specifically requires solve it without division. 

Here is the elegant O(n) approach that using Left & Right approach: 

      The product except the element it self is actually can be break down to Left part product and Right part product. For example for number 3 in the example above, the Left part : 1 * 2 = 2 , the Right part: 4. So the product except 3 will be  2 * 4 = 8. 

      Here is the code based on this idea: 

  

            Example 2: Longest Consecutive Sequence 

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Try it out, see if you can get it. 

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

 Analyze: The sequence here, again, can be divided into left and right parts, we can hold each elements of this array and to find its left possible sequence and right possible sequence. 

              The trick here is to put every number into Set that we could use contains() to find out weather we exist this number in input in O(1) time and remove it from our set after we do find it for not recounting the same sequence again. 

Hope you could use this approach to solve more problems :-) 

Enjoy Coding^^ 

Ye Jiang 

Sliding Window Algorithm

                   Sliding Window Algorithm & Examples 

    Sliding window algorithm is a very useful tool to solve problem about finding an optimal subarray or an optimal substring.  As you can get from the name, this algorithm will keep  two pointer in the input array or string, which may represent a window.  Inside this window is a subarray or substring that satisfy certain properties we want.  Then we keep moving this two pointer like sliding  this window from the beginning to end to find a optimal size window.


   Here are 5 examples that could  illustrate  this algorithm very clearly.

    Example 1: Minimum Size Subarray Sum 

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

     // Java Solution using sliding window approach: 

   Explain:  For this example, window will be the subarray from pointer i to j.  

      while ( j < a.length)    -- > we sliding this window until we reach the end of this array 

  while (sum >= s )      --> as long as the sum from i to j >= s, which means we keep a valid size window  

and we moving our start point i to reduce size of window if possible.

    Example 2 : Longest Substring with At Most Two Distinct Characters 

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

For example, Given s = “ababcd”,

T is "abab" which its length is 4.

 // Java Solution using sliding window approach: 

  Explain:  Here we have a start pointer and i as end pointer, we use for loop i  try every possible end point and use while loop

                                             while( distinct> 2 ) {

                                         while(--map[s.charAt(start++)]>0); 

                                              distinct --;  

                                        }       

        to adjust start point to keep this window valid.

             maxLen = Math.max(maxLen, i - start+1)

  will record the max Length we had during whole process.

Update:
 Sorry for the confusion code in that wile loop, which did 3 things in one line. Here is the code that is more readable: 

Example 3 : Longest Substring with At Most K Distinct Characters 

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

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

T is "aba" which its length is 3.

Here is a almost identical solution with sliding window approach: 

Explain : We almost have the same code except the condition we move our start point becomes

                  ( distinct > k). 

Update
 Also that one line of code did 3 things together, here is the version that is more readable and I prefer to write in this way 

     Example 4: Max One Problem 

Given a array that contains either 0 or 1 in each position. Also given a number b, which represent how many 0 you can turn into a 1. Need to find the maximum  continuous  1 you could make in this given array. 

  For example : array  A: [ 1,0 ,0 ,1 , 1 , 1 ,0 , 0, 1, 0, 0], number b = 2.   Flip two 0 at index 6 and 7, 

     then array A become [ 1,0, 0, 1,  1 , 1, 1,  1, 1, 0, 0] , which will give us maximum  6 consecutive 1  from index 3 to index  8.  In the end you should return those index of this sequence. So [3,4,5,6,7,8] will be return.     Another example will be A :[ 0 , 1 , 0 , 1, 0 ], b = 1.   array [ 1, 2 , 3] should be return.  

    Suggestion: try it by your self before you look at the solution below.

 Explain: there are explanations on the comment already. Just want to mention that there are lots of different way to solve this question, but sliding window approach is probably the most elegant one to deal with it. 

      Example 5: Minimum Window Substring 

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC". 

Again try it out, before you look at the solution below 

Explain:  

      The whole idea is let every char in T +1 value in the map we created, and as long as we find this same char in S, we  -1 value, and if we successfully covered T.length() many char, which means we find every char in T inside this window.  

       Notice at line 12 I have comment : j++ make conner case work and substring do not need to +1 . So there is two case when we calculate the substring length, 

1:  Start from 0 index until index k, where the length of substring is actually k+1.    

2:  From index i ( i !=0), to index j, i is close( the char at index i is not in range), the length is(  j - i ). 

So for the first situation, we need to add 1 in its length, but since we using j++, which will make this case still work for us. 

      

Update: 

Line 19 is still confusing to me sometime, So here is how we separate 3 things into pieces: 

  

  As you may find out, sliding window is a very elegant tool to solve problems. Hope you enjoy it. 

Enjoy Coding ^^ 

Ye Jiang