-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathproblems.txt
More file actions
1737 lines (1726 loc) · 127 KB
/
problems.txt
File metadata and controls
1737 lines (1726 loc) · 127 KB
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<p> Given a string <i>s</i>, partition <i>s</i> such that every substring of the partition is a palindrome.</p><p> Return the minimum cuts needed for a palindrome partitioning of <i>s</i>.</p><p> For example, given <i>s</i> = <code>"aab"</code>,<br
/> Return <code>1</code> since the palindrome partitioning <code>["aa","b"]</code> could be produced using 1 cut.</p>Solve this problem</a><b>Palindrome Partitioning</b><p> Given a string <i>s</i>, partition <i>s</i> such that every substring of the partition is a palindrome.</p><p> Return all possible palindrome partitioning of <i>s</i>.</p><p> For example, given <i>s</i> = <code>"aab"</code>,<br
/>Return<pre>
[
["aa","b"],
["a","a","b"]
]
</pre></p><b>Surrounded Regions</b><span
class='date' title='2013-02-22 02:32:25'>Feb 22</span><span
class='stats' title='11049 accepted submissions out of 41380 (27%)'>11049 / 41380</span></div><div
class='row-even question-content'><p> Given a 2D board containing <code>'X'</code> and <code>'O'</code>, capture all regions surrounded by <code>'X'</code>.</p><p>A region is captured by flipping all <code>'O'</code>s into <code>'X'</code>s in that surrounded region .</p><p> For example,<br
/><pre>
X X X X
X O O X
X X O X
X O X X
</pre></p><p> After running your function, the board should be:<pre>
X X X X
X X X X
X X X X
X O X X
</pre></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(130, "Surrounded Regions"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_130'>(link to this question)</a></span></div></div><div><div
id='question_129' class='row-odd question-title'><span
class='none'></span><b>Sum Root to Leaf Numbers</b><span
class='date' title='2013-02-19 02:31:58'>Feb 19</span><span
class='stats' title='8344 accepted submissions out of 23632 (35%)'>8344 / 23632</span></div><div
class='row-odd question-content'><p>Given a binary tree containing digits from <code>0-9</code> only, each root-to-leaf path could represent a number.</p><p>An example is the root-to-leaf path <code>1->2->3</code> which represents the number <code>123</code>.</p><p>Find the total sum of all root-to-leaf numbers.</p><p>For example,<pre>
1
/ \
2 3
</pre></p><p> The root-to-leaf path <code>1->2</code> represents the number <code>12</code>.<br
/> The root-to-leaf path <code>1->3</code> represents the number <code>13</code>.</p><p> Return the sum = 12 + 13 = <code>25</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(129, "Sum Root to Leaf Numbers"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_129'>(link to this question)</a></span></div></div><div><div
id='question_128' class='row-even question-title'><span
class='accepted'></span><b>Longest Consecutive Sequence</b><span
class='date' title='2013-02-14 02:45:27'>Feb 14</span><span
class='stats' title='7913 accepted submissions out of 22936 (35%)'>7913 / 22936</span></div><div
class='row-even question-content'><p> Given an unsorted array of integers, find the length of the longest consecutive elements sequence.</p><p> For example,<br
/> Given <code>[100, 4, 200, 1, 3, 2]</code>,<br
/> The longest consecutive elements sequence is <code>[1, 2, 3, 4]</code>. Return its length: <code>4</code>.</p><p> Your algorithm should run in O(<i>n</i>) complexity.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(128, "Longest Consecutive Sequence"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_128'>(link to this question)</a></span></div></div><div><div
id='question_126' class='row-odd question-title'><span
class='none'></span><b>Word Ladder II</b><span
class='date' title='2013-02-11 06:30:11'>Feb 11</span><span
class='stats' title='7646 accepted submissions out of 36433 (21%)'>7646 / 36433</span></div><div
class='row-odd question-content'><p> Given two words (<i>start</i> and <i>end</i>), and a dictionary, find all shortest transformation sequence(s) from <i>start</i> to <i>end</i>, such that:</p><ol><li>Only one letter can be changed at a time</li><li>Each intermediate word must exist in the dictionary</li></ol><p> For example,</p><p> Given:<br
/> <i>start</i> = <code>"hit"</code><br
/> <i>end</i> = <code>"cog"</code><br
/> <i>dict</i> = <code>["hot","dot","dog","lot","log"]</code><br
/></p><p> Return<br
/><pre>
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
</pre></p><p> <b>Note:</b><br
/><ul><li>All words have the same length.</li><li>All words contain only lowercase alphabetic characters.</li></ul></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(126, "Word Ladder II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_126'>(link to this question)</a></span></div></div><div><div
id='question_127' class='row-even question-title'><span
class='none'></span><b>Word Ladder</b><span
class='date' title='2013-02-11 06:26:11'>Feb 11</span><span
class='stats' title='10499 accepted submissions out of 37276 (28%)'>10499 / 37276</span></div><div
class='row-even question-content'><p> Given two words (<i>start</i> and <i>end</i>), and a dictionary, find the length of shortest transformation sequence from <i>start</i> to <i>end</i>, such that:</p><ol><li>Only one letter can be changed at a time</li><li>Each intermediate word must exist in the dictionary</li></ol><p> For example,</p><p> Given:<br
/> <i>start</i> = <code>"hit"</code><br
/> <i>end</i> = <code>"cog"</code><br
/> <i>dict</i> = <code>["hot","dot","dog","lot","log"]</code><br
/></p><p> As one shortest transformation is <code>"hit" -> "hot" -> "dot" -> "dog" -> "cog"</code>,<br
/> return its length <code>5</code>.</p><p> <b>Note:</b><br
/><ul><li>Return 0 if there is no such transformation sequence.</li><li>All words have the same length.</li><li>All words contain only lowercase alphabetic characters.</li></ul></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(127, "Word Ladder"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_127'>(link to this question)</a></span></div></div><div><div
id='question_125' class='row-odd question-title'><span
class='accepted'></span><b>Valid Palindrome</b><span
class='date' title='2013-01-13 01:13:00'>Jan 13</span><span
class='stats' title='7412 accepted submissions out of 23481 (32%)'>7412 / 23481</span></div><div
class='row-odd question-content'><p> Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.</p><p> For example,<br
/> <code>"A man, a plan, a canal: Panama"</code> is a palindrome.<br
/> <code>"race a car"</code> is <i>not</i> a palindrome.</p><p> <b>Note:</b><br
/> Have you consider that the string might be empty? This is a good question to ask during an interview.</p><p> For the purpose of this problem, we define empty string as valid palindrome.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(125, "Valid Palindrome"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_125'>(link to this question)</a></span></div></div><div><div
id='question_124' class='row-even question-title'><span
class='none'></span><b>Binary Tree Maximum Path Sum</b><span
class='date' title='2012-11-08 04:29:15'>Nov 8 '12</span><span
class='stats' title='7312 accepted submissions out of 26768 (27%)'>7312 / 26768</span></div><div
class='row-even question-content'><p> Given a binary tree, find the maximum path sum.</p><p> The path may start and end at any node in the tree.</p><p> For example:<br
/> Given the below binary tree,<pre>
1
/ \
2 3
</pre></p><p> Return <code>6</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(124, "Binary Tree Maximum Path Sum"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_124'>(link to this question)</a></span></div></div><div><div
id='question_123' class='row-odd question-title'><span
class='none'></span><b>Best Time to Buy and Sell Stock III</b><span
class='date' title='2012-11-07 05:24:04'>Nov 7 '12</span><span
class='stats' title='6064 accepted submissions out of 18525 (33%)'>6064 / 18525</span></div><div
class='row-odd question-content'><p>Say you have an array for which the <i>i</i><sup>th</sup> element is the price of a given stock on day <i>i</i>.</p><p>Design an algorithm to find the maximum profit. You may complete at most <i>two</i> transactions.</p><p><b>Note:</b><br
/> You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(123, "Best Time to Buy and Sell Stock III"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_123'>(link to this question)</a></span></div></div><div><div
id='question_122' class='row-even question-title'><span
class='none'></span><b>Best Time to Buy and Sell Stock II</b><span
class='date' title='2012-10-31 02:30:23'>Oct 31 '12</span><span
class='stats' title='6007 accepted submissions out of 11762 (51%)'>6007 / 11762</span></div><div
class='row-even question-content'><p>Say you have an array for which the <i>i</i><sup>th</sup> element is the price of a given stock on day <i>i</i>.</p><p>Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(122, "Best Time to Buy and Sell Stock II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_122'>(link to this question)</a></span></div></div><div><div
id='question_121' class='row-odd question-title'><span
class='none'></span><b>Best Time to Buy and Sell Stock</b><span
class='date' title='2012-10-30 11:30:34'>Oct 30 '12</span><span
class='stats' title='7527 accepted submissions out of 16932 (44%)'>7527 / 16932</span></div><div
class='row-odd question-content'><p>Say you have an array for which the <i>i</i><sup>th</sup> element is the price of a given stock on day <i>i</i>.</p><p>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.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(121, "Best Time to Buy and Sell Stock"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_121'>(link to this question)</a></span></div></div><div><div
id='question_120' class='row-even question-title'><span
class='none'></span><b>Triangle</b><span
class='date' title='2012-10-30 00:02:25'>Oct 30 '12</span><span
class='stats' title='6503 accepted submissions out of 17796 (37%)'>6503 / 17796</span></div><div
class='row-even question-content'><p>Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.</p><p> For example, given the following triangle<br
/><pre>
[
[<font color="red">2</font>],
[<font color="red">3</font>,4],
[6,<font color="red">5</font>,7],
[4,<font color="red">1</font>,8,3]
]
</pre></p><p> The minimum path sum from top to bottom is <code>11</code> (i.e., <font
color="red">2</font> + <font
color="red">3</font> + <font
color="red">5</font> + <font
color="red">1</font> = 11).</p><p> <b>Note:</b><br
/> Bonus point if you are able to do this using only <i>O</i>(<i>n</i>) extra space, where <i>n</i> is the total number of rows in the triangle.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(120, "Triangle"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_120'>(link to this question)</a></span></div></div><div><div
id='question_119' class='row-odd question-title'><span
class='none'></span><b>Pascal's Triangle II</b><span
class='date' title='2012-10-29 00:54:37'>Oct 29 '12</span><span
class='stats' title='5210 accepted submissions out of 12287 (42%)'>5210 / 12287</span></div><div
class='row-odd question-content'><p>Given an index <i>k</i>, return the <i>k</i><sup>th</sup> row of the Pascal's triangle.</p><p> For example, given <i>k</i> = 3,<br
/> Return <code>[1,3,3,1]</code>.</p><p> <b>Note:</b><br
/> Could you optimize your algorithm to use only <i>O</i>(<i>k</i>) extra space?</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(119, "Pascal's Triangle II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_119'>(link to this question)</a></span></div></div><div><div
id='question_118' class='row-even question-title'><span
class='none'></span><b>Pascal's Triangle</b><span
class='date' title='2012-10-28 23:03:39'>Oct 28 '12</span><span
class='stats' title='4857 accepted submissions out of 10981 (44%)'>4857 / 10981</span></div><div
class='row-even question-content'><p>Given <i>numRows</i>, generate the first <i>numRows</i> of Pascal's triangle.</p><p> For example, given <i>numRows</i> = 5,<br
/> Return<pre>
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
</pre></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(118, "Pascal's Triangle"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_118'>(link to this question)</a></span></div></div><div><div
id='question_117' class='row-odd question-title'><span
class='none'></span><b>Populating Next Right Pointers in Each Node II</b><span
class='date' title='2012-10-28 17:54:41'>Oct 28 '12</span><span
class='stats' title='5299 accepted submissions out of 13177 (40%)'>5299 / 13177</span></div><div
class='row-odd question-content'><p>Follow up for problem "<i>Populating Next Right Pointers in Each Node</i>".</p><p>What if the given tree could be any binary tree? Would your previous solution still work?</p><p> <b>Note:</b><ul><li>You may only use constant extra space.</li></ul></p><p> For example,<br
/> Given the following binary tree,<br
/><pre>
1
/ \
2 3
/ \ \
4 5 7
</pre></p><p> After calling your function, the tree should look like:<br
/><pre>
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
</pre></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(117, "Populating Next Right Pointers in Each Node II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_117'>(link to this question)</a></span></div></div><div><div
id='question_116' class='row-even question-title'><span
class='none'></span><b>Populating Next Right Pointers in Each Node</b><span
class='date' title='2012-10-28 17:51:40'>Oct 28 '12</span><span
class='stats' title='5938 accepted submissions out of 12053 (49%)'>5938 / 12053</span></div><div
class='row-even question-content'><p> Given a binary tree<pre>
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
</pre></p><p>Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to <code>NULL</code>.</p><p>Initially, all next pointers are set to <code>NULL</code>.</p><p> <b>Note:</b><ul><li>You may only use constant extra space.</li><li>You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).</li></ul></p><p> For example,<br
/> Given the following perfect binary tree,<br
/><pre>
1
/ \
2 3
/ \ / \
4 5 6 7
</pre></p><p> After calling your function, the tree should look like:<br
/><pre>
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
</pre></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(116, "Populating Next Right Pointers in Each Node"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_116'>(link to this question)</a></span></div></div><div><div
id='question_115' class='row-odd question-title'><span
class='none'></span><b>Distinct Subsequences</b><span
class='date' title='2012-10-19 04:59:20'>Oct 19 '12</span><span
class='stats' title='6266 accepted submissions out of 17972 (35%)'>6266 / 17972</span></div><div
class='row-odd question-content'><p> Given a string <b>S</b> and a string <b>T</b>, count the number of distinct subsequences of <b>T</b> in <b>S</b>.</p><p> A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, <code>"ACE"</code> is a subsequence of <code>"ABCDE"</code> while <code>"AEC"</code> is not).</p><p> Here is an example:<br
/> <b>S</b> = <code>"rabbbit"</code>, <b>T</b> = <code>"rabbit"</code></p><p> Return <code>3</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(115, "Distinct Subsequences"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_115'>(link to this question)</a></span></div></div><div><div
id='question_114' class='row-even question-title'><span
class='accepted'></span><b>Flatten Binary Tree to Linked List</b><span
class='date' title='2012-10-14 23:37:44'>Oct 14 '12</span><span
class='stats' title='7105 accepted submissions out of 21371 (33%)'>7105 / 21371</span></div><div
class='row-even question-content'><p> Given a binary tree, flatten it to a linked list in-place.</p><p> For example,<br
/> Given<pre>
1
/ \
2 5
/ \ \
3 4 6
</pre></p>The flattened tree should look like:<br
/><pre>
1
\
2
\
3
\
4
\
5
\
6
</pre><p
class="showspoilers"><a
href="#" onclick="showSpoilers(this); return false;">click to show hints.</a></p><div
class="spoilers"><b>Hints:</b><p>If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(114, "Flatten Binary Tree to Linked List"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_114'>(link to this question)</a></span></div></div><div><div
id='question_113' class='row-odd question-title'><span
class='none'></span><b>Path Sum II</b><span
class='date' title='2012-10-14 14:49:54'>Oct 14 '12</span><span
class='stats' title='6392 accepted submissions out of 17591 (36%)'>6392 / 17591</span></div><div
class='row-odd question-content'><p> Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.</p>For example:<br
/> Given the below binary tree and <code>sum = 22</code>,<pre>
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
</pre><p> return<br
/><pre>
[
[5,4,11,2],
[5,8,4,5]
]
</pre></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(113, "Path Sum II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_113'>(link to this question)</a></span></div></div><div><div
id='question_112' class='row-even question-title'><span
class='none'></span><b>Path Sum</b><span
class='date' title='2012-10-14 02:33:38'>Oct 14 '12</span><span
class='stats' title='6653 accepted submissions out of 15901 (42%)'>6653 / 15901</span></div><div
class='row-even question-content'><p> Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.</p>For example:<br
/> Given the below binary tree and <code>sum = 22</code>,<pre>
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
</pre><p> return true, as there exist a root-to-leaf path <code>5->4->11->2</code> which sum is 22.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(112, "Path Sum"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_112'>(link to this question)</a></span></div></div><div><div
id='question_111' class='row-odd question-title'><span
class='none'></span><b>Minimum Depth of Binary Tree</b><span
class='date' title='2012-10-10 02:21:40'>Oct 10 '12</span><span
class='stats' title='7310 accepted submissions out of 18192 (40%)'>7310 / 18192</span></div><div
class='row-odd question-content'><p>Given a binary tree, find its minimum depth.</p><p>The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(111, "Minimum Depth of Binary Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_111'>(link to this question)</a></span></div></div><div><div
id='question_110' class='row-even question-title'><span
class='none'></span><b>Balanced Binary Tree</b><span
class='date' title='2012-10-09 03:04:35'>Oct 9 '12</span><span
class='stats' title='7722 accepted submissions out of 18479 (42%)'>7722 / 18479</span></div><div
class='row-even question-content'><p>Given a binary tree, determine if it is height-balanced.</p><p> For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of <i>every</i> node never differ by more than 1.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(110, "Balanced Binary Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_110'>(link to this question)</a></span></div></div><div><div
id='question_109' class='row-odd question-title'><span
class='none'></span><b>Convert Sorted List to Binary Search Tree</b><span
class='date' title='2012-10-03 00:35:00'>Oct 3 '12</span><span
class='stats' title='5768 accepted submissions out of 16298 (35%)'>5768 / 16298</span></div><div
class='row-odd question-content'><p>Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(109, "Convert Sorted List to Binary Search Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_109'>(link to this question)</a></span></div></div><div><div
id='question_108' class='row-even question-title'><span
class='none'></span><b>Convert Sorted Array to Binary Search Tree</b><span
class='date' title='2012-10-02 23:21:00'>Oct 2 '12</span><span
class='stats' title='5459 accepted submissions out of 11289 (48%)'>5459 / 11289</span></div><div
class='row-even question-content'><p>Given an array where elements are sorted in ascending order, convert it to a height balanced BST.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(108, "Convert Sorted Array to Binary Search Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_108'>(link to this question)</a></span></div></div><div><div
id='question_107' class='row-odd question-title'><span
class='accepted'></span><b>Binary Tree Level Order Traversal II</b><span
class='date' title='2012-10-01 22:11:18'>Oct 1 '12</span><span
class='stats' title='4449 accepted submissions out of 10092 (44%)'>4449 / 10092</span></div><div
class='row-odd question-content'><p>Given a binary tree, return the <i>bottom-up level order</i> traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).</p><p> For example:<br
/> Given binary tree <code>{3,9,20,#,#,15,7}</code>,<br
/><pre>
3
/ \
9 20
/ \
15 7
</pre></p><p> return its bottom-up level order traversal as:<br
/><pre>
[
[15,7]
[9,20],
[3],
]
</pre></p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(107, "Binary Tree Level Order Traversal II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_107'>(link to this question)</a></span></div></div><div><div
id='question_106' class='row-even question-title'><span
class='accepted'></span><b>Construct Binary Tree from Inorder and Postorder Traversal</b><span
class='date' title='2012-09-30 22:37:43'>Sep 30 '12</span><span
class='stats' title='4493 accepted submissions out of 12665 (35%)'>4493 / 12665</span></div><div
class='row-even question-content'><p>Given inorder and postorder traversal of a tree, construct the binary tree.</p><p><b>Note:</b><br
/> You may assume that duplicates do not exist in the tree.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(106, "Construct Binary Tree from Inorder and Postorder Traversal"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_106'>(link to this question)</a></span></div></div><div><div
id='question_105' class='row-odd question-title'><span
class='accepted'></span><b>Construct Binary Tree from Preorder and Inorder Traversal</b><span
class='date' title='2012-09-30 21:00:29'>Sep 30 '12</span><span
class='stats' title='4869 accepted submissions out of 14001 (35%)'>4869 / 14001</span></div><div
class='row-odd question-content'><p>Given preorder and inorder traversal of a tree, construct the binary tree.</p><p><b>Note:</b><br
/> You may assume that duplicates do not exist in the tree.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(105, "Construct Binary Tree from Preorder and Inorder Traversal"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_105'>(link to this question)</a></span></div></div><div><div
id='question_104' class='row-even question-title'><span
class='none'></span><b>Maximum Depth of Binary Tree</b><span
class='date' title='2012-09-30 02:40:09'>Sep 30 '12</span><span
class='stats' title='6343 accepted submissions out of 9043 (70%)'>6343 / 9043</span></div><div
class='row-even question-content'><p>Given a binary tree, find its maximum depth.</p><p>The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(104, "Maximum Depth of Binary Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_104'>(link to this question)</a></span></div></div><div><div
id='question_103' class='row-odd question-title'><span
class='accepted'></span><b>Binary Tree Zigzag Level Order Traversal</b><span
class='date' title='2012-09-29 05:09:43'>Sep 29 '12</span><span
class='stats' title='4378 accepted submissions out of 12129 (36%)'>4378 / 12129</span></div><div
class='row-odd question-content'><p>Given a binary tree, return the <i>zigzag level order</i> traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).</p><p> For example:<br
/> Given binary tree <code>{3,9,20,#,#,15,7}</code>,<br
/><pre>
3
/ \
9 20
/ \
15 7
</pre></p><p> return its zigzag level order traversal as:<br
/><pre>
[
[3],
[20,9],
[15,7]
]
</pre></p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(103, "Binary Tree Zigzag Level Order Traversal"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_103'>(link to this question)</a></span></div></div><div><div
id='question_102' class='row-even question-title'><span
class='accepted'></span><b>Binary Tree Level Order Traversal</b><span
class='date' title='2012-09-29 03:19:48'>Sep 29 '12</span><span
class='stats' title='5832 accepted submissions out of 14746 (40%)'>5832 / 14746</span></div><div
class='row-even question-content'><p>Given a binary tree, return the <i>level order</i> traversal of its nodes' values. (ie, from left to right, level by level).</p><p> For example:<br
/> Given binary tree <code>{3,9,20,#,#,15,7}</code>,<br
/><pre>
3
/ \
9 20
/ \
15 7
</pre></p><p> return its level order traversal as:<br
/><pre>
[
[3],
[9,20],
[15,7]
]
</pre></p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(102, "Binary Tree Level Order Traversal"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_102'>(link to this question)</a></span></div></div><div><div
id='question_101' class='row-odd question-title'><span
class='accepted'></span><b>Symmetric Tree</b><span
class='date' title='2012-09-24 02:30:52'>Sep 24 '12</span><span
class='stats' title='7123 accepted submissions out of 14917 (48%)'>7123 / 14917</span></div><div
class='row-odd question-content'><p>Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).</p><p> For example, this binary tree is symmetric:<pre>
1
/ \
2 2
/ \ / \
3 4 4 3
</pre></p><p> But the following is not:<br
/><pre>
1
/ \
2 2
\ \
3 3
</pre></p><p> <b>Note:</b><br
/> Bonus points if you could solve it both recursively and iteratively.</p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(101, "Symmetric Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_101'>(link to this question)</a></span></div></div><div><div
id='question_100' class='row-even question-title'><span
class='accepted'></span><b>Same Tree</b><span
class='date' title='2012-09-03 23:48:41'>Sep 3 '12</span><span
class='stats' title='6423 accepted submissions out of 10037 (64%)'>6423 / 10037</span></div><div
class='row-even question-content'><p> Given two binary trees, write a function to check if they are equal or not.</p><p>Two binary trees are considered equal if they are structurally identical and the nodes have the same value.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(100, "Same Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_100'>(link to this question)</a></span></div></div><div><div
id='question_99' class='row-odd question-title'><span
class='none'></span><b>Recover Binary Search Tree</b><span
class='date' title='2012-09-01 21:00:40'>Sep 1 '12</span><span
class='stats' title='4967 accepted submissions out of 16821 (30%)'>4967 / 16821</span></div><div
class='row-odd question-content'><p> Two elements of a binary search tree (BST) are swapped by mistake.</p><p>Recover the tree without changing its structure.</p><b>Note:</b><br
/> A solution using O(<i>n</i>) space is pretty straight forward. Could you devise a constant space solution?</p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(99, "Recover Binary Search Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_99'>(link to this question)</a></span></div></div><div><div
id='question_98' class='row-even question-title'><span
class='accepted'></span><b>Validate Binary Search Tree</b><span
class='date' title='2012-08-31 20:54:13'>Aug 31 '12</span><span
class='stats' title='6761 accepted submissions out of 19400 (35%)'>6761 / 19400</span></div><div
class='row-even question-content'><p> Given a binary tree, determine if it is a valid binary search tree (BST).</p><p> Assume a BST is defined as follows:<ul><li>The left subtree of a node contains only nodes with keys <b>less than</b> the node's key.</li><li>The right subtree of a node contains only nodes with keys <b>greater than</b> the node's key.</li><li>Both the left and right subtrees must also be binary search trees.</li></ul></p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(98, "Validate Binary Search Tree"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_98'>(link to this question)</a></span></div></div><div><div
id='question_97' class='row-odd question-title'><span
class='none'></span><b>Interleaving String</b><span
class='date' title='2012-08-31 00:40:40'>Aug 31 '12</span><span
class='stats' title='7096 accepted submissions out of 24208 (29%)'>7096 / 24208</span></div><div
class='row-odd question-content'><p> Given <i>s1</i>, <i>s2</i>, <i>s3</i>, find whether <i>s3</i> is formed by the interleaving of <i>s1</i> and <i>s2</i>.</p><p> For example,<br
/> Given:<br
/> <i>s1</i> = <code>"aabcc"</code>,<br
/> <i>s2</i> = <code>"dbbca"</code>,</p><p> When <i>s3</i> = <code>"aadbbcbcac"</code>, return true.<br
/> When <i>s3</i> = <code>"aadbbbaccc"</code>, return false.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(97, "Interleaving String"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_97'>(link to this question)</a></span></div></div><div><div
id='question_95' class='row-even question-title'><span
class='none'></span><b>Unique Binary Search Trees II</b><span
class='date' title='2012-08-27 23:48:50'>Aug 27 '12</span><span
class='stats' title='3664 accepted submissions out of 10952 (33%)'>3664 / 10952</span></div><div
class='row-even question-content'><p>Given <i>n</i>, generate all structurally unique <b>BST's</b> (binary search trees) that store values 1...<i>n</i>.</p><p> For example,<br
/> Given <i>n</i> = 3, your program should return all 5 unique BST's shown below.<pre>
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
</pre></p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(95, "Unique Binary Search Trees II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_95'>(link to this question)</a></span></div></div><div><div
id='question_96' class='row-odd question-title'><span
class='none'></span><b>Unique Binary Search Trees</b><span
class='date' title='2012-08-27 23:47:39'>Aug 27 '12</span><span
class='stats' title='5456 accepted submissions out of 10302 (53%)'>5456 / 10302</span></div><div
class='row-odd question-content'><p>Given <i>n</i>, how many structurally unique <b>BST's</b> (binary search trees) that store values 1...<i>n</i>?</p><p> For example,<br
/> Given <i>n</i> = 3, there are a total of 5 unique BST's.<pre>
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
</pre></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(96, "Unique Binary Search Trees"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_96'>(link to this question)</a></span></div></div><div><div
id='question_94' class='row-even question-title'><span
class='none'></span><b>Binary Tree Inorder Traversal</b><span
class='date' title='2012-08-27 23:47:03'>Aug 27 '12</span><span
class='stats' title='7385 accepted submissions out of 16684 (44%)'>7385 / 16684</span></div><div
class='row-even question-content'><p>Given a binary tree, return the <i>inorder</i> traversal of its nodes' values.</p><p> For example:<br
/> Given binary tree <code>{1,#,2,3}</code>,<br
/><pre>
1
\
2
/
3
</pre></p><p> return <code>[1,3,2]</code>.</p><p><b>Note:</b> Recursive solution is trivial, could you do it iteratively?</p><p
class="showspoilers">confused what <code>"{1,#,2,3}"</code> means? <a
href="#" onclick="showSpoilers(this); return false;">> read more on how binary tree is serialized on OJ.</a></p><div
class="spoilers"><br
/><b>OJ's Binary Tree Serialization:</b><p> The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.</p><p> Here's an example:<br
/><pre>
1
/ \
2 3
/
4
\
5
</pre>The above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(94, "Binary Tree Inorder Traversal"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_94'>(link to this question)</a></span></div></div><div><div
id='question_93' class='row-odd question-title'><span
class='none'></span><b>Restore IP Addresses</b><span
class='date' title='2012-08-08 02:47:56'>Aug 8 '12</span><span
class='stats' title='4543 accepted submissions out of 16957 (27%)'>4543 / 16957</span></div><div
class='row-odd question-content'><p>Given a string containing only digits, restore it by returning all possible valid IP address combinations.</p><p> For example:<br
/> Given <code>"25525511135"</code>,</p><p> return <code>["255.255.11.135", "255.255.111.35"]</code>. (Order does not matter)</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(93, "Restore IP Addresses"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_93'>(link to this question)</a></span></div></div><div><div
id='question_92' class='row-even question-title'><span
class='none'></span><b>Reverse Linked List II</b><span
class='date' title='2012-06-27 21:13:28'>Jun 27 '12</span><span
class='stats' title='5508 accepted submissions out of 18773 (29%)'>5508 / 18773</span></div><div
class='row-even question-content'><p> Reverse a linked list from position <i>m</i> to <i>n</i>. Do it in-place and in one-pass.</p><p> For example:<br
/> Given <code>1->2->3->4->5->NULL</code>, <i>m</i> = 2 and <i>n</i> = 4,</p><p> return <code>1->4->3->2->5->NULL</code>.</p><p> <b>Note:</b><br
/> Given <i>m</i>, <i>n</i> satisfy the following condition:<br
/> 1 ? <i>m</i> ? <i>n</i> ? length of list.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(92, "Reverse Linked List II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_92'>(link to this question)</a></span></div></div><div><div
id='question_90' class='row-odd question-title'><span
class='none'></span><b>Subsets II</b><span
class='date' title='2012-06-25 22:32:45'>Jun 25 '12</span><span
class='stats' title='4769 accepted submissions out of 13419 (36%)'>4769 / 13419</span></div><div
class='row-odd question-content'><p> Given a collection of integers that might contain duplicates, <i>S</i>, return all possible subsets.</p><p><b>Note:</b><br
/><ul><li>Elements in a subset must be in non-descending order.</li><li>The solution set must not contain duplicate subsets.</li></ul></p><p> For example,<br
/> If <b><i>S</i></b> = <code>[1,2,2]</code>, a solution is:</p><pre>
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
</pre><a
href='#' onclick='clearSavedJudgeCode(); setJudge(90, "Subsets II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_90'>(link to this question)</a></span></div></div><div><div
id='question_91' class='row-even question-title'><span
class='none'></span><b>Decode Ways</b><span
class='date' title='2012-06-25 21:13:00'>Jun 25 '12</span><span
class='stats' title='6747 accepted submissions out of 26583 (25%)'>6747 / 26583</span></div><div
class='row-even question-content'><p> A message containing letters from <code>A-Z</code> is being encoded to numbers using the following mapping:</p><pre>
'A' -> 1
'B' -> 2
...
'Z' -> 26
</pre><p> Given an encoded message containing digits, determine the total number of ways to decode it.</p><p> For example,<br
/> Given encoded message <code>"12"</code>,
it could be decoded as <code>"AB"</code> (1 2) or <code>"L"</code> (12).</p><p> The number of ways decoding <code>"12"</code> is 2.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(91, "Decode Ways"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_91'>(link to this question)</a></span></div></div><div><div
id='question_89' class='row-odd question-title'><span
class='none'></span><b>Gray Code</b><span
class='date' title='2012-05-20 16:20:00'>May 20 '12</span><span
class='stats' title='3727 accepted submissions out of 8371 (45%)'>3727 / 8371</span></div><div
class='row-odd question-content'><p>The gray code is a binary numeral system where two successive values differ in only one bit.</p><p>Given a non-negative integer <i>n</i> representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.</p><p>For example, given <i>n</i> = 2, return <code>[0,1,3,2]</code>. Its gray code sequence is:</p><pre>
00 - 0
01 - 1
11 - 3
10 - 2
</pre><p><b>Note:</b><br
/> For a given <i>n</i>, a gray code sequence is not uniquely defined.</p><p>For example, <code>[0,2,3,1]</code> is also a valid gray code sequence according to the above definition.</p><p>For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(89, "Gray Code"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_89'>(link to this question)</a></span></div></div><div><div
id='question_88' class='row-even question-title'><span
class='accepted'></span><b>Merge Sorted Array</b><span
class='date' title='2012-05-20 16:19:00'>May 20 '12</span><span
class='stats' title='6055 accepted submissions out of 13640 (44%)'>6055 / 13640</span></div><div
class='row-even question-content'><p>Given two sorted integer arrays A and B, merge B into A as one sorted array.</p><p> <b>Note:</b><br
/> You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are <i>m</i> and <i>n</i> respectively.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(88, "Merge Sorted Array"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_88'>(link to this question)</a></span></div></div><div><div
id='question_87' class='row-odd question-title'><span
class='none'></span><b>Scramble String</b><span
class='date' title='2012-04-30 12:17:01'>Apr 30 '12</span><span
class='stats' title='4644 accepted submissions out of 14931 (31%)'>4644 / 14931</span></div><div
class='row-odd question-content'><p> Given a string <i>s1</i>, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.</p><p> Below is one possible representation of <i>s1</i> = <code>"great"</code>:</p><pre>
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
</pre><p> To scramble the string, we may choose any non-leaf node and swap its two children.</p><p> For example, if we choose the node <code>"gr"</code> and swap its two children, it produces a scrambled string <code>"rgeat"</code>.</p><pre>
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
</pre><p> We say that <code>"rgeat"</code> is a scrambled string of <code>"great"</code>.</p><p> Similarly, if we continue to swap the children of nodes <code>"eat"</code> and <code>"at"</code>, it produces a scrambled string <code>"rgtae"</code>.</p><pre>
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
</pre><p> We say that <code>"rgtae"</code> is a scrambled string of <code>"great"</code>.</p><p> Given two strings <i>s1</i> and <i>s2</i> of the same length, determine if <i>s2</i> is a scrambled string of <i>s1</i>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(87, "Scramble String"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_87'>(link to this question)</a></span></div></div><div><div
id='question_86' class='row-even question-title'><span
class='none'></span><b>Partition List</b><span
class='date' title='2012-04-30 12:14:48'>Apr 30 '12</span><span
class='stats' title='5164 accepted submissions out of 15877 (33%)'>5164 / 15877</span></div><div
class='row-even question-content'><p>Given a linked list and a value <i>x</i>, partition it such that all nodes less than <i>x</i> come before nodes greater than or equal to <i>x</i>.</p><p> You should preserve the original relative order of the nodes in each of the two partitions.</p><p> For example,<br
/> Given <code>1->4->3->2->5->2</code> and <i>x</i> = 3,<br
/> return <code>1->2->2->4->3->5</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(86, "Partition List"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_86'>(link to this question)</a></span></div></div><div><div
id='question_85' class='row-odd question-title'><span
class='none'></span><b>Maximal Rectangle</b><span
class='date' title='2012-04-24 02:08:18'>Apr 24 '12</span><span
class='stats' title='3792 accepted submissions out of 13475 (28%)'>3792 / 13475</span></div><div
class='row-odd question-content'><p> Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(85, "Maximal Rectangle"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_85'>(link to this question)</a></span></div></div><div><div
id='question_84' class='row-even question-title'><span
class='none'></span><b>Largest Rectangle in Histogram</b><span
class='date' title='2012-04-23 00:20:14'>Apr 23 '12</span><span
class='stats' title='6550 accepted submissions out of 21145 (31%)'>6550 / 21145</span></div><div
class='row-even question-content'><p> Given <i>n</i> non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.</p><p> <img
src="http://www.leetcode.com/wp-content/uploads/2012/04/histogram.png" /><br
/><p
style="font-size: 11px">Above is a histogram where width of each bar is 1, given height = <code>[2,1,5,6,2,3]</code>.</p></p><p> <img
src="http://www.leetcode.com/wp-content/uploads/2012/04/histogram_area.png" /><br
/><p
style="font-size: 11px">The largest rectangle is shown in the shaded area, which has area = <code>10</code> unit.</p></p><p> For example,<br
/> Given height = <code>[2,1,5,6,2,3]</code>,<br
/> return <code>10</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(84, "Largest Rectangle in Histogram"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_84'>(link to this question)</a></span></div></div><div><div
id='question_82' class='row-odd question-title'><span
class='none'></span><b>Remove Duplicates from Sorted List II</b><span
class='date' title='2012-04-22 14:41:38'>Apr 22 '12</span><span
class='stats' title='5564 accepted submissions out of 16823 (33%)'>5564 / 16823</span></div><div
class='row-odd question-content'><p> Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only <i>distinct</i> numbers from the original list.</p><p> For example,<br
/> Given <code>1->2->3->3->4->4->5</code>, return <code>1->2->5</code>.<br
/> Given <code>1->1->1->2->3</code>, return <code>2->3</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(82, "Remove Duplicates from Sorted List II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_82'>(link to this question)</a></span></div></div><div><div
id='question_83' class='row-even question-title'><span
class='none'></span><b>Remove Duplicates from Sorted List</b><span
class='date' title='2012-04-22 14:40:36'>Apr 22 '12</span><span
class='stats' title='6081 accepted submissions out of 11943 (51%)'>6081 / 11943</span></div><div
class='row-even question-content'><p> Given a sorted linked list, delete all duplicates such that each element appear only <i>once</i>.</p><p> For example,<br
/> Given <code>1->1->2</code>, return <code>1->2</code>.<br
/> Given <code>1->1->2->3->3</code>, return <code>1->2->3</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(83, "Remove Duplicates from Sorted List"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_83'>(link to this question)</a></span></div></div><div><div
id='question_81' class='row-odd question-title'><span
class='none'></span><b>Search in Rotated Sorted Array II</b><span
class='date' title='2012-04-20 00:33:03'>Apr 20 '12</span><span
class='stats' title='4077 accepted submissions out of 10753 (38%)'>4077 / 10753</span></div><div
class='row-odd question-content'><p>Follow up for "Search in Rotated Sorted Array":<br
/> What if <i>duplicates</i> are allowed?</p><p>Would this affect the run-time complexity? How and why?</p><p>Write a function to determine if a given target is in the array.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(81, "Search in Rotated Sorted Array II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_81'>(link to this question)</a></span></div></div><div><div
id='question_80' class='row-even question-title'><span
class='none'></span><b>Remove Duplicates from Sorted Array II</b><span
class='date' title='2012-04-19 23:12:29'>Apr 19 '12</span><span
class='stats' title='4602 accepted submissions out of 11239 (41%)'>4602 / 11239</span></div><div
class='row-even question-content'><p> Follow up for "Remove Duplicates":<br
/> What if duplicates are allowed at most <i>twice</i>?</p><p> For example,<br
/> Given sorted array A = <code>[1,1,1,2,2,3]</code>,</p><p> Your function should return length = <code>5</code>, and A is now <code>[1,1,2,2,3]</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(80, "Remove Duplicates from Sorted Array II"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_80'>(link to this question)</a></span></div></div><div><div
id='question_79' class='row-odd question-title'><span
class='none'></span><b>Word Search</b><span
class='date' title='2012-04-18 21:24:24'>Apr 18 '12</span><span
class='stats' title='6762 accepted submissions out of 21892 (31%)'>6762 / 21892</span></div><div
class='row-odd question-content'><p> Given a 2D board and a word, find if the word exists in the grid.</p><p> The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.</p><p> For example,<br
/> Given <b>board</b> =<pre>
[
["ABCE"],
["SFCS"],
["ADEE"]
]
</pre><b>word</b> = <code>"ABCCED"</code>, -> returns <code>true</code>,<br
/> <b>word</b> = <code>"SEE"</code>, -> returns <code>true</code>,<br
/> <b>word</b> = <code>"ABCB"</code>, -> returns <code>false</code>.<br
/></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(79, "Word Search"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_79'>(link to this question)</a></span></div></div><div><div
id='question_78' class='row-even question-title'><span
class='none'></span><b>Subsets</b><span
class='date' title='2012-04-18 21:21:48'>Apr 18 '12</span><span
class='stats' title='6226 accepted submissions out of 16269 (38%)'>6226 / 16269</span></div><div
class='row-even question-content'><p> Given a set of distinct integers, <i>S</i>, return all possible subsets.</p><p><b>Note:</b><br
/><ul><li>Elements in a subset must be in non-descending order.</li><li>The solution set must not contain duplicate subsets.</li></ul></p><p> For example,<br
/> If <b><i>S</i></b> = <code>[1,2,3]</code>, a solution is:</p><pre>
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
</pre><a
href='#' onclick='clearSavedJudgeCode(); setJudge(78, "Subsets"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_78'>(link to this question)</a></span></div></div><div><div
id='question_77' class='row-odd question-title'><span
class='none'></span><b>Combinations</b><span
class='date' title='2012-04-18 21:20:58'>Apr 18 '12</span><span
class='stats' title='5708 accepted submissions out of 14105 (40%)'>5708 / 14105</span></div><div
class='row-odd question-content'><p> Given two integers <i>n</i> and <i>k</i>, return all possible combinations of <i>k</i> numbers out of 1 ... <i>n</i>.</p><p> For example,<br
/> If <i>n</i> = 4 and <i>k</i> = 2, a solution is:</p><pre>
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
</pre><a
href='#' onclick='clearSavedJudgeCode(); setJudge(77, "Combinations"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_77'>(link to this question)</a></span></div></div><div><div
id='question_76' class='row-even question-title'><span
class='none'></span><b>Minimum Window Substring</b><span
class='date' title='2012-04-15 15:25:25'>Apr 15 '12</span><span
class='stats' title='4849 accepted submissions out of 20420 (24%)'>4849 / 20420</span></div><div
class='row-even question-content'><p> Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).</p><p> For example,<br
/> <b>S</b> = <code>"ADOBECODEBANC"</code><br
/> <b>T</b> = <code>"ABC"</code><br
/></p><p> Minimum window is <code>"BANC"</code>.</p><p> <b>Note:</b><br
/> If there is no such window in S that covers all characters in T, return the emtpy string <code>""</code>.</p><p> If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(76, "Minimum Window Substring"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_76'>(link to this question)</a></span></div></div><div><div
id='question_75' class='row-odd question-title'><span
class='accepted'></span><b>Sort Colors</b><span
class='date' title='2012-04-09 01:24:46'>Apr 9 '12</span><span
class='stats' title='5950 accepted submissions out of 14106 (42%)'>5950 / 14106</span></div><div
class='row-odd question-content'><p> Given an array with <i>n</i> 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.</p><p> Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.</p><p> <b>Note:</b><br
/> You are not suppose to use the library's sort function for this problem.</p><p
class="showspoilers"><a
href="#" onclick="showSpoilers(this); return false;">click to show follow up.</a></p><div
class="spoilers"><p><b>Follow up:</b><br
/> A rather straight forward solution is a two-pass algorithm using counting sort.<br
/> 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.</p><p>Could you come up with an one-pass algorithm using only constant space?<br
/></p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(75, "Sort Colors"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_75'>(link to this question)</a></span></div></div><div><div
id='question_74' class='row-even question-title'><span
class='accepted'></span><b>Search a 2D Matrix</b><span
class='date' title='2012-04-07 01:50:51'>Apr 7 '12</span><span
class='stats' title='5288 accepted submissions out of 11782 (45%)'>5288 / 11782</span></div><div
class='row-even question-content'><p>Write an efficient algorithm that searches for a value in an <i>m</i> x <i>n</i> matrix. This matrix has the following properties:</p><p><ul><li>Integers in each row are sorted from left to right.</li><li>The first integer of each row is greater than the last integer of the previous row.</li></ul></p><p> For example,</p><p> Consider the following matrix:</p><pre>
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
</pre><p>Given <b>target</b> = <code>3</code>, return <code>true</code>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(74, "Search a 2D Matrix"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_74'>(link to this question)</a></span></div></div><div><div
id='question_73' class='row-odd question-title'><span
class='none'></span><b>Set Matrix Zeroes</b><span
class='date' title='2012-04-06 03:10:45'>Apr 6 '12</span><span
class='stats' title='4561 accepted submissions out of 10629 (43%)'>4561 / 10629</span></div><div
class='row-odd question-content'><p> Given a <i>m</i> x <i>n</i> matrix, if an element is 0, set its entire row and column to 0. Do it in place.</p><p
class="showspoilers"><a
href="#" onclick="showSpoilers(this); return false;">click to show follow up.</a></p><div
class="spoilers"><b>Follow up:</b><p> Did you use extra space?<br
/> A straight forward solution using O(<i>m</i><i>n</i>) space is probably a bad idea.<br
/> A simple improvement uses O(<i>m</i> + <i>n</i>) space, but still not the best solution.<br
/> Could you devise a constant space solution?</p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(73, "Set Matrix Zeroes"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_73'>(link to this question)</a></span></div></div><div><div
id='question_72' class='row-even question-title'><span
class='accepted'></span><b>Edit Distance</b><span
class='date' title='2012-04-04 21:05:54'>Apr 4 '12</span><span
class='stats' title='5171 accepted submissions out of 14897 (35%)'>5171 / 14897</span></div><div
class='row-even question-content'><p> Given two words <i>word1</i> and <i>word2</i>, find the minimum number of steps required to convert <i>word1</i> to <i>word2</i>. (each operation is counted as 1 step.)</p><p> You have the following 3 operations permitted on a word:</p><p> a) Insert a character<br
/> b) Delete a character<br
/> c) Replace a character<br
/></p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(72, "Edit Distance"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_72'>(link to this question)</a></span></div></div><div><div
id='question_71' class='row-odd question-title'><span
class='none'></span><b>Simplify Path</b><span
class='date' title='2012-04-04 00:33:28'>Apr 4 '12</span><span
class='stats' title='3445 accepted submissions out of 13388 (26%)'>3445 / 13388</span></div><div
class='row-odd question-content'><p>Given an absolute path for a file (Unix-style), simplify it.</p><p>For example,<br
/> <b>path</b> = <code>"/home/"</code>, => <code>"/home"</code><br
/> <b>path</b> = <code>"/a/./b/../../c/"</code>, => <code>"/c"</code><br
/></p><p
class="showspoilers"><a
href="#" onclick="showSpoilers(this); return false;">click to show corner cases.</a></p><div
class="spoilers"><b>Corner Cases:</b><p><ul><li>Did you consider the case where <b>path</b> = <code>"/../"</code>?<br
/> In this case, you should return <code>"/"</code>.</li><li>Another corner case is the path might contain multiple slashes <code>'/'</code> together, such as <code>"/home//foo/"</code>.<br
/> In this case, you should ignore redundant slashes and return <code>"/home/foo"</code>.</li></p></div><a
href='#' onclick='clearSavedJudgeCode(); setJudge(71, "Simplify Path"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_71'>(link to this question)</a></span></div></div><div><div
id='question_70' class='row-even question-title'><span
class='accepted'></span><b>Climbing Stairs</b><span
class='date' title='2012-04-03 22:00:37'>Apr 3 '12</span><span
class='stats' title='6879 accepted submissions out of 13083 (53%)'>6879 / 13083</span></div><div
class='row-even question-content'><p>You are climbing a stair case. It takes <i>n</i> steps to reach to the top.</p><p>Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(70, "Climbing Stairs"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_70'>(link to this question)</a></span></div></div><div><div
id='question_69' class='row-odd question-title'><span
class='none'></span><b>Sqrt(x)</b><span
class='date' title='2012-04-03 21:59:57'>Apr 3 '12</span><span
class='stats' title='8283 accepted submissions out of 28329 (29%)'>8283 / 28329</span></div><div
class='row-odd question-content'><p>Implement <code>int sqrt(int x)</code>.</p><p>Compute and return the square root of <i>x</i>.</p><a
href='#' onclick='clearSavedJudgeCode(); setJudge(69, "Sqrt(x)"); openConsole(); return false;'>? Solve this problem</a><span
class='link-question'><a
href='#question_69'>(link to this question)</a></span></div></div><div><div
id='question_68' class='row-even question-title'><span
class='none'></span><b>Text Justification</b><span
class='date' title='2012-04-03 07:28:18'>Apr 3 '12</span><span
class='stats' title='3100 accepted submissions out of 15986 (19%)'>3100 / 15986</span></div><div
class='row-even question-content'><p> Given an array of words and a length <i>L</i>, format the text such that each line has exactly <i>L</i> characters and is fully (left and right) justified.</p><p> You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces <code>' '</code> when necessary so that each line has exactly <i>L</i> characters.</p><p> Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.</p><p> For the last line of text, it should be left justified and no extra space is inserted between words.</p><p> For example,<br
/> <b>words</b>: <code>["This", "is", "an", "example", "of", "text", "justification."]</code><br
/> <b>L</b>: <code>16</code>.</p><p> Return the formatted lines as:<br
/><pre>
[
"This is an",
"example of text",
"justification. "
]
</pre></p><p> <b>Note:</b> Each word is guaranteed not to exceed <i>L</i> in length.</p><p
class="showspoilers"><a
href="#" onclick="showSpoilers(this); return false;">click to show corner cases.</a></p><div
class="spoilers"><b>Corner Cases:</b><p><ul><li>A line other than the last line might contain only one word. What should you do in this case?<br