Leetcode 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Analysis:

Use queue.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List> levelOrder(TreeNode root) {
        // O(n) BFS
        
        List<List> result = new ArrayList<>();
        
        if (root == null) {
            return result;
        }
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            ArrayList level = new ArrayList<>();
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                // poll the head
                TreeNode head = queue.poll();
                level.add(head.val);
                
                // add the left subnode
                if (head.left != null) {
                    queue.offer(head.left);
                }
                
                // add the right subnode
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

Leetcode 235 & 236. Lowest Common Ancestor of a Binary (Search) Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Analysis:

Check for the properties of the BST. If root.val > both p.val and q.val, we know the lca is in the left side, then goto the left subtree. If root.val < both p.val & q.val, then go to right subtree. Otherwise, return root.

Time complexity: O(logn)

Space complexity: O(1)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // O(logn)
        
        if (root == null || p == null || q == null) {
            return null;
        }
        
        if (root.val > p.val && root.val > q.val) {
            // left sub tree
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            // right sub tree
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

Followup:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Analysis:

No properties similar to BST. We can use divide and conquer. Divide the tree to be the left and right. If left & right not null, return root. If left not null, return left, otherwise return right.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // O(n)
        
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // divide: get the left and right lca
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // conquer: check for the left and right
        // If left and right both exits, then return root
        if (left != null && right != null) {
            return root;
        }
        
        if (left != null) {
            return left;
        }
        
        if (right != null) {
            return right;
        }
        
        return null;
    }
}

Leetcode 2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis:

• Initialize current node to dummy head of the returning list.
• Initialize carry to $0$.
• Initialize $p$ and $q$ to head of $l1$ and $l2$ respectively.
• Loop through lists $l1$ and $l2$ until you reach both ends.
  • Set $x$ to node $p$‘s value. If $p$ has reached the end of $l1$, set to $0$.
  • Set $y$ to node $q$‘s value. If $q$ has reached the end of $l2$, set to $0$.
  • Set $sum=x+y+carry$.
  • Update $carry=sum/10$.
  • Create a new node with the digit value of $(summod10)$ and set it to current node’s next, then advance current node to next.
  • Advance both $p$ and $q$.
• Check if $carry=1$, if so append a new node with digit $1$ to the returning list.
• Return dummy head’s next node.

Time complexity: O(max(m, n))

Space complexity: O(max(m, n))

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // O(n) O(1)
        
        if (l1 == null || l2 == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        int sum = 0;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            
            sum = num1 + num2 + carry;
            
            // update the next node
            cur.next = new ListNode(sum % 10);
            
            cur = cur.next;
            carry = sum / 10;
            
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        
        // Check the last corner case
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        
        return dummy.next;
    }
}

Leetcode 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.

• The linked lists must retain their original structure after the function returns.

• You may assume there are no cycles anywhere in the entire linked structure.

• Your code should preferably run in O(n) time and use only O(1) memory.

Analysis:

3 steps:

• Get the length of both list
• Let the longer list to go before len1-len2 steps
• Make the lists go further, if they’re the same, then we find it

Time complexity: O(m + n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // O(m + n)
        
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // Let the longer list to go before lenA - lenB 
        for (int i = 0; i < Math.abs(lenA - lenB); i++) {             if (lenA > lenB) {
                headA = headA.next;
            } else {
                headB = headB.next;
            }
        }
        
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    
    public int getLength(ListNode head) {
        int len = 0;
        
        while (head != null) {
            head = head.next;
            len++;
        }
        
        return len;
    }
}

Leetcode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analysis:

Make a dummy node, compare the two values in the two lists. If one is smaller, add it to the head. Update the head to next.

Note: the two lists may not be the same length. After all iteration, we need to check the lefts and add them to the result.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // O(n)
        
        if (l1 == null) {
            return l2;
        }
        
        if (l2 == null) {
            return l1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            
            cur = cur.next;
        }
        
        // Check if there're lefts
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        
        return dummy.next;
    }
}

Leetcode 141 & 142. Linked List Cycle I & II

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Analysis:

Typical two pointer questions. Give two pointers fast and slow, fast run 2 steps and slow run 1 step. If there’s a cycle, finally slow == fast. If no cycle, fast == null || fast.next == null.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        // while (slow != fast) {
        //     if (fast == null || fast.next == null) {
        //         return false;
        //     }
            
        //     slow = slow.next;
        //     fast = fast.next.next;
        // }
        
        // return true;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

Followup:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Analysis:
Follow the figure below:

链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            if (fast == slow) {
                break;
            }
        }
        
        if (fast != slow) {
            return null;
        }
        
        fast = head;
        
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return fast;
    }
}

Leetcode 48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Analysis:

Use some math magic?

Time complexity: O(n ^ 2)

Space complexity: O(1)

Code is below:

public class Solution {
    public void rotate(int[][] matrix) {
        // O(n^2)
        
        if (matrix == null || matrix.length == 0 ||
            matrix[0] == null || matrix[0].length == 0) {
                return;
            }
            
        int len = matrix.length;
            
        for (int i = 0; i < len / 2; i++) {
            for (int j = 0; j < (len + 1) / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len -j - 1];
                matrix[len - i - 1][len -j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = temp;
            }
        }
        
    }
}

Leetcode 238. 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 ofnums except nums[i].

Solve it without division and in O(n).

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

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Analysis:

To get the products of all others, we can have an array of the same length. Then go through the array, get all products for all lefts. Then Go from the back and multiply all values on the right.

Note: we need to set up the first value res[0]  to be 1 initially.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        // O(n) O(1)
        
        if (nums == null || nums.length == 0) {
            return nums;
        }
        
        int[] res = new int[nums.length];
        int left = 1;
        int right = 1;
        
        res[0] = 1;
        
        // Get the product of all lefts
        for (int i = 1; i < nums.length; i++) {             left = left * nums[i - 1];             res[i] = left;         }                  // Go from the back, get the product of all rights         for (int i = nums.length - 2; i >= 0; i--) {
            right = right * nums[i + 1];
            res[i] = right * res[i];
        }
        
        return res;
    }
}

Leetcode 121. Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Analysis:
Go through the whole array and maintains the min value and the max profit.

Time complexity: O(n)
Space complexity: O(1)

Code is below:

public class Solution {
    public int maxProfit(int[] prices) {
        // O(n) 
        
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        // The smallest value and the profit
        int min = Integer.MAX_VALUE;
        int profit = 0;
        
        for (int price : prices) {
            // update the min value and the max profit
            min = price < min ? price : min;             profit = (price - min) > profit ? price - min : profit;
        }
        
        return profit;
    }
}

Leetcode 204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Analysis:

Sieve of Eratosthenes

To avoid time out. Basic idea:

Create a boolean array of size n and mark them true;

Go through the array, if find a prime number p, then start p^2, p^2+p, p^2+2p are all not prime number. Mark them to be false;

Go through the array again and count the prime number.

Note: 0 & 1 are not prime

(n/2+n/3+n/5…+n/比n小的最大素数） = n*(小于n的所有素数倒数的和） = O(n * log(logn))

Time complexity: O(nloglogn)

Space complexity: O(n)

Code is below:

public class Solution {
    public int countPrimes(int n) {
        // O(nloglogn) O(n)
        
        int count = 0;
        
        boolean[] prime = new boolean[n];
        
        for (int i = 2; i < n; i++) {
            prime[i] = true;
        }
        
        for (int i = 2; i * i < n; i++) {
            if (prime[i]) {
                // start from p^2, p^2+p, p^2+2p... not prime
                for (int j = i * i; j < n; j += i) {
                    prime[j] = false;
                }
            }
        }
        
        for (int i = 2; i < n; i++) {
            if(prime[i]) {
                count++;
            }
        }
        return count;
    }
}

Time out method:

public int countPrimes(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}

private boolean isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}