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 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 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Analysis:

Have a dummy node and a temporal node. Iterate the whole list and change every node pair.

Nice to have the figure to help understand.

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 swapPairs(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        dummy.next = head;
        
        while (head != null && head.next != null) {
            // First operation
            node.next = head.next;
            head.next = node.next.next;
            node.next.next = head;
            
            // Go to another round
            node = head;
            head = head.next;
        }
        
        return dummy.next;
    }
}

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 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 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle

Analysis:

Keep two values, one is the sum for all values. One is the global max sum. If the sum is less than 0, make it to be 0.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public int maxSubArray(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }
        
        return max;
    }
}

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 151 & 186. Reverse Words in a String I& II

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis:

Use extra place. To split the whole string and get a string array, then go from the back and put them in a new string.

Time complexity : O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public String reverseWords(String s) {
        // O(n) O(n)
        
        if (s == null || s.length() == 0) {
            return "";
        }
        
        s = s.trim();
        String[] str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for (int i = str.length - 1; i >= 0; i--) {
            if (!str[i].equals("")) {
                sb.append(str[i]).append(" ");
            }
        }
        
        return sb.toString().trim();
    }
}

Followup:
Could you do it in-place without allocating extra space?

Analysis:
Use str.toCharArray() to change it to char array. Then reverse the whole array. Scan the array, if find a ‘ ‘, then reverse it from beginning. Update the start.

Time complexity : O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public void reverseWords(char[] s) {
        // O(n) O(1)
        
        if (s == null || s.length == 0) {
            return;
        }
        
        // reverse the whole array
        reverse(s, 0, s.length - 1);
        
        //reverse part of the words
        for (int i = 0, start = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }
    
    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start++;
            end--;
        }
    }
}

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;
    }
}