Sunday, April 23, 2017

LeetCode Online Judge Questions Table

Leetcode (Finished)

# Title Difficulty Keyword
303 Range Sum Query - Immutable Easy DP
301 Remove Invalid Parentheses Hard
300 Longest Increasing Subsequence Medium DP
299 Bulls and Cows Easy Hash Map
297 Serialize and Deserialize Binary Tree Hard Tree Travsersal
295 Find Median from Data Stream Hard Heap
292 Nim Game Easy
290 Word Pattern Easy Hash
289 Game of Life Meduim Array
287 Find the Duplicate Number Hard Two Pointers, Linked list
284 Peeking Iterator Medium Design
283 Moving Zeros Easy two pointers
282 Expression Add Operators Hard DFS, String
279 Perfect Squares Medium BFS, DP
278 First Bad Version Easy binary search
275 H-Index II Medium binary search
274 H-Index Medium
273 Integer to English Words Hard String
268 Missing Number Medium
264 Ugly Number II Medium
263 Ugly Number Easy
260 Single Number III Medium
258 Add Digits Easy
257 Binary Tree Paths Easy
242 Valid Anagram Easy
241 Different Ways to Add Parentheses Medium
240 Search a 2D Matrix II Medium
239 Sliding Window Maximum Hard
238 Product of Array Except Self Medium
237 Delete Node in a Linked List Easy
236 Lowest Common Ancestor of a Binary Tree Medium
235 Lowest Common Ancestor of a Binary Search Tree Easy
234 Palindrome Linked List Easy
233 Number of Digit One Hard
232 Implement Queue using Stacks Easy
231 Power of Two Easy
230 Kth Smallest Element in a BST Medium
229 Majority Element II Medium
228 Summary Ranges Medium
227 Basic Calculator II Medium
226 Invert Binary Tree Easy
225 Implement Stack using Queues Easy
224 Basic Calculator Hard
223 Rectangle Area Easy
222 Count Complete Tree Nodes Medium
221 Maximal Square Medium
220 Contains Duplicate III Medium
219 Contains Duplicate II Easy
218 The Skyline Problem Hard
217 Contains Duplicate Easy
216 Combination Sum III Medium
215 Kth Largest Element in an Array Medium
214 Shortest Palindrome Hard
213 House Robber II Medium DP
212 Word Search II Hard
211 Add and Search Word - Data structure design Medium
210 Course Schedule II Medium
209 Minimum Size Subarray Sum Medium
208 Implement Trie (Prefix Tree) Medium
207 Course Schedule Medium
206 Reverse Linked List Easy
205 Isomorphic Strings Easy
204 Count Primes Easy
203 Remove Linked List Elements Easy
202 Happy Number Easy
201 Bitwise AND of Numbers Range Medium
200 Number of Islands Medium
199 Binary Tree Right Side View Medium
198 House Robber Easy
191 Number of 1 Bits Easy
190 Reverse Bits Easy
189 Rotate Array Easy
188 Best Time to Buy and Sell Stock IV Hard
187 Repeated DNA Sequences Medium
179 Largest Number Medium
174 Dungeon Game Hard
173 Binary Search Tree Iterator Medium
172 Factorial Trailing Zeroes Easy
171 Excel Sheet Column Number Easy
169 Majority Element Easy
168 Excel Sheet Column Title Easy
167 Two Sum II - Input array is sorted Medium
166 Fraction to Recurring Decimal Medium
165 Compare Version Numbers Easy
164 Maximum Gap Hard
162 Find Peak Element Medium
160 Intersection of Two Linked Lists Easy
155 Min Stack Easy
154 Find Minimum in Rotated Sorted Array II Hard
153 Find Minimum in Rotated Sorted Array Medium
152 Maximum Product Subarray Medium
151 Reverse Words in a String Medium
150 Evaluate Reverse Polish Notation Medium
149 Max Points on a Line Hard
148 Sort List Medium
147 Insertion Sort List Medium
146 LRU Cache Hard
145 Binary Tree Postorder Traversal Hard
144 Binary Tree Preorder Traversal Medium
143 Reorder List Medium
142 Linked List Cycle II Medium
141 Linked List Cycle Easy
140 Word Break II Hard
139 Word Break Medium
138 Copy List with Random Pointer Hard
137 Single Number II Medium
136 Single Number Easy
135 Candy Hard
134 Gas Station Medium
133 Clone Graph Medium
132 Palindrome Partitioning II Hard
131 Palindrome Partitioning Medium
130 Surrounded Regions Medium
129 Sum Root to Leaf Numbers Medium
128 Longest Consecutive Sequence Hard
127 Word Ladder Medium
126 Word Ladder II Hard
125 Valid Palindrome Easy
124 Binary Tree Maximum Path Sum Hard
123 Best Time to Buy and Sell Stock III Hard
122 Best Time to Buy and Sell Stock II Medium
121 Best Time to Buy and Sell Stock Easy
120 Triangle Medium
119 Pascal's Triangle II Easy
118 Pascal's Triangle Easy
117 Populating Next Right Pointers in Each Node II Hard
116 Populating Next Right Pointers in Each Node Medium
115 Distinct Subsequences Hard
114 Flatten Binary Tree to Linked List Medium
113 Path Sum II Medium
112 Path Sum Easy
111 Minimum Depth of Binary Tree Easy
110 Balanced Binary Tree Easy
109 Convert Sorted List to Binary Search Tree Medium
108 Convert Sorted Array to Binary Search Tree Medium
107 Binary Tree Level Order Traversal II Easy
106 Construct Binary Tree from Inorder and Postorder Traversal Medium
105 Construct Binary Tree from Preorder and Inorder Traversal Medium
104 Maximum Depth of Binary Tree Easy
103 Binary Tree Zigzag Level Order Traversal Medium
102 Binary Tree Level Order Traversal Easy
101 Symmetric Tree Easy
100 Same Tree Easy
99 Recover Binary Search Tree Hard
98 Validate Binary Search Tree Medium
97 Interleaving String Hard
96 Unique Binary Search Trees Medium
95 Unique Binary Search Trees II Medium
94 Binary Tree Inorder Traversal Medium
93 Restore IP Addresses Medium
92 Reverse Linked List II Medium
91 Decode Ways Medium
90 Subsets II Medium
89 Gray Code Medium
88 Merge Sorted Array Easy
87 Scramble String Hard
86 Partition List Medium
85 Maximal Rectangle Hard
84 Largest Rectangle in Histogram Hard
83 Remove Duplicates from Sorted List Easy
82 Remove Duplicates from Sorted List II Medium
81 Search in Rotated Sorted Array II Medium
80 Remove Duplicates from Sorted Array II Medium
79 Word Search Medium
78 Subsets Medium
77 Combinations Medium
76 Minimum Window Substring Hard
75 Sort Colors Medium
74 Search a 2D Matrix Medium
73 Set Matrix Zeroes Medium
72 Edit Distance Hard
71 Simplify Path Medium
70 Climbing Stairs Easy
69 Sqrt(x) Medium
68 Text Justification Hard
67 Add Binary Easy
66 Plus One Easy
65 Valid Number Hard
64 Minimum Path Sum Medium
63 Unique Paths II Medium
62 Unique Paths Medium
61 Rotate List Medium
60 Permutation Sequence Medium
59 Spiral Matrix II Medium
58 Length of Last Word Easy
57 Insert Interval Hard
56 Merge Intervals Hard
55 Jump Game Medium
54 Spiral Matrix Medium
53 Maximum Subarray Medium
52 N-Queens II Hard
51 N-Queens Hard
50 Pow(x, n) Medium
49 Group Anagrams Medium
48 Rotate Image Medium
47 Permutations II Medium
46 Permutations Medium
45 Jump Game II Hard
44 Wildcard Matching Hard
43 Multiply Strings Medium
42 Trapping Rain Water Hard
41 First Missing Positive Hard
40 Combination Sum II Medium
39 Combination Sum Medium
38 Count and Say Easy
37 Sudoku Solver Hard
36 Valid Sudoku Easy
35 Search Insert Position Medium
34 Search for a Range Medium
33 Search in Rotated Sorted Array Hard
32 Longest Valid Parentheses Hard
31 Next Permutation Medium
30 Substring with Concatenation of All Words Hard
29 Divide Two Integers Medium
28 Implement strStr() Easy
27 Remove Element Easy
26 Remove Duplicates from Sorted Array Easy
25 Reverse Nodes in k-Group Hard
24 Swap Nodes in Pairs Easy
23 Merge k Sorted Lists Hard
22 Generate Parentheses Medium
21 Merge Two Sorted Lists Easy
20 Valid Parentheses Easy
19 Remove Nth Node From End of List Easy
18 4Sum Medium
17 Letter Combinations of a Phone Number Medium
16 3Sum Closest Medium
15 3Sum Medium
14 Longest Common Prefix Easy
13 Roman to Integer Easy
12 Integer to Roman Medium
11 Container With Most Water Medium
10 Regular Expression Matching Hard
9 Palindrome Number Easy
8 String to Integer (atoi) Easy
7 Reverse Integer Easy
6 ZigZag Conversion Easy
5 Longest Palindromic Substring Medium
4 Median of Two Sorted Arrays Hard
3 Longest Substring Without Repeating Characters Medium
2 Add Two Numbers Medium
1 Two Sum Easy Hash Map

Friday, January 13, 2017

leetCode Question: Remove Invalid Parentheses

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]


In this post, I will firstly present the very basic yet workable solutions using BFS, which is implemented in C++.

Then I will explain the DFS solution which is much faster but needs a little more thinking. It is implemented in python.


First of all, notice that the problem requires all possible results, thus a search algorithm (BFS, or DFS) often would be a good option.

Considering the BFS solution, in this problem we will expand a "tree" with all its child nodes from one level to the other, until we find the leaf nodes we want. So given a string s, the mimimum number of deletion is 0, which is the string itself, also it is the root node of our tree. If it is a valid string, we're done.

Then we expand the tree by delete only 1 parentheses, each child node is one string where 1 parentheses is deleted from the root. Therefore, nodes in this level of tree, represents all possible strings where only 1 parentheses is removed.

We could check each new string and see if it is a valid one. If in current level there is at lease one valid string, the search is terminated after this level is done. Since the minimum of deletion is current level depth, while the possible valid string are all in this level.

For the implementation, we should have:

  • A function to check if the string is valid or not.
  • A queue for the BFS, which stores the nodes in the same level.
    • Here I use a "map" which we will eliminate the duplicate strings, so that the number of "check" could be reduced.
      Please check the C++ code below for more details.


Some will notice that in the BFS solution above, the bottleneck is the number of calls for "check". Each time we have to check all the nodes in current level and then go to next level. Alternatively, we could try using DFS.

To reduce the number of "check" being called, we could store the state (true or false) of nodes in each search path. So in next search if we go to the same node, we already have the states, which we don't have to check again.

Also, we could firstly compute the number of '(' and ')' to be removed by counting the parentheses in original string. Notice that after the removal, we still have to check the result string again.

Code (C++):

class Solution {
bool check(string s, int k){
int c = 0;
for (int i=0;i<s.size();i++){
if (i!=k && s[i] == '('){ c+=1; }
if (i!=k && s[i] == ')'){ c-=1; if (c<0){return false;}}
return c==0;
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_map<string, bool> mp1;
unordered_map<string, bool> mp2;
if (check(s,-1)){
return res;
mp1[s] = true;
while (!mp1.empty()){
bool check_flag = false;
for (auto it1 = mp1.begin();it1!=mp1.end();it1++){
string tmp = it1->first;
for (int i=0; i < tmp.size(); i++){
string tmp2 = tmp;
if (check(tmp, i) && mp2.find(tmp2) == mp2.end()){
check_flag = true;
mp2[tmp2] = true;
if (check_flag){
return res;
mp1 = mp2;
return res;

Code (Python):

class Solution(object):
def check(self, s):
c = 0
for ch in s:
if ch == '(':
c += 1
if ch == ')':
c -= 1
if c < 0:
return False
return c == 0
def dfs(self, s, d_l, d_r, res, hist):
if d_l == 0 and d_r == 0 :
if not s in res and self.check(s):
res[s] = True
elif s == "":
for i in range(len(s)):
if not s[0:i] + s[i+1:] in hist:
hist[s[0:i] + s[i+1:]] = True
if s[i] == '(' and d_l > 0:
self.dfs(s[0:i] + s[i+1:], d_l-1, d_r, res, hist)
if s[i] == ')' and d_r > 0:
self.dfs(s[0:i] + s[i+1:], d_l, d_r-1, res, hist)
def removeInvalidParentheses(self, s):
:type s: str
:rtype: List[str]
res = {}
hist = {}
d_r = 0 # number of '(' to be deleted
d_l = 0 # number of ')' to be deleted
for ch in s:
if ch == '(':
d_l += 1
if ch == ')':
if d_l > 0:
d_l -= 1
d_r += 1
self.dfs(s, d_l, d_r, res, hist)
return res.keys()