Thursday, May 16, 2019

Leetcode solution 272: Closest Binary Search Tree Value II

Problem Statement 

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:
Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hints
  • Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  • Try to assume that each node has a parent pointer, it makes the problem much easier.
  • Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  • You would need two stacks to track the path in finding predecessor and successor node separately.  
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

At first glance, it might look very similar to the Closest Binary Search Tree Value. They need look similar except finding K in less than O(N) time is way harder, hehehehe
 


Okay, more seriously.
 

 

Brute force, convert BST into sorted array

A quick thought would be if we traverse the BST in order, and put them into an array, now the problem becomes given an sorted array, find K elements that are closest to the target. That search should be done binary search find the target, and expand left and right compare the values with diff, take the smaller one and continue. Overall, this brute force idea time complexity would be O(N), and space complexity is O(N), N is the total number of tree nodes.


Use a max heap

Another way or anytime when you need to find K things, always think about heap. Here if we traverse the tree (in any order) and use a K sized max heap, we can solve the problem in O(NlgK) time complexity, O(K) space complexity


Use two stacks 

This is a smart idea that I read from leetcode discussion. This is also following leetcode's hint. Keeping two separate stacks, one stack is all the nodes less or equal to the target (i.e., predecessor), the other is all the nodes larger than the target (i.e., successor). After that, merge those two stacks and keep the K closest element to target.

Note, the time complexity is still O(N + K). Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.


Use threaded tree

You might also think about the double threaded tree given the hint, starting from the root, keep asking the predecessor and successor since double threaded tree allows you to have that. However, I didn't code this one up since it requires you to modify the tree structure which normally not allowed in interviews and also it's a bit too complicated for a coding interview

Solutions

Brute force, convert BST into sorted array

Code it on your own :)
Time Complexity: assuming tree size is N, O(N)
Space Complexity: O(N)

 

Use a max heap


Time Complexity: assuming tree size is N, O(NlgK) because insertion into PQ is O(lgK)
Space Complexity: O(K)

 

Use two stacks


Time Complexity: assuming tree size is N, O(N+K) worst case. Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.
Space Complexity: O(N) worst case. Even if BST is balanced, we still need O(N/2), still O(N)

 

References

Saturday, April 27, 2019

Leetcode solution 270: Closest Binary Search Tree Value

Problem Statement 

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:
Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

This is a very easy problem as long as you are familiar with Binary Search Tree.  In order to find the value that is closest to the given target, we can traverse the tree and keep a record of the minimum delta. Of course we can traverse the entire tree but we can definite do it better by always branch out either left or right given the target and root node value.

For example, if  current node is 10, and target is 9, the next possible smaller value must exist only on the left part of or with the current node

     10
   /   \
  7     11

Solutions

Recursion solution 


 

Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search
Space Complexity:O(1) if not considering recursion function stacks.

Iterative solution 

public int closestValue(TreeNode root, double target) {
    int ret = root.val;   
    while(root != null){
        if(Math.abs(target - root.val) < Math.abs(target - ret)){
            ret = root.val;
        }      
        root = root.val > target? root.left: root.right;
    }     
    return ret;
}

From:
https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70331/Clean-and-concise-java-solution

Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search
Space Complexity:O(1)

 

References

Sunday, April 21, 2019

Leetcode solution 10: Regular Expression Matching

Problem Statement 

Given an input string (s) and a pattern (p), 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).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

The thought process is very similar to Leetcode Solution 44: Wildcard Matching, you can find the blog here and the video tutorial here.

Step 0 really is to understand what the "*" really means.
'*' Matches zero or more of the preceding element.
A few examples,
  • "" and "a*": True, since * could match zero occurrence of the preceding char 'a', not here zero means deleting the original 'a'
  •  "a" and "a*": True, since * could match "one" occurrence in total
  • "aa" and "a*": True since * could match an extra one occurrence of the preceding char 'a', you can also think of it as "two" occurrences of 'a' in total
  • "" and "*": A very tricky case, my code below returns True but leetcode expects False. My code still passes OJ so this is really not a valid case. I argue this should be True since it is one occurrence of empty "" in total

The first attempt (if you haven't seen this question before) is trying to solve it using recursion. The idea is simple. While comparing the s and p char by char, as soon as you see a "*", you will start recurse
  • remove the preceding char and the "*", recurse and compare 
  • for every char equals to the preceding char in the pattern, as long as they are equal to the current char in s, recurse and compare
The time complexity in a ballpark looks like exponential to the P length, but a more detailed analysis from leetcode's original solution can be found here.

If you recall what problems can be solved using DP, DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP
  • Only Yes/No, True/False question without returning detailed step by step results 
  • Extreme values, e.g., Max, Min, Best optimal value
 I have posted several videos on how to solve DP problems using a template, essentially
  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up
This problem can be solved using DP by having formulas like below when a "*" is seen


Once you have the formula, coding up DP problem should be a piece of cake. You can find the video tutorial on this problem here

Solutions

DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix
Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

Sunday, April 14, 2019

Leetcode solution 44: Wildcard Matching

Problem Statement 

Given an input string (s) and a pattern (p), 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).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

It seems an easy problem first using recursion and brute forcefully solving the problem, but the OJ will quickly throw a TLE (Time Limit Exceeded) error since it is exponential time. Well, if you were like me, tried really hard to optimize my brute force solution, either using some heuristics or pruning on the recursion, however, still no luck :(

DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP
  • Only Yes/No, True/False question without returning detailed step by step results 
  • Extreme values, e.g., Max, Min, Best optimal value
 I have posted several videos on how to solve DP problems using a template, essentially
  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up 
You can find the video tutorial on this problem here

Solutions

Brute force recursion, TLE

Time Complexity: assuming S length is M, P length is N, this is O(M*2^N), exponential basically
Space Complexity: No extra space needed other than the additional recursion function stack

 


DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix
Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

Monday, April 1, 2019

Leetcode solution 208: Implement Trie (Prefix Tree)

Problem Statement 

Implement a trie with insertsearch, and startsWith methods.
Example:
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true
Note:
  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

Trie (prefix tree) is a very common data structure that appears very often in interviews. I used to get asked Trie at Fitbit, Snap and Google back in the days. I highly recommend you brush up on this basic data structure.

Please refer to this Baozi Training Blog for a modified version explained:
https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html

Leetcode actually did a great job explaining this problem. Feel free to download the explanation here (all credit and copyright goes to leetcode, obviously) 

Solutions

 


Time Complexity: assuming N is the word length, insert O(N), search O(N), startWith O(N)
Space Complexity: assuming N is the word length, insert O(N), search O(1), startWith O(1)

References

Sunday, March 24, 2019

Leetcode solution 680: Valid Palindrome II

Problem Statement 


Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

  Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

We should all be very familiar with how to determine if a string is a palindrome by keeping two pointers, one from beginning and one from the end of the string. The variation of this problem is to we can at most delete one character. Our thought process is the same to try two pointers.

Let's use one example:  "abbac", when we start two pointers, the first char 'a' and the last char 'c' are different. We might want to check if the previous of 'c' equals to 'a', we can have a chance OR the next after 'a' is a 'c', we can also have a chance. In this case, we return True since the previous of 'c' indeed is 'a' and the rest is simply a palindrome.

However, what happens if we do have two choices? For example, "accac", the first 'a' and last 'c' are different, but we can choose either way, but it will result in different results. (i.e., "ccac" or "acca"), as long as one of the is a palindrome, we return True. Sounds familiar, yes, we can easily use recursion to achieve that. To make it better, we only need to recurse at most once since we are only allowed to delete at most one char.

Solutions

Implementation V1

Implementation V2

Time Complexity: O(N), N is the string length, worst case we traverse the string twice using recursion , O(N) + O(N) still equals O(N)

Space Complexity: No additional space is needed (recursion function stack not included). Even counting function recursion stack, it's still O(1), which means constant space since you are bound to recurse only once

References

Tuesday, March 12, 2019

Leetcode solution 211: Add and Search Word - Data structure design

Problem Statement 


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.
Example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

  Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

It's a string pattern searching problem, and because it matches the word strictly from the beginning to the end (note, even the partial matching is considered False, e.g., word "abcd", search("abc") should return False), the Trie (prefix tree) data structure comes very handy. It's a common simple data structure that often comes in coding interviews, be sure you can write it bug free.

Once we are familiar with Trie, addWord simply builds the Trie and search just looks for the exact matching. One tricky part of this problem is ".", which can match any one and only one letter. This requires a recursive search of all the sub-nodes in the trie when encountering a "."

Even not asked in this leetcode question, but there are some very good follow up question

Solutions


Time Complexity:
  • addWord: O(N), N is the length of the word
  • search: O(M), where M is the entire Trie's space (i.e., the total number of Trie nodes). Think about a worst case of N "............" dots. where N is the length of the word that is larger than the depth of the Trie (larger than the longest word seen so far). More specifically, it's N * (Nodes on Trie's each level) = N * (M / lgM) assuming trie's height is lgM, for worst case, N equals lgM, so N *(M / lgM) = lgM * (M / lgM) = M. Note a trie could be compressed (e.g., the single nodes are merged back to the upper level) but this analysis still holds true
Space Complexity:
  • addWord: O(N), creating N more nodes in the trie, N is the length of the word
  • search: No additional space needed

References