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

• Youtube
• B站

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

• Leetcode disucssion solution

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

• Youtube
• B站

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

• Leetcode disucssion solution using add(0,value)

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

• Youtube
• B站

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

• Leetcode official solution  
• Code solving level order traversal using DFS with a map