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

Sunday, November 18, 2018

Leetcode Solution 438: Find All Anagrams in a String


Problem Statement 


Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
  Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

This looks like a string pattern matching problem, we might start go down the KMP or Rabin Karp route (calculate string hash value). However, the unique requirement is they need to be anagrams. We already know several way to compare if two words are anagrams. Sort, bucketize it. Assuming the longer string length is N, the shorter pattern string length is M, if we do it in brute force way, i.e., for each M length substring in N, we check if they are anagrams, it is O(N*M) assuming we have to repopulate all the maps. Obviously we can optimize this by keeping a sliding window only insert and delete one character at a time. That way, it is only O(N*256), still O(N). (note, 256 is the ASCII char length since every time we need to compare if two ASCII char maps are the same or not)


It is also a good problem to have a pattern on coding for two pointers (sliding) window problem.
  • Initialize the two maps
  • Keep a start and end pointer, move one at a time
  • Don't forget to compare the last element

Solutions

Sliding Window using Two Pointers

Time Complexity:O(N), len(s) is N, len(p) is M. We only loop through s once, each time we compare anagrams with a constant 256 loop, thus O(256*N) = O(N)
Space Complexity: O(N)

References

Sunday, November 4, 2018

Leetcode Solution 49: Group Anagrams


Problem Statement 


Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Note:
  • All inputs will be in lowercase.
  • The order of your output does not matter.
  Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

Every time we hear about anagrams, we automatically think would relate to how to find two words are anagrams, where we can solve in O(N), easy. That would result in a brute force solution.

Another quick thought would be sort each word and keep a map to track it, however, sorting is also not free.

Now we think harder, how can we avoid the O(MlgM) sorting (M is the word length) as the map's lookup key? Now the question becomes how we can generate a unique value (ideally string) for the same set of characters regardless of its order?  This is similar to the MD5 or SHA1 or hash value of certain object. So we can keep an array of chars, count the chars and translate that array into a string. Note simply count the sum of the array won't work, e.g., "ac" and "bb" will result in the same value.

Solutions

Brute force, for every pair of string in the array, check if they are anagrams. 

Time Complexity:O(M*N^2), M is the word length, and N is the string array length
Space Complexity: O(N)

Sort each string as key

As described above,we sort each string and use it as the lookup key so we can group the anagrams.
Time Complexity: O(N*M*LgM), M is the word length, and N is the string array length
Space Complexity: O(N)

"Hash" each string as key

Kind similar to hashing, we covert each string as key by generating a unique value using linear algorithm instead of sorting NlgN algorithm. 

Time Complexity: O(N*M), M is the word length, and N is the string array length
Space Complexity: O(N)

References

Monday, April 9, 2018

Leetcode Solution 155: Min Stack


Problem Statement 


Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack. 
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.
 
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

Since the Min Stack preserves most of the stack operations, it is natural to composite with a normal stack, the question is how do we keep the minimum value. Simply keeping the smallest value won't work since once that value is popped out from the stack, there is no way to track the next smallest value.

One solution is to define an extra struct where it carries the minimum value before itself is popped out of the stack, basically the current minimum value so far seen in this stack. When newer element comes in, if value is smaller than the previous one, we update. Else ignore the larger values and carry over the smaller value.

Another solution is to keep two stacks. Similarly, the other stack only keeps the smallest value. We can only keep the smallest value or we can always push a value with the current smallest value seen far (essentially similar to solution one).

Solutions

Define own structure to carry over the minimum value so far


Time Complexity:O(1) Push, Pop, Top, GetMin
Space Complexity: O(N) , N is the total number of nodes, used extra class storage, negligible in practice.

 

Use two stacks.

As described above, we simply keep a minimum stack. Below implementation only pushes the smallest value, and when pop, need to peek the stack.
Time Complexity: O(1),Push, Pop, Top, GetMin
Space Complexity: O(N) , N is the total number of nodes

References

Saturday, April 7, 2018

Leetcode Solution 538: Convert BST to Greater Tree


Problem Statement 

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

When a tree problem is presented, normally we will think if any kind of traversal could be applied, e.g, preorder/inorder/postorder or level order traversal. In this problem, we want to update the tree node value with the sum of itself and all the node values larger itself. Yep, directly modifying the input param values (In real world, it is bad practice to directly manipulate the input value since it might surprise your downstream callers unless it is clearly documented), so tree structure is not modified.

You might first think of a brute force method, perform a normal left to right inorder traversal, then it is sorted ascendingly, then do a rolling sum from largest to smallest element. This is normal when we don't really know how to deal with tree structure so we serialize the tree into an array and later we can deserialize it back. In this problem, we don't need to deserialize since tree structure is not changed. This however requires extra O(N) space.

Now let's look at a better solution. In BST, all the nodes that have greater value than the node itself lives in the right subtree, so if we traverse the right subtree first, update the tree value, then traverse the left subtree (all the right subtree nodes have greater value than left subtree), then the problem becomes doing an inorder traversal, except this time we go to right first, update value, then go to left. To keep the running sum, it is most easy to keep a global variable to track it.

Solutions

Naive inorder traversal with serialize tree into array 



Time Complexity: O(N), N is the total number of tree nodes
Space Complexity: O(N) , N is the total number of tree nodes, since we are using extra list.

 

 Reverse inorder traversal

As described above, we simply do a reverse inorder traversal, right to left and keep a running sum.


Time Complexity: O(N), N is the total number of tree nodes
Space Complexity: O(lgN) , N is the total number of tree nodes, since we are doing recursion.

References

Sunday, February 4, 2018

Leetcode solution 621 Task Scheduler


Problem Statement 

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
  1. The number of tasks is in the range [1, 10000].
  2. The integer n is in the range [0, 100].
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

  1. Array is not sorted, could it be sorted?
  2. Task is a finite set, 26 maximum. 
  3. It is about extreme value (min value in this case), can Dynamic Programming (DP) be applied?
  4. DP seems cannot be applied here, it is very hard to come up with a mathematical induction function, even though there is a solution by coming up with a math formula, but it is very hard to come up with this in a real interview session.  
  5. Can we do any binary search hear, nope
  6. Hmm... it seems maybe we can be greedy here, doing it in a round robin way. Schedule the largest job first, then 2nd largest job, then 3rd largest job until the internal is met. Note, we have to always apply the largest job as soon as possible, for example, if we have a test case [A, A, A, A, A, B, C, D, E] and interval n is 2, if we are doing strict round robin, it would be A, B, C, D, E, A, idle, idle, A, idle, idle, A, idle, idle, A -> 15 cycle, where we should really apply A as soon as possible, so it becomes A, B, C, A, D, E, A, idle, idle, A, idle, idle, A -> 13 cycle.

Solutions

Sort after every iteration 

Given the greedy sort, we want to always apply the largest job first, so we should sort the jobs first (job name does not matter), after meeting the interval requirement, sort the array again and repeat by applying the largest job first, then 2nd largest etc.

Use priority queue (max heap) 

Instead of sorting after every iteration, we can use a max heap to always pop out the largest element, and instead of sort O(NlgN) on every iteration, it will just be O(lgN) to heaptify, even though N is fixed 26 on size.

References