Saturday, October 26, 2019

Leetcode solution 201: Bitwise AND of Numbers Range

Problem Statement 

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: [5,7]
Output: 4
Example 2:
Input: [0,1]
Output: 0

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Normally we just implement as we do at work, which is keep increasing the number and do an AND. It will still pass the OJ, just need to pay attention to overflow situation (using a long would solve the problem)

Now we are pushing ourselves, can we solve it more than linear. Only log/binary is faster than linear. The idea is to find the common left bits of m and n, and later shift n (total number of digits - common length digits) because the right part would end up to be 0.

For example, from 4 to 7, thte common left part is 1, the range and value would be 100 (which is n left shift twice)
  • 1 00
  • 1 01
  • 1 10
  • 1 11

Solutions

Linear solution


Time Complexity: O(N) essentially n - m
Space Complexity: O(1) no extra space is needed

Logarithmic solution


Time Complexity: O(lgN) because we keep dividing 2 (left shift) of n
Space Complexity: O(1) no extra space is needed

References

Saturday, October 12, 2019

Leetcode solution 103: Binary Tree Zigzag Level Order Traversal

Problem Statement 

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It’s purely an implementation problem to be honest. Very similar to to binary tree level order traversal, we just need to use some data structure to hold the values while we control the traversal order. I choose to use a deque (i.e., doubled linked list) to keep the order. You can also use a queue like many other online solutions but note when calling add(0, value) to an array list is not very efficient since to have array copy every time.

Solutions


Time Complexity: O(N) since we visit each node once
Space Complexity: O(N) since used a deque

References

Saturday, October 5, 2019

Leetcode solution 199: Binary Tree Right Side View

Problem Statement 


Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is a great problem and I highly recommend we solve it in both DFS and BFS for level order traversal because it  covers everything we need to know about trees in interviews.

This would be a better test case because right subtree would not be deep enough to cover the left subtree
   1            <---
 /   \
2     3         <---
 \     
  5             <---
[1, 3, 5] 

Level order traversal using BFS(queue)

It should be relatively natural for us think about using level order traversal and we can simply use a queue and always find the right most element when we pop out element from each level.

Level order traversal using DFS(map)

A pre-order traversal way, just like order level traversal using DFS with a map(key is depth, value is node). This method utilizes a depth to value map to record the right most value on each order while performing a pre-order traversal, namely record the node value, go left then go right. This way, right value can always overwrite the left value thus keeping a “right side view”



I personally don't like the leetcode official solution, where in DFS you don’t need two stacks and in
BFS you don’t need the maps.

Follow up, how about implement a left side view? Trivial right?

Solutions

Level order traversal using BFS(queue)


Time Complexity: O(N) since we visit each node once
Space Complexity: O(N), more precisely the number of element on the last level, aka queue size when it’s a complete tree


Level order traversal using DFS(map)

Time Complexity: O(N) since we visit each node once

Space Complexity: O(lgN) because we are using a map and map size should be tree height, which worst case could be O(N)

References

Saturday, September 28, 2019

Leetcode solution 1176: Diet Plan Performance

Problem Statement 

A dieter consumes calories[i] calories on the i-th day. 
Given an integer k, for every consecutive sequence of k days (calories[i], calories[i+1], ..., calories[i+k-1] for all 0 <= i <= n-k), they look at T, the total calories consumed during that sequence of k days (calories[i] + calories[i+1] + ... + calories[i+k-1]):
  • If T < lower, they performed poorly on their diet and lose 1 point; 
  • If T > upper, they performed well on their diet and gain 1 point;
  • Otherwise, they performed normally and there is no change in points.
Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.
Note that the total points can be negative.

Example 1:
Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explanation: Since k = 1, we consider each element of the array separately and compare it to lower and upper.
calories[0] and calories[1] are less than lower so 2 points are lost.
calories[3] and calories[4] are greater than upper so 2 points are gained.
Example 2:
Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explanation: Since k = 2, we consider subarrays of length 2.
calories[0] + calories[1] > upper so 1 point is gained.
Example 3:
Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explanation:
calories[0] + calories[1] > upper so 1 point is gained.
lower <= calories[1] + calories[2] <= upper so no change in points.
calories[2] + calories[3] < lower so 1 point is lost.

Constraints:
  • 1 <= k <= calories.length <= 10^5
  • 0 <= calories[i] <= 20000
  • 0 <= lower <= upper
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is an easy problem but might be a bit hard to code it up correctly in one pass. We can use a sliding window to keep a rolling sum and compare it with upper and lower bound.

A few caveats in implementation:
  • We can simplify using two pointers start and end by keeping an index i (start) and i - k (end)
  • We can only have one loop instead of having two separate loops
sliding window

Solutions

Sliding window


Time Complexity: O(N) visited the array once
Space Complexity: O(1) No extra space is needed

References

  • None

Saturday, September 21, 2019

Leetcode solution 1169: Invalid Transactions

Problem Statement 

A transaction is possibly invalid if:
  • the amount exceeds $1000, or;
  • if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.
Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.
Given a list of transactions, return a list of transactions that are possibly invalid.  You may return the answer in any order.

Example 1:
Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.
Example 2:
Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
Output: ["alice,50,1200,mtv"]
Example 3:
Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
Output: ["bob,50,1200,mtv"]

Constraints:
  • transactions.length <= 1000
  • Each transactions[i] takes the form "{name},{time},{amount},{city}"
  • Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.
  • Each {time} consist of digits, and represent an integer between 0 and 1000.
  • Each {amount} consist of digits, and represent an integer between 0 and 2000.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It's an implementation problem and it's up to you how fast you can type to determine whether you want to flex your muscles on object oriented design. It's actually quite a small moev, whether you want to convert the comma separated line into a Transaction object or not.

To meet the two conditions, we can simply loop over all the transactions while at the same time, keep a map to store all the transactions under the same name. Then the problem is compare the city for all the transactions under the same name that time is less or equal than 60 mins. At first I was trying to sort the collection based on the time in ascending order. However, that does not really help reduce the O(N^2) complexity since worst case is still all transactions are within the 60 mins bound, and one "bad" transaction can essentially cause all the previous "good" transactions to become bad, so we have to go back and revisit the previous ones. (as shown in below graph)

Example on one transaction make all previous ones invalid


Caveats
  • It's better to use a Set for de-duplication than a list since we might add duplicate transactions to the collection (e.g., a transaction > 1000 amount could also be invalid due to same name with different city under time < 60min)


Solutions


Time Complexity: O(N^2),we have to loop through the transactions in a nested way for worst case all transactions are under the same name and all within 60min.
Space Complexity: O(N),the result list and set and the extra hashmap we used

References

  • None

Friday, August 30, 2019

Leetcode solution 257: Binary Tree Paths

Problem Statement 

Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Easy problem. Use pre-order traversal from root to leaf and keep the recursion path. The recursion returning condition would be when a node doesn’t have left and right children. Note use a string to keep appending is easier than using a string builder, because we need to pop out and reset the string builder.

Caveat
  • Handle the single node situation when no "->". E.g.,  A vs A->B
There is also an iterative implementation of this using one stack, similar to BST iterator using one stack problem. 

Solutions

Pre-order traversal


Time Complexity: O(N), each node is visited once
Space Complexity: O(N), N is the total nodes since that's the string length you need

References

Friday, August 23, 2019

Leetcode solution 124: Binary Tree Maximum Path Sum

Problem Statement 


Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

When dealing with binary tree related problem, traversals using recursion is our friend. It seems we can perform a post-order traversal, and keep track of the maximum sums.

If the path cannot go across root, then in each post-order step, we will have the max_sum_of_the_left_path, max_sum_of_the_right_path, the current_node_value, we simply return and record

single_path_max = max(the current_node_value, max(max_sum_of_the_left_path, max_sum_of_the_right_path) + current_node_value)

However, the problem allows a path that goes through the root, therefore, we need to also record a max between left + current node value + right, i.e.,

global_max = max(single_path_max, max_sum_of_the_left_path + current_node_value + max_sum_of_the_right_path)

One caveat is in your recursion, we should still return the single_path_max. The reason we should not return the global_max is in that case, it will not be a single node to single node path.

Solutions

Post-order recursion


Time Complexity: O(N), each node is visited once
Space Complexity:No extra space is needed other than the recursion function stack

References

Leetcode solution 173: Binary Search Tree Iterator

Problem Statement 

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.

Example:
BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:
  • next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
  • You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

 

Brute force dump tree into array method

It’s very similar to BST in order traversal. From that train of thought , we can easily have a brute force solution: perform an in-order traversal, dump that order into an array. Then we can have an pointer point to the array and move the pointer forward every time we call next() method. The time complexity of this brute force way is O(N) in the constructor phase (N is the total number of nodes in the tree). Even though we iterate through the tree 2 times, it’s still O(N), hasNext() and Next() would all be O(1). Space complexity is O(N) as well since we need an extra array to store all the elements in the tree.
Brute force way to dump the tree into an array then iterate over the array
Image credit: https://leetcode.com/articles/binary-search-tree-iterator/



In order traversal using stack  

 

In order to reduce memory from O(N) to O(lgN), aka O(h) where h is the height of the tree, an alternative is return the next() inline while we are performing the recursion. The tricky part is if we still perform the in-order traversal using recursion, there is no easier way to plug in the next() method into the recursion call.

We know we can always use stack to simulate recursion (the push function stack part), and by having a tree node in the stack, it’s also easier to track the predecessor  and successor. The starting position should point to the smallest node in the tree, which is the left most node, we keep going left and pushing the nodes we visited to the stack. Whenever next() is called, we return the top of the stack, and we check if there is any right child of the node, if so, continue push the nodes into the stack until we hit the left most one. hasNext() is simply checking if there is still nodes in the stack. The time complexity of next() would be average O(1) even we have a while loop to keep finding the left most child since on high level, each node is still visited only once. Space complexity is O(lgN) since we at most would put the height of tree worth of elements into the stack.

Initial stage
Image credit: https://leetcode.com/articles/binary-search-tree-iterator/
Find the left most child
Image credit: https://leetcode.com/articles/binary-search-tree-iterator/


Solutions

In order traversal using stack

Note in next() method, we don't need to check if there is still element left in the stack. It is the caller's responsibility to check so. It is described in the Java's Iterator interface NoSuchElementException should be thrown.



Time Complexity: next(), hasNext() O(1) on average even with the while loop, think each node is visited essentially only once
Space Complexity: O(lgN), extra stack is needed capped at tree height

References

Sunday, August 18, 2019

Leetcode solution 772: Basic Calculator III

Problem Statement 


Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .
The expression string contains only non-negative integers, +-*/ operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].
Some examples:
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is an extension problem to Basic Calculator and Basic Calculator II. The differences are this time it really looks like a real calculator where it can do "+-*/" and with brackets.

It's still the same thought process with exactly the same idea before: having two stacks,  one stack for the operator and the other for the operands, and with exactly the same calculating preferences before: calculate * and / before + and -. When seeing right bracket, continue popping till you see the left bracket.

This works fine assuming all the integers are non-negative, which they are supposed to be based on the problem description, and that's what most of the existing online leetcode solutions did as well.

As of 08/18/2019, this doesn't seem to be the case because leetcode decides to include "non-negative" integer test cases. See below case "-1+4*3/3/3"

An "non-negative" integer case


Since we are practicing interviews, so let's also address the non-negative integer case as well

A few caveats
  • (New) Handle negative integer starting case:
    "-1 + 2" or "-(2+3)*4"
  • (New) Handle negative integer in between expression case:
    "1 - (-7)"
  • (New) Calculate whenever you can calculate since division order matters
    15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0,  then 15/0 invalid
  • Pay attention to the order when popping out operands and calculate, the order matters. 
  • The number might not be just single digit, so need to read the char and convert the numbers

Solutions

Two stacks for non-negative integer solution

Keep two stacks, operator and operands as explained in the above "Thought Process"



Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

Two stacks for negative integer solution

Essentially how do address the below two situations given the current code structure
  • (New) Handle negative integer starting case. I simply just check if the first char in trimmed string is "-", and push a -1 into operands and "*" into operator. (e.g.,  -(a+b) = -1 * (a+b) and -a = -1 * a)
    "-1 + 2" or "-(2+3)*4"
  • (New) Handle negative integer in between expression case. This is a bit hacky because a  "-" in the middle of the expression could mean two things: a normal minus sign or a negative sigh denoting negative integer. Luckily "1 - - 2" would not be a valid case which means there should always be a left bracket before the negative sign for negative integer. What I did was using isNegativeNumberFollowingLeftBracket to find those cases and put a -1 and * into the operator and operands respectively
    "1 - (-7)"


Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

References