LeetCode – Generate Parentheses
1. Problem
Given n pairs of parentheses, write a function to generate all combinations of wellformed parentheses. For example, given n = 3, a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”.
2. Idea
This problem can be properly solved by a recursive strategy. Three pieces of information are maintained during the search for all matched parentheses: the exploration prefix so far, the number opening of the remaining opening parentheses, and the number closing of the remaining closing parentheses. When both opening and closing (initiallyn ) are zero, no parenthesis is left and we have got a new match. If only opening is zero, a new match is obtained by appending to prefix the remaining ‘)’s. Otherwise, we are safe to append to prefix a ‘(‘, subtract opening by one, and carry on the process recursively. If there has been more ‘(‘ than ‘)’ in the prefix , we can also append to prefix a ‘)’, subtract closing by one, and carry on the process recursively. By this means, all possible valid parentheses will be found.
3. Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package me.darrensunny.leetcode;
import java.util.ArrayList;
/**
* LeetCode – Generate Parentheses
* Created by Darren on 1445.
*/
public class GenerateParentheses {
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> parenthesis = new ArrayList<String>();
genParenthesis(“”, n, n, parenthesis);
return parenthesis;
}
private void genParenthesis(String prefix, int opening, int closing, ArrayList<String> parenthesis) {
// The number of ‘(‘s cannot be greater than that of ‘)’s anytime
if (opening > closing)
return;
if (opening == 0 && closing == 0) { // No ‘(‘ or ‘)’ remaining
parenthesis.add(prefix);
} else if (opening == 0) { // No ‘(‘ remaining; the rest must be ‘)’s
for (int i = 0; i < closing; i++)
prefix += “)”;
parenthesis.add(prefix);
} else {
genParenthesis(prefix+“(“, opening–1, closing, parenthesis); // Adding ‘(‘ is save all the time
if (closing > opening) // Add ‘)’ only if more ‘(‘s have been used (more ‘)’s remaining)
genParenthesis(prefix+“)”, opening, closing–1, parenthesis);
}
}
}

4. Wrapup
You might be interested in knowing the number of such combinations ofn pairs of parentheses. In fact, its number is known as the Catalan number, which is calculated as follows:
You are recommended to learn from the Wikipedia page more applications that yields to the Catalan number.
LeetCode – Merge k Sorted Lists
1. Problem
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
2. Idea
A trivial solution is to use k−1 comparisons to find the smallest node (i.e., whose value is the smallest) among k lists, and repeat this process for ntimes where n is the number of the nodes in all lists. This solution yieldsO(nk) time complexity. Alternatively, there are at least two nontrivial solutions, by divideandconquer or by using a min heap.
 By dividieandconquer: This idea resembles that of MergeSort, where a list is sorted by dividing its elements into two parts, sorting each part recursively, and merging them into a list. In the context of this problem, we can divide the sorted lists into two parts, merge each part recursively, and finally merge the two parts into a list. Now suppose the number of the nodes in the k lists is n . It can be seen that the running time T(k) for merging k lists has the recursive expression:
T(k)=2T(k/2)+O(n).
By the master theorem (or more vividly by the recursion tree generated by the above equation) and since k=O(n) ,
T(k)=O(k)+O(nlogk)=O(nlogk).Its space complexity is the size of the recursion stack, which is O(logk) .
 By using a min heap (priority queue): Things become simpler when an appropriate data structure is used. In this case, we can use a min heap of size k to save the smallest node in each list. As long as the heap is not empty, its min node is definitely the smallest among the remaining nodes in all lists, and thus inserted to the resulting list and removed from the heap. When the node has a next node, we put the next node into the heap and repeat the process until the queue is empty (all nodes have been processed). Since each insertion into and removal from the heap cost O(logk) time, and there are exactly n insertions and removals, the time complexity for this approach is O(nlogk) . The space usage is clearly O(k) due to the maintenance of the heap.
3. Implementation
The above nontrivial ideas are individually implemented as follows.
 Divide and Conquer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// By divideandconquer: 392ms for a total of 129 cases
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null  lists.isEmpty()) // Empty lists
return null;
int k = lists.size();
// Merge the lists within indices 0 and k1 (inclusive, i.e. all lists)
return mergeLists(lists, 0, k–1);
}
// Merge the lists within indices begin and end into a list
private ListNode mergeLists(ArrayList<ListNode>lists, int begin, int end) {
if (begin > end) // Invalid
return null;
if (begin == end) // Merge one list
return lists.get(begin);
if (begin+1 == end) // Merge two lists
return merge(lists.get(begin), lists.get(end));
// Merge more than two lists
int middle = (begin+end) / 2;
// Divideandconquer: merge the lists within indices begin and middle, and those
// within indices middle+1 and end, and merge these two resulting lists
return merge(mergeLists(lists, begin, middle), mergeLists(lists, middle+1, end));
}
// Merge two sorted lists into a list
private ListNode merge(ListNode n1, ListNode n2) {
ListNode head = new ListNode(0), tail = head; // Use a header to avoid boundary check
// Add the smaller node into the list until the end of a list
while (n1 != null && n2 != null) {
if (n1.val <= n2.val) {
tail.next = n1;
n1 = n1.next;
} else {
tail.next = n2;
n2 = n2.next;
}
tail = tail.next;
}
// Add the remaining part (if any)
if (n1 != null)
tail.next = n1;
else
tail.next = n2;
return head.next; // Return the list without the header
}

 Priority Heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// By priority queue: 428ms for a total of 129 cases
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null  lists.isEmpty()) // Empty lists
return null;
int k = lists.size();
// Use a heap (priority queue) to process
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(k, new Comparator<ListNode>() {
@Override
public int compare(ListNode n1, ListNode n2) {
return n1.val–n2.val;
}
});
// Put the first (smallest) node into the heap
for (ListNode node : lists) {
if (node != null)
heap.offer(node);
}
ListNode head = new ListNode(0), tail = head; // Use a header to avoid boundary check
// Put the smallest in the heap to the resulting list,
// and add its next node (if any) to the heap
while (!heap.isEmpty()) {
ListNode temp = heap.poll();
tail.next = temp;
tail = tail.next;
if (temp.next != null)
heap.offer(temp.next);
}
return head.next; // Return the list without the header

4. Wrapup
Both solutions have the same time complexity, and are accepted by LeetCode OJ. Though the priority queue solution costs slightly more time given the test cases, it is more preferable since it is easy to implemented,highly readable, and does not need to maintain the information for recursion as in the divideandconquer one.
LeetCode – Swap Nodes in Pairs
1. Problem
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.
2. Idea
A trivial problem that does not need much elaboration. Just use a reference that points to the node ahead each pair to complete the swapping. Note the use of a header node to avoid boundary check.
3. Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package me.darrensunny.leetcode;
/**
* LeetCode – Swap Nodes in Pairs
* Created by Darren on 1446.
*/
public class SwapNodesInPairs {
public ListNode swapPairs(ListNode head) {
ListNode header = new ListNode(0), t = header; // Use a header to avoid boundary check
header.next = head;
// Swap adjacent nodes; t points to the node ahead the first of the pair
while (t.next != null && t.next.next != null) {
// Swapping
ListNode temp = t.next;
t.next = t.next.next;
temp.next = t.next.next;
t.next.next = temp;
// Advance t to ahead the next pair
t = temp;
}
return header.next;
}
}

4. Wrapup
Only an extra node is created. One pass of the nodes suffices to get the work done.