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 25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Analysis:

We need to keep a count of the node. If the count % k == 0, then we reverse the node between this range.

/**

* Reverse a link list between pre and next exclusively

* an example:

* a linked list:

* 0->1->2->3->4->5->6

* |           |

* pre        next

* after call pre = reverse(pre, next)

*

* 0->3->2->1->4->5->6

*          |  |

*          pre next

*

* @return the reversed list’s last node, which is the precedence of parameter next

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 reverseKGroup(ListNode head, int k) {
        // O(n)
        
        if (head == null || head.next == null || k < 2) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        
        int count = 0;
        while (head != null) {
            count++;
            if (count % k == 0) {
                prev = reverseList(prev, head.next);
                head = prev.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
    
    // reverse list node from prev to end - 1
    public ListNode reverseList(ListNode prev, ListNode end) {
        ListNode cur = prev.next;
        ListNode temp = cur.next;
        
        while (temp != end) {
            cur.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
            temp = cur.next;
        }
        
        return cur;
    }
}

Leetcode 92 & 206. Reverse Linked List I & II

Reverse a singly linked list.

click to show more hints.

Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?

Analysis:

For iteration, we need to have a prev and next node for temporal save.

For recursive,

Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n₁ → … → n_k-1 → n_k → n_k+1 → … → n_m → Ø

Assume from node n_k+1 to n_m had been reversed and you are at node n_k.

n₁ → … → n_k-1 → n_k → n_k+1 ← … ← n_m

We want n_k+1’s next node to point to n_k.

So, n_k.next.next = n_k

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 reverseList(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return null;
        }
        
        // iteration
        ListNode current = head;
        ListNode prev = null;
        ListNode next;
        
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
        
        // recursive
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        
        return p;
    }
}

Followup:
Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Analysis:
Go through the list and find the position before m. Then start from m, reverse the n-m nodes like reverse linked list.

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 reverseBetween(ListNode head, int m, int n) {
        // O(n)
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        
        // Find the position before the reverse start
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        
        // Reverse the n - m nodes
        ListNode cur = prev.next;
        for (int i = 0; i < n - m; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

Leetcode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

Analysis:

The basic (two-pass) way is to count the occurrence of 0, 1 and 2. Then overwrite the corresponding value.

A better (one-pass) way is to use three pointers. One is for left, one is right and one is the index.

If we encounter 0, we swap it with the left value, left++, index++; if we encounter 1, index++; if we encounter 2, swap it with the right value, right–;

Time complexity: O(n)

Space complexity: O(1)

An example for this algorithm is :

1 0 2 2 1 0
    ^         ^
    L         H
    M

    Mid != 0 || 2
    Mid++

    1 0 2 2 1 0
    ^ ^       ^
    L M       H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 1 2 2 1 0
      ^ ^     ^
      L M     H

    Mid == 2
    Swap High and Mid
    High--

    0 1 0 2 1 2
      ^ ^   ^
      L M   H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 0 1 2 1 2
        ^ ^ ^
        L M H

    Mid == 2
    Swap High and Mid
    High--

    0 0 1 1 2 2
        ^ ^
        L M
          H

    Mid <= High is our exit case

Code is below:

public class Solution {
    public void sortColors(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return;
        }
        
        int left = 0; 
        int right = nums.length - 1;
        int i = 0;
        
        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums, i, left);
                left++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums, i, right);
                right--;
            } else {
                i++;
            }
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = 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 168 & 171. Excel Sheet Column Title / Number

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB

Analysis:
当n > 0时， 假如n % 26 == 0，则n为26的倍数，要转换为’Z’插入队首，之后n = n / 26 – 1， 假如n % 26 != 0， 则使用一般方法计算字符，int c = ‘A’ + n % 26 – 1， 之后 n /= 26。

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

Code is below:

public class Solution {
    public String convertToTitle(int n) {
        // O(n)
        
        if (n <= 0) {             return "";         }                  StringBuilder sb = new StringBuilder();                  while (n > 0) {
            if (n % 26 == 0) {
                sb.insert(0, 'Z');
                n = n / 26 - 1;
            } else {
                int c = 'A' + n % 26 - 1;
                sb.insert(0, (char) c);
                n /= 26;
            }
        }
        
        return sb.toString();
    }
}

Followup:
Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28

Analysis:
得到数字，其实就是把26进制的数转换为10进制的数。算法就是基本的进制转换方法，从后往前第n位的值乘上26^(n-1)。这里26进制数是1开始的，即A是1。

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

Code is below:

public class Solution {
    public int titleToNumber(String s) {
        // O(n)
        
        int res = 0;
        
        for (int i = 0; i < s.length(); i++) {
            res = res * 26 + (s.charAt(i) - 'A' + 1);
        }
        
        return res;
    }
}

Leetcode 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Analysis:

Brute force way. Go from the haystack and compare with needle, if it’s not the same, then break. Finally when j equals to the length of needle, we find the index.

Time complexity: O(mn)

Space complexity: O(1)

The code is below:

public class Solution {
    public int strStr(String haystack, String needle) {
        // O(mn)
        
        if (haystack == null || needle == null) {
            return -1;
        }
        
        int m = haystack.length();
        int n = needle.length();
        
        for (int i = 0; i < m - n + 1; i++) {
            int j = 0;
            for (j = 0; j < n; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            
            if (j == n) {
                return i;
            }
        }
        
        return -1;
    }
}

Leetcode 12 & 13. Integer to Roman & Roman to Integer

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:

I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)

因为罗马数字都是由最大化的表示，比如10会表示成X而不是VV，所以我们可以从最大可能的表示向小的依次尝试。因为提示1-3999，所有的可能性不多，我们可以直接打表来帮助我们选择表示方法。在一个数量级中有四种可能的表示方法，以1-9为例，1-3是由I表示出来的，4是IV，5是V，6-8是V和若干个I，9是IX。

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public String intToRoman(int num) {
        // O(n) O(n)
        
        if (num <= 0) {
            return "";
        }
        
        // List all possible cases
        String[] roman = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] integer = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        StringBuilder sb = new StringBuilder();
        
        // Go through the integer list and find the largest base to add
        for (int i = 0; i < integer.length; i++) {             while (num >= integer[i]) {
                sb.append(roman[i]);
                num -= integer[i];
            }
        }
        
        return sb.toString();
    }
}

Followup:
Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:
Put the corresponding value in a map. Then go through the string from back, if last value is less than the previous value, then add the value. Otherwise, minus the value.

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
2. 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
3. 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4

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

Below is the code:

public class Solution {
    public int romanToInt(String s) {
        // O(n) O(n)
        
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Map<Character, Integer> map = new HashMap<Character, Integer>();
	    map.put('I', 1);
	    map.put('V', 5);
	    map.put('X', 10);
	    map.put('L', 50);
	    map.put('C', 100);
	    map.put('D', 500);
	    map.put('M', 1000);
	    
	    int len = s.length();
	    
	    int res = map.get(s.charAt(len - 1));
	    for (int i = len - 2; i >= 0; i--) {
	        if (map.get(s.charAt(i + 1)) <= map.get(s.charAt(i))) {
	            res += map.get(s.charAt(i));
	        } else {
	            res -= map.get(s.charAt(i));
	        }
	    }
	    
	    return res;
    }
}