📓 Algorithms Search Ctrl + K

0. Int roduct ion t o Dat a St ruct ures & Algorit hms wit h Leet code
1. Dut ch Flags Problem
2. List Part it oning
3. Count ers
4. Majorit y Vot e
5. Removing Parent heses
6. Remove Duplicat es from Sort ed Array
7. Mat hs
8. Lone Int eger
9. Pigeonhole
10. Check If N and It s Double Exist
11. Find Numbers wit h Even Number of Digit s
12. Two Point ers
13. Remove Element
14. Replace Element s wit h Great est Element on Right Side
15. Valid Mount ain Array
16. Sort Array by Parit y
17. Squares of a Sort ed Array
18. Max Consecut ive Ones
19. Sliding Window
20. Max Consecut ive Ones 3
21. St acks
22. Balanced Bracket s
23. General St rings & Arrays
24. Move Zeros
25. Unique Element s
26. Merge Sort ed Array
27. Mat rices
28. Valid Square
29. Mat rix Search Sequel
30. Unt it led
31. Int roduct ion
32. Backt racking
33. Permut at ions
34. Int roduct ion
35. Minimum (Maximum) Pat h t o Reach a Target
36. Min Cost Climbing St airs
37. Coin Change
38. Minimum Pat h Sum
39. Triangle
40. Minimum Cost t o Move Chips t o The Same Posit ion
41. Consecut ive Charact ers
42. Perfect Squares
43. Dist inct Ways
44. Climbing St airs
45. Unique Pat hs
46. Number of Dice Rolls wit h Target Sum
47. Merging Int ervals
48. Minimum Cost Tree From Leaf Values
49. DP on St rings
50. Levensht ein Dist ance
51. Longest Common Subsequence
52. Int roduct ion
53. First Bad Version
54. Sqrt (x)
55. Search Insert Posit ion
56. Advanced
57. KoKo Eat ing Banana
58. Capacit y t o Ship Packages wit hin D Days
59. Minimum Number of Days t o Make m Bouquet s
60. Split array largest sum
61. Minimum Number of Days t o Make m Bouquet s
62. Koko Eat ing Bananas
63. Find K-t h Smallest Pair Dist ance
64. Ugly Number 3
65. Find t he Smallest Divisor Given a Threshold
66. Kt h smallest number in mult iplicat ion t able
67. Binary Trees
68. Merging Binary Trees
69. Binary Tree Preorder Traversal
70. Binary Tree Post order Traversal
71. Binary Tree Level Order Traversal
72. Binary Tree Inorder Traversal
73. Symmet ric Tree
74. Populat ing Next Right Point ers in Each Node
75. Populat ing Next Right Point ers in Each Node II
76. 106. Const ruct Binary Tree from Inorder and Post order Traversal
77. Serialise and Deserialise a Linked List
78. Maximum Dept h of Binary Tree
79. Lowest Common Ancest or of a Binary Tree
80. n-ary Trees
81. Unt it led
82. Minimum Height Trees
83. Binary Search Trees
84. Count ing Maximal Value Root s in Binary Tree
85. Count BST nodes in a range
86. Invert a Binary Tree
87. Maximum Difference Bet ween Node and Ancest or
88. Binary Tree Tilt
89. Pract ice
90. What is a Linked List ?
91. Add Two Numbers
92. Add Two Numbers 2
93. Reverse a Linked List
94. Tort oise & Hare Algorit hm
95. Middle of t he Linked List
96. Int roduct ion
97. Uncomplet ed
98. Minimum Cost For Ticket s
99. Minimum Falling Pat h Sum
Introduction to Data Structures
& Algorithms with Leetcode
You can read this here ht t ps://beesec.git book.io/algorit hms/

Int roduct ion t o Dat a St ruct ures & Algorit hms wit h Leet code
Algorithms

Git Hub repo is here: ht t ps://git hub.com/bee-san/Algorit hms

Welcome t o Bee's guide t o dat ast ruct ures and algorit hms! This is based on
ht t ps://git hub.com/guyinat uxedo/night mare

What you need to know

• Learn dat a st ruct ures & algorit hms (DS&A) using leet code

• Only learn DS&A t hat is used in real world

• Learn why it works, not just how.

• Sort ed by how likely it is t o show up in an int erview and how vit al t hat knowledge is t o
underst anding ot her DS&A.

• The problems are most ly medium - hards, I t ry t o not include easy problems unless t hey are t he
first problem in a cat egory.

This is a course on dat ast ruct ures and algorit hms based around leet code problems. Learn DS&A via
problems, wit h lengt hy explanat ions.

This guide is ordered by how likely it is for t hat dat ast ruct ure / algorit hm t o show up in an int erview
and how vit al t hat knowledge is t o underst anding ot her dat a st ruct ures / algorit hms.

Each sect ion will lead wit h a leet code st yle problem, and end wit h problems you can do on your own.
This way, you only ever learn what is relevant .

All code will be in Pyt hon due t o how easy it is t o read. If you want t o cont ribut e more code, feel free
t o. This is on Git Hub aft er all!

If you're okay wit h Pyt hon, but want t o learn t he advanced st uff check out my ot her book
ht t ps://git hub.com/bee-san/Pyt hon-Zero-t o-Hero

I also have my own blog, ht t ps://skerrit t .blog t hat you may enjoy.
Resources
You should roughly know t hese t hings. I have linked t o some of my own resources for you t o learn t hem:

• Pyt hon (Not an expert , you can use ot her languages or cont ribut e more languages)

• Big O not at ion (not an expert , just t he basics)

For ot her resources you should see:

• CTCI

• MIT 6.006

How to contribute
• Explain t hings more easily

• Look t hrough my Not Done Yet sect ion and complet e / improve t hem!

Why Leetcode and not X, Y, Z platform?

1. Everyone knows Leet code

2. Leet code discussion board is popping, and t here's many Yout ube videos about each plat form

3. AlgoExpert is not paying me t o t ell you t hat t he scariest t hing in t he world is not knowing how t o
invert a binary t ree in a coding int erview yet.

4. HackerRank's problems are t oo wordy for me t o copy & past e.

5. Companies use Leet code

6. Honest ly if any ot her coding company came along and paid me t o advert ise t heir product I would
it 's just I used Leet code. Deciding on what the best platform to use is another form of
procrastination. I just picked t he first one I saw and went wit h it .

Important Notes
• Not all solut ions are made by me (bee-san). This book is 100% open source and somet imes people
on Leet code forums have way bet t t er solut ions t han I do.

Next
Dut ch Flags Problem
Last updat ed 4 years ago

Dutch Flags Problem

Dut ch nat ional flag problem
Wikipedia

The Dutch national flag problem [1] is a comput er science programming problem proposed by Edsger
Dijkst ra.[2] The flag of t he Net herlands consist s of t hree colors: red, whit e and blue. Given balls of
t hese t hree colors arranged randomly in a line (it does not mat t er how many balls t here are), t he t ask is
t o arrange t hem such t hat all balls of t he same color are t oget her and t heir collect ive color groups are
in t he correct order.

The solut ion t o t his problem is of int erest for designing sort ing algorit hms; in part icular, variant s of t he
quicksort algorit hm t hat must be robust t o repeat ed element s may use a t hree-way part it ioning
funct ion t hat groups it ems less t han a given key (red), equal t o t he key (whit e) and great er t han t he key
(blue). Several solut ions exist t hat have varying performance charact erist ics, t ailored t o sort ing arrays
wit h eit her small or large numbers of repeat ed element s

Previous
Next
Int roduct ion t o Dat a St ruct ures &
List Part it oning
Algorit hms wit h Leet code

Last updat ed 4 years ago

List Partitoning
ht t ps://binarysearch.com/problems/List -Part it ioning

^^ Not leet code, but t he problem was nice.

Question Answer

Given a list of st rings strs , cont aining t he st rings "red" , "green" and "blue" , part it ion t he
list so t hat t he red come before green, which come before blue.

Constraints

• n ≤ 100,000 where n is t he lengt h of strs .

This should be done in \mat hcal{O}(n)O(n) t ime.

Bonus: Can you do it in \mat hcal{O}(1)O(1) space? That is, can you do it by only rearranging t he list
(i.e. wit hout creat ing any new st rings)?

Example 1

Input

strs = ["green", "blue", "red", "red"]

Output

["red", "red", "green", "blue"]

Previous Next
Dut ch Flags Problem Count ers

Last updat ed 4 years ago

Counters
Here's anot her common pat t ern you may see.

counter = 0
for i in n: # n is a list of items
if condition(i):
counter += 1
else:
counter -= 1

We have a single count er and we increment it / decrement it based on a condit ion.

We keep a count er and we perform t hings based on t his count er.

Anot her example is:

counter = 0
while counter < len(s):
if condition(s[counter]):
counter += 1

Previous Next
List Part it oning Majorit y Vot e

Last updat ed 4 years ago

Majority Vote
ht t ps://leet code.com/problems/majorit y-element /

Question Answer

Given an array of size n, find t he majorit y element . The majorit y element is t he element t hat
appears more than ⌊ n/2 ⌋ t imes.

You may assume t hat t he array is non-empt y and t he majorit y element always exist in t he array.

Example 1:

Input: [3,2,3]
Output: 3

Previous Next
Count ers Removing Parent heses

Last updat ed 4 years ago

Removing Parentheses
ht t ps://binarysearch.com/problems/Removing-Parent heses

I know it 's not Leet code please don't kill me. I was in a compet it ion and I t hought t his was
neat . Couldn't find t he leet code alt ernat ive.

Question Answer

Given a st ring of parent heses s , ret urn t he minimum number of parent heses t o be removed t o
make t he st ring valid (i.e. each open parent hesis is event ually closed).

For example, given t he st ring "()())()" , you should ret urn 1. Given t he st ring ")(" , you should
ret urn 2, since we must remove all of t hem.

Previous Next
Majorit y Vot e Remove Duplicat es from Sort ed Array

Last updat ed 4 years ago

Remove Duplicates from Sorted Array
ht t ps://leet code.com/problems/remove-duplicat es-from-sort ed-array/

If a quest ion ment ions a specific propert y about t he input dat a, oft en t he opt imal solut ion will make
use of t his propert y.

In t his case, we are t old t hat t he array is sort ed. That means our opt imal solut ion must make use of t he
fact it is sort ed.

List en carefully t o what your int erviewer is t elling you, every word might come in handy.

Question Answer

Given a sort ed array nums, remove t he duplicat es in-place such t hat each element appears only
once and ret urns t he new lengt h.

Do not allocat e ext ra space for anot her array, you must do t his by modifying the input array in-
place wit h O(1) ext ra memory.

Previous Next
Removing Parent heses Mat hs

Last updat ed 4 years ago

Maths
Lone Int eger Pigeonhole

Find Numbers wit h Even Number of

Check If N and It s Double Exist
Digit s

Previous Next
Remove Duplicat es from Sort ed Array Lone Int eger

Last updat ed 4 years ago

Lone Integer
ht t ps://binarysearch.com/problems/Lone-Int eger

Question Answer

You are given a list of int egers nums where each int eger occurs exact ly t hree t imes except for
one which occurs once. Ret urn t he lone int eger.

Bonus: can you do it in O(1) space?

Constraints

• n ≤ 10,000 where n is lengt h of nums

Example 1

Input

nums = [2, 2, 2, 9, 5, 5, 5]

Previous Next
Mat hs Pigeonhole

Last updat ed 4 years ago

Pigeonhole
ht t ps://binarysearch.com/problems/Pigeonhole

Question Answer

You are given a list nums of lengt h n + 1 picked from t he range 1, 2, ..., n . By t he
pigeonhole principle, t here must be a duplicat e. Find and ret urn it . There is guarant eed t o be
exact ly one duplicat e.

Bonus: Can you do t his in linear t ime and const ant space?

Previous Next
Lone Int eger Check If N and It s Double Exist

Last updat ed 4 years ago

Check If N and Its Double Exist
ht t ps://leet code.com/problems/check-if-n-and-it s-double-exist /

Question Answer

Given an array arr of int egers, check if t here exist s t wo int egers N and M such t hat N is
t he double of M ( i.e. N = 2 * M ).

More formally check if t here exist s t wo indices i and j such t hat :

• i != j

• 0 <= i, j < arr.length

• arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]

Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Next
Previous
Find Numbers wit h Even Number
Pigeonhole
of Digit s

Last updat ed 4 years ago

Find Numbers with Even Number of Digits
ht t ps://leet code.com/problems/find-numbers-wit h-even-number-of-digit s/

Modulus
To find out whet her a number is even or not , we use t he modulus operat or. Y % X implies t hat Y is
divided by X, and what ever t he remainder is will be t he result .

If we divide a number by 2, and it 's odd we will have a remainder.

6 % 2 == 0 # False

The number being divided is called t he dividend, and t he number t hat divides t he dividend is called t he
divisor.

We can also use modulus for ot her t hings, such as checking if a number is odd. Or t urning a list int o a
loop. If we have a list t hat is size 6, and we want t o it erat e 9 numbers but have it loop back around, we
can use modulus for t his.

6 % 9 = 3, which means our index will be at 3.

Question Answer

Given an array nums of int egers, ret urn how many of t hem cont ain an even number of digit s.

Input: nums = [12,345,2,6,7896]

Output: 2
Explanation:
12 contains 2 digits (even number of digits).
345 contains 3 digits (odd number of digits).
2 contains 1 digit (odd number of digits).
6 contains 1 digit (odd number of digits).
7896 contains 4 digits (even number of digits).
Therefore only 12 and 7896 contain an even number of digits.

Previous Next
Check If N and It s Double Exist Two Point ers
Last updat ed 4 years ago

Two Pointers
Replace Element s wit h Great est
Remove Element
Element on Right Side

Valid Mount ain Array Sort Array by Parit y

 Squares of a Sort ed Array Max Consecut ive Ones

Previous
Next
Find Numbers wit h Even Number
Remove Element
of Digit s

Last updat ed 4 years ago

Remove Element
ht t ps://leet code.com/problems/remove-element /

Question Answer

Given an array nums and a value val, remove all inst ances of t hat value in-place and ret urn t he new
lengt h.

Do not allocat e ext ra space for anot her array, you must do t his by modifying the input array in-
place wit h O(1) ext ra memory.

The order of element s can be changed. It doesn't mat t er what you leave beyond t he new lengt h.

Clarification:

Confused why t he ret urned value is an int eger but your answer is an array?

Not e t hat t he input array is passed in by reference, which means a modificat ion t o t he input array
will be known t o t he caller as well.

Int ernally you can t hink of t his:

// nums is passed in by reference. (i.e., without making a copy)

int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.

// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

Next
Previous
Replace Element s wit h Great est Element
Two Point ers
on Right Side

Last updat ed 4 years ago

Replace Elements with
Greatest Element on Right Side
ht t ps://leet code.com/problems/replace-element s-wit h-great est -element -on-right -side/

Question Answer

Given an array arr , replace every element in t hat array wit h t he great est element among t he
element s t o it s right , and replace t he last element wit h -1 .

Aft er doing so, ret urn t he array.

Example 1:

Input: arr = [17,18,5,4,6,1]

Output: [18,6,6,6,1,-1]

Previous Next
Remove Element Valid Mount ain Array

Last updat ed 4 years ago

Valid Mountain Array
ht t ps://leet code.com/problems/valid-mount ain-array/solut ion/

Question Answer

Given an array of int egers arr , ret urn true if and only if it is a valid mountain array.

Recall t hat arr is a mount ain array if and only if:

• arr.length >= 3

• There exist s some i wit h 0 < i < arr.length - 1 such t hat :

◦ arr[0] < arr[1] < ... < arr[i - 1] < A[i]

◦ arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]

Output: false

Previous
 Replace Element s wit h Great est Element Next

on Right Side Sort Array by Parit y

Last updat ed 4 years ago

Sort Array by Parity

 ht t ps://leet code.com/problems/sort -array-by-parit y/

Question Answer

Given an array A of non-negat ive int egers, ret urn an array consist ing of all t he even element s of
A , followed by all t he odd element s of A .

You may ret urn any answer array t hat sat isfies t his condit ion.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Previous Next
Valid Mount ain Array Squares of a Sort ed Array

Last updat ed 4 years ago

Squares of a Sorted Array
ht t ps://leet code.com/explore/learn/card/fun-wit h-arrays/521/int roduct ion/3240/

2 Pointers
The 2 point ers t echnique is where we have 2 variables point ing at different part s of t he array. An
example is:

x = [1, 2, 3, 4, 5]
pointer1 = 0
pointer2 = len(x) - 1
while pointer1 <= pointer2:
print(pointer1 + pointer2)
pointer1 += 1
pointer2 -= 1

This code adds t he largest element t o t he smallest element and goes inwards int o t he code.

Very oft en we'll want 2, 3, 4 point ers in our array. These point ers do not always have t o move at t he
same speed. Having 2 point ers is oft en an evolut ion of using 2 for loops. Look at t his problem:

Given an array of sort ed numbers and a t arget sum, find a pair in t he array whose sum is equal t o t he
given t arget .

Given t he array is sort ed, our first t hought might be 2 nest ed for loops. This is O(n^2). We want O(n).

We can achieve t his wit h point ers.

Place 1 point er at t he st art , and and anot her point er at t he end.

x = [1, 2, 3, 4, 5]
pointer1 = 0
pointer2 = len(x) - 1
target = 7

Now we calculat e t he sum of t he 2 numbers.

1 + 5 = 6
6 < target (7)
We know t he value is larger, so we move one t o t he right .

x = [1, 2, 3, 4, 5]
pointer1 = 2 # value 1
pointer2 = 4 # value 5
sum = 7
sum == target

This algorit hm is O(n).

The point ers pat t ern is an essent ial pat t ern for array manipulat ion, and we will see it come up a lot .
Especially wit h 2 point ers moving at different speeds.

Question Answer

Given an array of int egers A sort ed in non-decreasing order, ret urn an array of t he squares of
each number, also in sort ed non-decreasing order.

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Previous Next
Sort Array by Parit y Max Consecut ive Ones

Last updat ed 4 years ago

Max Consecutive Ones
ht t ps://leet code.com/problems/max-consecut ive-ones/

Question Answer

In t his quest ion we are asked:

Given a binary array, find t he maximum number of consecut ive 1s in t his array.

Input: [1,1,0,1,1,1]
Output: 3

Click "Answer" t ab t o see t he answer. Try t o do it yourself first !

Previous Next
Squares of a Sort ed Array Sliding Window

Last updat ed 4 years ago

Sliding Window
The sliding window t echnique eases t he t ask of finding opt imal chunks of contiguous data t hat meet a
cert ain condit ion:

• Longest subarray t hat …

• Short est subst ring cont aining …

• Et c

You can t hink of it as anot her variat ion of t he t wo point er t echnique, where point ers are updat ed
separat ely based on a cert ain condit ion. Below is t he basic recipe for t his t ype of problems, in
pseudocode:

Create two pointers, l, and r

Create variable to keep track of the result (res)

Iterate until condition A is satisfied:

Based on condition B:
update l, r or both
Update res
Return res

Previous Next
Max Consecut ive Ones Max Consecut ive Ones 3

Last updat ed 4 years ago

Max Consecutive Ones 3
ht t ps://leet code.com/problems/max-consecut ive-ones-iii/

Question Answer

Given an array A of 0s and 1s, we may change up t o K values from 0 t o 1.

Ret urn t he lengt h of t he longest (cont iguous) subarray t hat cont ains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation:
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Previous Next
Sliding Window St acks

Last updat ed 4 years ago

Stacks
A st ack is a t ype of dat a st ruct ure. Imagine it as a st ack of plat es. When we t ake a plat e, we t ake t he
plat e at t he t op.

When we add a plat e, we add it t o t he t op.

First in, first out .

St acks have 2 operat ions.

• .append(x) - Appends t he it em t o t he t op of t he st ack

• .pop() - Takes t he it em on t he t op of t he st ack

Previous Next
Max Consecut ive Ones 3 Balanced Bracket s

Last updat ed 4 years ago

Balanced Brackets
ht t ps://leet code.com/problems/valid-parent heses

Question Answer

Given a st ring s cont aining just t he charact ers '(' , ')' , '{' , '}' , '[' and ']' ,
det ermine if t he input st ring is valid.

An input st ring is valid if:

1. Open bracket s must be closed by t he same t ype of bracket s.

2. Open bracket s must be closed in t he correct order.

Previous Next
St acks General St rings & Arrays

Last updat ed 4 years ago

General Strings & Arrays
St rings are an abst ract ed dat at ype. They are arrays of charact ers. St rings are one of t he most popular
int erview t opics, and t he most vit al for you t o underst and.

Let 's learn bot h about st rings and arrays.

Previous Next
Balanced Bracket s Move Zeros

Last updat ed 4 years ago

Move Zeros
ht t ps://leet code.com/problems/move-zeroes/

In-Place
Somet hing t o not e is t hat if we want t o reduce space complexit y, oft en we'll want t o perform our
algorit hm on t he input array inst ead of creat ing a new array. This is called in-place.

Answer Question

Given an array nums , writ e a funct ion t o move all 0 's t o t he end of it while maint aining t he
relat ive order of t he non-zero element s.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do t his in-place wit hout making a copy of t he array.

2. Minimize t he t ot al number of operat ions.

Previous Next
General St rings & Arrays Unique Element s

Last updat ed 4 years ago

Unique Elements

BitMaps
Bit maps are arrays of specific sizes where every element is eit her True or False. They can be used for
many t hings but are an ext remely efficient met hod of st orage for cert ain algorit hms.

One example is t he act of whet her somet hing is open or closed, in or not in a set . Anyt hing t hat is
quant ifiable as a True / False operat ion.

An example of a Bit map is:

[False, False, False, False, True]

Let 's say you port scan a websit e t o see what port s are open wit h Rust Scan. The posit ion in t he array
relat es t o t he port number. So we have port numbers 1 t hrough 5. We st art wit h all port s closed (False),
but our scanner report s t hat port 5 is open so we set it t o True.

We use t he size of t he array, t he indices, and True / False values t o map True / False values t o a
domain.

Question Answer

Implement an algorit hm t o det ermine if a st ring has all unique charact ers

Previous Next
Move Zeros Merge Sort ed Array

Last updat ed 4 years ago

Merge Sorted Array
ht t ps://leet code.com/problems/merge-sort ed-array/

Question Answer

Given t wo sort ed int eger arrays nums1 and nums2, merge nums2 int o nums1 as one sort ed array.

Note:

• The number of element s init ialized in nums1 and nums2 are m and n respect ively.

• You may assume t hat nums1 has enough space (size t hat is equal t o m + n) t o hold addit ional
element s from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Previous Next
Unique Element s Mat rices

Last updat ed 4 years ago

Matrices
Valid Square Mat rix Search Sequel

Previous Next
Merge Sort ed Array Valid Square

Last updat ed 4 years ago

Valid Square
ht t ps://leet code.com/problems/valid-square/

Question Answer

Given t he coordinat es of four point s in 2D space, ret urn whet her t he four point s could const ruct a
square.

The coordinat e (x,y) of a point is represent ed by an int eger array wit h t wo int egers.

Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

Output: True

Previous Next
Mat rices Mat rix Search Sequel

Last updat ed 4 years ago

Matrix Search Sequel
ht t ps://leet code.com/problems/search-a-2d-mat rix-ii/submissions/

Question Answer

Writ e an efficient algorit hm t hat searches for a value in an m x n mat rix. This mat rix has t he
following propert ies:

• Int egers in each row are sort ed in ascending from left t o right .

• Int egers in each column are sort ed in ascending from t op t o bot t om.

Example:

Consider t he following mat rix:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

Given t arget = 5 , ret urn true .

Given t arget = 20 , ret urn false .

Previous Next
Valid Square Unt it led

Last updat ed 4 years ago

Untitled
Previous Next
Mat rix Search Sequel Int roduct ion

Last updat ed 4 years ago

Introduction

Discovering a Recursive Problem

A recursive funct ion should have t he following propert ies so t hat it does not result in an infinit e loop:

1. A simple base case (or cases) — a t erminat ing scenario t hat does not use recursion t o produce an
answer.
2. A set of rules, also known as recurrence relation t hat reduces all ot her cases t owards t he
base case.

Not e t hat t here could be mult iple places where t he funct ion may call it self.

A good hint is t hat recursion is built off of subproblems.

When you hear a problem wit h t he following st at ement s, it 's oft en (t hough not always) a good
candidat e for recursion: "Design a problem t o comput e t he nt h....", "Writ e code t o list t he first n....",
"implement a met hod t o comput e all....", and so on.

People t ypically have about 50% accuracy in t heir "t his sounds like a recursive problem...." inst inct . Use
t hat inst inct , since t hat 50% is valuable. But don't be afraid t o look at t he problem in a different way,
even if you init ially t hought it seemed recursive. There's a 50% chance you are wrong

Ot her t hings t hat can indicat e a recursion problem are:

• Does t he problem obviously break down int o subproblems?

• Could t he problem be solved wit h an arbit rary number of nest ed for loops? For when you t hink
"t his problem would be easy if I can cont rol how many nest ed for loops are generat ed"

• Can you reframe t he problem as a search problem? If so, DFS can be used.

• Is it easier t o solve recursively t han it erat ively?

Understanding any recursive code, step by step

Look at t he following code:
 void f(int n) {
if (n == 0) return;
f(n-1);
print(n);
}

What is t he out put of t his code?

If we read t he code in order, we might t hink it 'll print 5, 4, 3, 2, 1 . But t his is wrong, t he recursive
call happens before we can cont inue t o t he end.

Our code execut es as:

f(5)
f(4)
f(3)
f(2)
f(1)
f(0)
print(1)
print(2)
print(3)
print(4)
print(5)

The output is not always going to occur in the order it appears in our code

How do we accurately compute the output?

Walk t hrough t he code st ep by st ep. You are now t he compiler.

The most import ant t hing t o do is t o walk t hrough t he code exact ly as t he compiler would. As soon as
you st art assuming how t he code will behave and not reading t hrough it line-by-line, you’re screwed.

Draw the tree

All recursive funct ions act like a t ree.

ht t ps://s3-us-west -2.amazonaws.com/secure.not ion-st at ic.com/8c42d9b9-4ab8-4bb0-a279-

5dfb9fb4c38f/Unt it led.png

Do not lose track of variables

As funct ions get more complicat ed it becomes harder and harder t o act ually st ore everyt hing in your
head, especially since you have t o do your recursion out of order. The t ree will help you wit h t his.
Practice

I know t his may not sound like t he most fun t ask, but underst anding recursive code is crit ically
import ant . If you can underst and t he recursive code t hat ot her people writ e and why it works it will
make it exponent ially easier for you t o writ e your own recursive code.

Returning from Recursive Functions

Some recursive funct ions simply ret urn an object aft er it 's done. But not always! Let 's t alk about t he
different ways it can ret urn.

Global Variable
The first opt ion (and t he only one here t hat I’d say you should probably never use) is t o st ore your
result int o a global variable. We all know t hat global variables aren’t a great solut ion when t here is
anot her opt ion, so t ry t o avoid t his if possible.

For demonst rat ion purposes, let ’s look at a funct ion t hat count s t he number of even values in an array.
Here’s how we could writ e t his code using a global variable:

int globalResult;

void countEvenGlobal(int[] arr) {

globalResult = 0;
countEvenGlobal(arr, 0);
}

void countEvenGlobal(int[] arr, int i) {

if (i >= arr.length) return;
if (arr[i] % 2 == 0) globalResult++;
countEvenGlobal(arr, i+1);
}

The key here is t hat we will simply creat e a global variable and updat e t he value as we recurse t hrough
our code. Whenever we find an even value in our array, we just increment t he global variable, similar t o
how we might solve t his problem it erat ively.

Passed Variable
We pass a variable t o our recursive funct ion t hat will updat e as it goes.
 class ResultWrapper {
int result;
}

int countEvenPassed(int[] arr) {

ResultWrapper result = new ResultWrapper();
result.result = 0;
countEvenPassed(arr, 0, result);
return result.result;
}

void countEvenPassed(int[] arr, int i, ResultWrapper result) {

if (i >= arr.length) return;
if (arr[i] % 2 == 0) result.result++;
countEvenPassed(arr, i+1, result);
}

Not e in t his code, if we are using a language like Java, we have t o use some sort of Result Wrapper
class because we cannot direct ly pass a point er t o our funct ion and we will be updat ing t he value as we
go.

The advant age of t his approach is t hat it is generally t he easiest for most people t o underst and. It
also gives us t he opport unit y t o do t ail recursion, if t hat is somet hing t hat our language (and t he
problem) support s.

Build the result as we return

Our t hird st rat egy is a bit more difficult t o underst and because we are essent ially doing t he work t hat
we need t o do in reverse order. We will ret urn part ial values as we ret urn from our recursive calls and
combine t hem int o t he result t hat we want .

The reason t hat t his st rat egy is crit ical is t hat it will make it possible for us t o use t he FAST Met hod
t o solve dynamic programming problems. If we use one of t he previous t wo approaches, we are not
isolat ing our subproblems and so it becomes impossible for us t o act ually cache t he values t hat we
want .

int countEvenBuiltUp(int[] arr) {

return countEvenBuiltUp(arr, 0);
}

int countEvenBuiltUp(int[] arr, int i) {

if (i >= arr.length) return 0;
int result = countEvenBuiltUp(arr, i+1);
if (arr[i] % 2 == 0) result++;
return result;
}
For t he most part , you can use t hese ret urn st rat egies int erchangeably for different recursive
problems.

Don’t bot her pract icing using global variables, since you really should never use t hat in your int erview.
However, I would recommend pract icing bot h of t he ot hers. Try doing a pract ice problem bot h ways.
See what t he similarit ies and differences are. The ext ra pract ice will do you good!

Backtracing
Backt racking is an essent ial st rat egy t hat we use in recursion. It essent ially allows us t o t ry different
possible result s wit hout act ually knowing ahead of t ime what t he right result is.

Consider t he Knight ’s Tour problem. In t his problem, we want t o find a pat h t hat a knight can follow on a
chessboard where it will visit each square exact ly once.

ht t ps://s3-us-west -2.amazonaws.com/secure.not ion-st at ic.com/5d5116f4-5f85-4f8b-ae13-

4b31b5696683/image6.gif

We don’t act ually know what t he right more is t o make ahead of t ime and a knight can make up t o 8
different moves from any one square, so we just have t o pick a move at random.

But obviously not all combinat ions of moves will t ake us t hrough a valid pat h. Some moves might t rap
us in a corner t hat we can’t get out of wit hout visit ing t he same square t wice.

So what do we do? We “backt rack”.

The idea behind backt racking is simply t hat we ret race our st eps backwards and t hen t ry a different
pat h. This allows us t o t ry every different pat h unt il we ult imat ely find one t hat is valid.

Anot her example of t his t hat you’re likely already familiar wit h is dept h-first search in a t ree. When we
are looking for a node in a t ree, we consider t he left most branch first . Then what happens if we don’t
find t he node we’re looking for? We backt rack.

We go back up one level and t ry t he ot her child of t he parent node. If we st ill haven’t found what we
are looking for, we go back up t he t ree even furt her. This cont inues unt il we find what we are looking
for or have gone t hrough t he ent ire t ree.

Some common backt racking problems include:

• 0-1 Knapsack

• Sudoku Solving

• N Queens

• And many more…

A not e on backt racking: A lot of people hear “backt racking” and t hey st ress out about it , but my guess
is t hat if you’ve done any recursion in t he past , you’re already familiar wit h t he basic concept . Don’t
st ress t oo much about t his one specifically. Just make sure you underst and how t o implement t he 6
recursive pat t erns and you’ll learn how t o do backt racking as a side-effect .

Tail Recursion
Okay t his is t he most unnecessarily worried about concept in all of recursion. Tail recursion almost
never comes up in an int erview and isn’t even support ed by most major programming languages.

Tail recursion is an opt imizat ion t echnique t hat you can use t o improve t he space complexit y of a small
subset of recursive problems. To underst and how t his works, we do need t o t alk about space usage for
a second.

When you make recursive calls, t he comput er needs t o save t he st at e of t he current funct ion (all t he
variables, t he current posit ion t hat you’re execut ing at , et c) so t hat you can ret urn back aft er t he end
of t he recursive call.

Therefore, for every recursive call you make, you are using some space on t he call st ack. The more
recursive calls you make, t he more space you’re using.

Tail recursion allows us t o avoid having t o use ext ra space. Imagine t hat you writ e a funct ion where t he
very last line of t he funct ion is t he recursive call t hat immediat ely ret urns. Then do you really need t o
save t he previous funct ion st at e on t he call st ack?

No. You can just ret urn t he value from t he deepest level of your recursion direct ly t o t he t op.

That is what t ail recursion does for us. If we have a single recursive call t hat is t he very last t hing
before we ret urn, t hen we can opt imize out t he ext ra st ack space.

To look at our simple example from earlier, which of t hese is t ail recursive?

void f1(int n) {
if (n == 0) return;
f1(n-1);
print(n);
}

Or
 void f2(int n) {
if (n == 0) return;
print(n);
f2(n-1);
}

Based on our definit ion, you can see t hat in f2(), t he very last t hing we do is our recursive call. f1() print s
aft er we make t he recursive call so we can’t opt imize it because we are going t o need t o ret urn back
t o t he previous funct ion so t hat we can call print (n).

So in limit ed circumst ances, t ail recursion can be useful. It is part icularly useful while doing funct ional
programming, since you are oft en doing basic t hings like it erat ion recursively t hat can be easily
opt imized.

However, most of t he t ime, t ail recursion won’t be helpful t o us. Chances are t he language t hat you’re
using won’t support it and on t op of t hat , many of t he examples t hat we will see in our int erviews will
require us t o make mult iple recursive calls wit hin our funct ion. If you have mult iple calls, t hey can’t bot h
be t he last t hing before we ret urn and so t ail recursion is out of t he quest ion.

Calculating Time & Space Complexity

Time and space complexit y for recursive problems t ends t o pose quit e a challenge. Because recursive
problems are so hard t o parse in t he first place, it is oft en non-obvious how we would comput e t he
complexit y.

Time Complexity
Remember when we represent ed our recursion as a t ree st ruct ure? Well t hat t ree st ruct ure can show
us very clearly t he number of recursive calls we’re making.

And simply put , t he t ime complexit y is going t o be

O(number of recursive calls * work per recursive call) .

Wit h t his formula, we are now able t o simplify dramat ically int o t wo component s t hat we can more
easily calculat e.

First , let ’s t alk about t he number of recursive calls.

How do we est imat e t he t ot al number of recursive calls wit hout drawing out t he whole t ree? Well if
we want ed t o comput e t he number of nodes in a t ree, we can look at t he height of t he t ree and t he
branching fact or.

The height of t he t ree is how deep our recursion goes.

if you keep recursively calling f(n-1) and your base case is when n == 0, t hen our dept h is going t o be
O(n), since we keep decrement ing unt il n reaches 0. If we have mult iple different recursive calls, we
just consider what ever t he maximum dept h is (remember t hat Big Oh is an upper bound).

The branching fact or is t he maximum number of child nodes any parent has in a t ree. If we have a binary
t ree, t he branching fact or will be 2.

To find t he branching fact or of our recursive t ree, we simply need t o look at t he maximum number of
recursive calls. In our Fibonacci funct ion, we call fibonacci(n-1) and fibonacci(n-2) every t ime, which
gives us a branching fact or of 2.

int f(n) {
if (n == 0) return 0;

int sum = 0;
for (int i = 0; i < n; i++) {
sum += f(n-i);
}

return sum;
}

What would be t he branching fact or here?

It seems hard as t he branching fact or depends on n . But remember, we only need t he worst case.

In t his case, t he worst case is n .

Now we have t he branching fact or and height of our recursive t ree, we can use t hese t o calculat e t he
t ime complexit y of our recursive funct ion using t his heurist ic:

$$number\_ of\_ nodes = O(branching\_ fact or^{dept h\_ of\_ recursion})$$

Knowing t he number of nodes, we get t hat our t ot al t ime complexit y is:

$$number\_ of\_ nodes = O(branching\_ fact or^{dept h\_ of\_ recursion}*work\_ per\_ recursive\_ call)$$

Work per recursive call is simply t he amount of work t hat we’re doing in our funct ion ot her t han when
we call it recursively. If we have any sort of for loop, such as in t he example above, our work per
recursive call will be proport ional t o t hat loop, or O(n) in t his case.

That gives us a t ime complexit y of $O(n^n*n)$ for t he funct ion above.

Space Complexity
Recursive space complexit y is a bit easier for us t o comput e, but is also not exact ly t rivial.
The space does not depend on t he branching fact or, only on t he height and t hen amount of space used
per recursive call.

When we t hink about t his for a minut e, it makes sense. The branching fact or leads t o mult iple different
pat hs t hrough our recursive t ree. We have t o consider each of t hese separat ely for t he t ime complexit y
because t ime is addit ive. There is no way t o reuse t ime.

Space, however, can be reused. Each t ime we recurse down, we will be using more and more space.
However, once we ret urn from our recursive funct ion, we clear up space t hat can be reused for t he next
pat h.

This gives us a formula for our space complexit y of simply:

$$O(dept h\_ of\_ recursion * space\_ per\_ recursive\_ call)$$

It is, however, import ant t o remember t hat recursion does act ually use up space, since t hat is
somet hing t hat many people oft en t end t o forget .

How to Approach
Recursive solut ions, by definit ion, are built off of solut ions t o subproblems. Many t imes, t his will mean
simply t o comput e F(n) by adding somet hing, removing somet hing, or ot herwise changing t he solut ion
for F(n-1).

In ot her cases, you might solve t he problem for t he first half of t he dat a set , t hen t he second half, and
t hen merge t hose result s.

Three of t he most common approaches t o dividing a problem int o subproblems are:

Bottom Up Approach
The bot t om-up approach is oft en t he must int uit ive. We st art wit h knowing how t o solve t he problem
for a simple case, like a list wit h only one element . Then we figure out how t o solve t he problem for
t wo element s, t hen for t hree element s and so on.

The key here is t o t hink about how you can build t he solut ion for one case off of t he previous case (or
mult iple previous cases).

Top Down Approach

The t op down approach can be more complex since it 's less concret e. But somet imes, it 's t he best way
t o t hink about t he problem.
In t hese problems, we t hink about how we can divide t he problem for case N int o subproblems.

Be careful of overlap bet ween cases.

Half and Half

Divide t he dat aset in half.

Binary search works wit h a half and half approach. When we look for an element in an sort ed array, we
first figure out which half of t he array cont ains t he value. Then we recurse and search for it in t hat half.

Merge sort is also a half and half approach.

Recursion Relation
There are t wo import ant t hings t hat one needs t o figure out before implement ing a recursive funct ion:

• recurrence relation : t he relat ionship bet ween t he result of a problem and t he result of it s
subproblems.

• base case : t he case where one can comput e t he answer direct ly wit hout any furt her recursion
calls. Somet imes, t he base cases are also called bottom cases, since t hey are oft en t he cases
where t he problem has been reduced t o t he minimal scale, t he bot t om, if we consider t hat dividing
t he problem int o subproblems is in a t op-down manner.

Once we figure out t he above t wo element s, t o implement a recursive funct ion we simply call t he
funct ion it self according t o t he recurrence relat ion unt il we reach t he base case.

To explain t he above point s, let 's look at a classic problem, Pascal's Triangle:

Pascal's t riangle are a series of numbers arranged in t he shape of t riangle. In Pascal's t riangle, t he
left most and t he right most numbers of each row are always 1. For t he rest , each number is t he sum of
t he t wo numbers direct ly above it in t he previous row.

ht t ps://s3-us-west -2.amazonaws.com/secure.not ion-st at ic.com/b51cce56-3073-4a0c-99ab-

547991fae4f5/PascalTriangleAnimat ed2.gif

Given t he above definit ion, one is asked t o generat e t he Pascal's Triangle up t o a cert ain number of
rows.

Recurrence Relation of Pascal's Triangle

Let 's st art wit h t he recurrence relat ion wit hin t he Pascal's Triangle.
First of all, we define a funct ion f(i,j) which ret urns t he number in t he Pascal's Triangle in t he i-th row
and j-th column.

We t hen can represent t he recurrence relat ion wit h t he following formula:

$$f(i, j) = f(i - 1, j - 1) + f(i - 1, j)$$

The 6 Core Recursive Patterns

ht t ps://www.yout ube.com/wat ch?v=BibDrTCGXRM

If you underst and each of t hese pat t erns and how t o code t hem, t hen you can apply t hese concept s t o
almost any recursive problems t hat might come up in your int erview. These 6 pat t erns are It erat ion,
Subproblems, Select ion, Ordering, Divide & Conquer, and Dept h First Search. For t he remainder of t his
sect ion, we will go int o each in more det ail.

Iteration
As you hopefully know, any problem t hat can be solved recursively can also be solved it erat ively and
vice versa. This is a fundament al concept behind funct ional languages, where you use recursion t o do
everyt hing; t here are no loops.

For example, consider t he problem of print ing a linked list in reverse order. There are plent y of
approaches we can t ake for t his problem, but recursion is uniquely concise:

void printReverse(Node n) {
if (n == null) return;
printReverse(n.next);
print(n.val);
}

For it erat ion, we simply make our recursive call on t he remainder of our input s, eit her by passing in t he
next node (as we did above) or by increment ing some index. While t his doesn’t come up t oo oft en, t his
is one of t he simplest applicat ions of recursion.

Subproblems

• Breaking down a problem int o subproblems

Wit h all t hat being said, t here are some problems t hat just lend t hemselves t o being broken down int o
subproblems.
One example of t his is t he Fibonacci problem t hat we’ve t alked about earlier in t his post . In t hat case,
even t he mat hemat ical definit ion of a Fibonacci sequence is recursive.

Anot her problem t hat frequent ly comes up is t he Towers of Hanoi problem. In t his case, we can simply
break down our problem by considering t he subproblem of moving t he t op n-1 disks. If we can move
t he t op n-1 disks, we just move all of t hem t o t he middle pin, move our bot t om disk t o t he dest inat ion
pin, and t hen move t he above disks again over t o t he dest inat ion pin. This works because all of t he
disks above our bot t om pin are not affect ed by any pins below t hem.

In problems like t his, you have t o look for t hose subproblems wit h which t o break up t he problem.
However, t here aren’t t oo many problems in t his cat egory, since most can be more explicit ly solved
wit h one of t he following pat t erns.

Selection
This is my favorit e pat t ern t o t est people on because it is one of t he most common pat t erns t o come
up in recursion (and dynamic programming). In t his pat t ern, we are simply finding all of t he combinat ions
of our input t hat mat ch a cert ain crit eria.

Consider for example t he 0-1 Knapsack Problem. In t his problem, we have a series of it ems t hat have
weight s and values. We want t o figure out what t he maximum value is t hat we can achieve while
remaining under some fixed weight .

Many people recognize t his as a dynamic programming problem, since it ’s a classic example, but let ’s
look at it from a recursive st andpoint .

What would be a brut e force solut ion t o t his problem? Well we can easily validat e for a given
combinat ion of it ems whet her it is under t he maximum weight , and we can also easily comput e t he
weight for any combinat ion. That means if we could just generat e all t he different combinat ions, we
could figure out t he opt imal answer.

Figuring out all t he combinat ions is t he core of a select ion problem. I like t he t erm “select ion” because
t he way our code works is t o simply include/exclude, or “select ”, each it em in our list .

The brut e force code t o generat e all combinat ions might look somet hing like t his (t his is simplified,
but you get t he idea):
 List<List<Integer>> combinations(int[] n) {
List<List<Integer>> results = new LinkedList();
combinations(n, 0, results, new LinkedList<Integer>());
return results;
}

void combinations(int[] n, int i, List<List<Integer>> results, List<Integer> path) {

if (i == n.length) {
results.add(path);
return;
}

List<Integer> pathWithCurrent = new LinkedList(path);

pathWithCurrent.add(n[i]);

// Find all the combinations that exclude the current item

combinations(n, i+1, results, path);

// Find all the combinations that include the current item

combinations(n, i+1, results, pathWithCurrent);
}

Once we underst and t his basic pat t ern, we can st art t o make opt imizat ions. In many cases, we may
act ually be able t o filt er out some combinat ions premat urely. For example, in t he Knapsack problem, we
can limit our recursion t o only consider combinat ions of it ems t hat st ay below t he prescribed weight .

If you spend t he majorit y of your t ime on any one pat t ern, it should be t his one. It comes up so
frequent ly in so many different forms. Some good problems t o get your st art ed are 0-1 Knapsack,
Word Break, and N Queens.

Ordering
This pat t ern is t he permut at ion t o Select ion’s combinat ion. Essent ially here we’re looking at any case in
which we want t o consider different orderings of our values. The most st raight forward problem here is
just t o figure out all of t he permut at ions of a given set of element s, alt hough just like wit h select ion,
we may add in addit ional rest rict ions.

Some examples of problems t hat fall under t his cat egory are Bogosort (sort ing a list of it ems by
generat ing all permut at ions and det ermining which is sort ed), finding all numbers t hat can be made
from a set of digit s t hat mat ch a cert ain propert y, det ermine all palindromic st rings t hat can be made
from a set of charact ers, and more.

In it s most simple form, t his is one way t hat we can brut e force generat e all permut at ions of a list . You
can also see an alt ernat ive approach here:
 List<List<Integer>> permutations(Set<Integer> n) {
List<List<Integer>> results = new LinkedList();
permutations(n, results, new LinkedList<Integer>());
return results;
}

void permutations(Set<Integer> n, List<List<Integer>> results, List<Integer> path) {

if (n.isEmpty()) {
results.add(path);
return;
}

for (int i : n) {
// For now ignore concurrent modification issue
n.remove(i);
List<Integer> pathWithCurrent = new LinkedList(path);
pathWithCurrent.add(i);
permutations(n, results, pathWithCurrent);
n.add(i);
}
}

As you can hopefully see, t here is a lot of similarit y bet ween t his solut ion and t he combinat ions
solut ion above. By underst anding t hese t wo pat t erns and t heir variant s, you can cover a huge number of
t he different possible recursive problems you might be asked in your int erview.

Divide and Conquer

If you know about some of t he common applicat ions of recursion, you probably saw t his one coming.
Divide and conquer is t he backbone t o how we use t echniques such as mergesort , binary search, dept h
first search, and more. In t his t echnique, we at t empt t o break t he problem space in half, solve each half
separat ely, and t hen come back t oget her.

Most frequent ly, t his pat t ern is used as part of common algorit hms t hat you should already know, such
as t he one I ment ioned above, but t here are a handful of problems for which t his can be valuable.

For example, consider t rying t o det ermine all of t he unique binary t rees t hat we can generat e from a
set of numbers. If you pick a root node, you simply need t o generat e all of t he possible variat ions of a
left and right subt ree.

Consider t rying t o find t he maximum and minimum value of a list using t he minimum number of
comparisons. One way t hat we can do t his is by split t ing t he list repeat edly, much t he same as how we
would do mergesort .

This t echnique generally applies t o t ree and sort ing/searching problems where we will be split t ing t he
problem space and t hen recombining t he result s.
There is also a slight ly different case in which D&C is very useful: Trying t o find all of t he ways t o group
a set . Imagine, for example, t hat you have a mat hemat ical funct ion. You want t o det ermine all of t he
different ways t hat you can group t he argument s. This can be done by recursively t rying split t ing your
formula at every different point . Here is an example of what t his code might look like. It uses a st ring,
but demonst rat es t he same concept :

List<String> parentheses(String s) {
if (s.length() == 1) {
List<String> result = new LinkedList<String>();
result.add(s);
return result;
}

List<String> results = new LinkedList<String>();

for (int i = 1; i < s.length(); i++) {

List<String> left = parentheses(s.substring(0, i));
List<String> right = parentheses(s.substring(i, s.length()));

for (String s1 : left) {

for (String s2 : right) {\\
results.add("(" + s1 + s2 + ")");
}
}
}

return results;
}

In t his example, we t ake t he st ring and we t ry finding every different midpoint . For example “abcd”
becomes “(a)(bcd)”, “(ab)(cd)”, and “(abc)(d)”. Then we recursively apply t his t o each of t he halves of t he
st ring.

Depth First Search

Dept h first search is our final pat t ern t hat our recursive funct ions can fall under. It ’s also one t hat we’ll
likely find ourselves using a lot . That ’s because DFS (and BFS) are used ext ensively whenever we are
doing anyt hing wit h t rees or graphs.

In t erms of t he det ails of t rees and graphs, I’m not going t o go in dept h here. There is way t oo much t o
cover so I’m going t o leave t hem t o t heir own st udy guides.

The main import ant t hing wit h DFS is t o underst and how not only t o search for a node in a t ree or graph
but also how t o act ually find t he pat h it self. If you can’t do t hat , you’re severely limit ing what you can
act ually do.

Here is what t he code might look like t o find t he pat h t o a specific node in a t ree:
 List<Node> pathToNode(Node root, int val) {
if (root == null) return null;
if (root.value == val) {
List<Node> toReturn = new LinkedList<Node>();
toReturn.add(root);
return toReturn;
}

List<Node> left = pathToNode(root.left, val);

if (left != null) {
left.add(0, root);
return left;
}

List<Node> right = pathToNode(root.right, val);

if (right != null) {
right.add(0, root);
return right;
}

return null;
}

And t here’s not t hat much more t o it t han t hat . In most cases, you will use dept h first search as part of
a larger problem, rat her t han act ually having t o modify it in any significant way. Therefore t he most
import ant t hing is underst anding t he core of how DFS works.

Wit h t hese 6 recursive pat t erns, you will be able t o solve almost any recursive problem t hat you could
see in your int erview. The key is t o look for t hose pat t erns in t he problems t hat you are solving. If you
see t he pat t ern, use it . If not , t ry somet hing else. Different pat t erns will work bet t er for different
people, so do what feels right t o you.

Example
344. Reverse St ring

Print a st ring in reverse order.

You can easily solve t his problem it erat ively, i.e. looping t hrough t he st ring st art ing from it s last
charact er. But how about solving it recursively?

First , we can define t he desired funct ion as printReverse(str[0...n-1]) , where str[0]

represent s t he first charact er in t he st ring. Then we can accomplish t he given t ask in t wo st eps:

1. printReverse(str[1...n-1]) : print t he subst ring str[1...n-1] in reverse order.

2. print(str[0]) : print t he first charact er in t he st ring.
Not ice t hat we call t he funct ion it self in t he first st ep, which by definit ion makes t he funct ion
recursive.

Here is t he code snippet :

private static void printReverse(char [] str) {

helper(0, str);
}

private static void helper(int index, char [] str) {

if (str == null || index >= str.length) {
return;
}
helper(index + 1, str);
System.out.print(str[index]);
}

Top Down vs Bottom Up

From here.

Top Down
"Top-down" means t hat in each recursive call, we will visit t he node first t o come up wit h some values,
and pass t hese values t o it s children when calling t he funct ion recursively. So t he "t op-down" solut ion
can be considered as a kind of preorder t raversal. To be specific, t he recursive funct ion
top_down(root, params) works like t his:

1. return specific value for null node

2. update the answer if needed // answer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, para
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, par
5. return the answer if needed // answer <-- left_ans, right_ans

For inst ance, consider t his problem: given a binary t ree, find it s maximum dept h.

We know t hat t he dept h of t he root node is 1 . For each node, if we know it s dept h, we will know t he
dept h of it s children. Therefore, if we pass t he dept h of t he node as a paramet er when calling t he
funct ion recursively, all t he nodes will know t heir dept h. And for leaf nodes, we can use t he dept h t o
updat e t he final answer. Here is t he pseudocode for t he recursive funct ion
maximum_depth(root, depth) :
 1. return if root is null
2. if root is a leaf node:
3. answer = max(answer, depth) // update the answer if needed
4. maximum_depth(root.left, depth + 1) // call the function recursively for left
5. maximum_depth(root.right, depth + 1) // call the function recursively for righ

Bottom Up
"Bot t om-up" is anot her recursive solut ion. In each recursive call, we will first ly call t he funct ion
recursively for all t he children nodes and t hen come up wit h t he answer according t o t he ret urned
values and t he value of t he current node it self. This process can be regarded as a kind of postorder
t raversal. Typically, a "bot t om-up" recursive funct ion bottom_up(root) will be somet hing like t his:

1. return specific value for null node

2. left_ans = bottom_up(root.left) // call function recursively for left chi
3. right_ans = bottom_up(root.right) // call function recursively for right ch
4. return answers // answer <-- left_ans, right_ans, root.v

Let 's go on discussing t he quest ion about maximum dept h but using a different way of t hinking: for a
single node of t he t ree, what will be t he maximum dept h x of t he subt ree root ed at it self?

If we know t he maximum dept h l of t he subt ree root ed at it s left child and t he maximum dept h r
of t he subt ree root ed at it s right child, can we answer t he previous quest ion? Of course yes, we can
choose t he maximum bet ween t hem and add 1 t o get t he maximum dept h of t he subt ree root ed at t he
current node. That is x = max(l, r) + 1 .

It means t hat for each node, we can get t he answer aft er solving t he problem for it s children.
Therefore, we can solve t his problem using a "bot t om-up" solut ion. Here is t he pseudocode for t he
recursive funct ion maximum_depth(root) :

1. return 0 if root is null // return 0 for null node

2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1 // return depth of the subtree rooted at

Conclusion

Conclusion

It is not easy t o underst and recursion and find out a recursive solut ion for t he problem. It needs
pract ice.

When you meet a t ree problem, ask yourself t wo quest ions: Can you det ermine some paramet ers t o
help t he node know it s answer? Can you use t hese paramet ers and t he value of t he node it self t o
det ermine what should be t he paramet ers passed t o it s children? If t he answers are bot h yes, t ry t o
solve t his problem using a " top-down " recursive solut ion.

Or, you can t hink of t he problem in t his way: for a node in a t ree, if you know t he answer of it s children,
can you calculat e t he answer of t hat node? If t he answer is yes, solving t he problem recursively using a
bottom up approach might be a good idea.

In t he following sect ions, we provide several classic problems for you t o help you underst and t ree
st ruct ure and recursion bet t er.

Previous Next
Unt it led Backt racking

Last updat ed 4 years ago

Backtracking

What is Backtracking?
Backt racking is where we increment ally build candidat es t o solut ions, and abandon candidat es
(backt rack) as soon we as det ermine t hat candidat e is not valid.

Backt racking has 3 key feat ures:

1. Make a change

2. Recurse
3. Undo t he change

And Backt racking is oft en used t o solve 3 t ypes of problems:

1. Decision Problem – We search for a feasible solut ion.

2. Opt imisat ion Problem – We search for t he best solut ion.
3. Enumerat ion Problem – We find all feasible solut ions.

What Problems can be solved by Backtracking?

Any problem t hat recursively build candidat es t o a solut ion and abandons a candidat e (backt racks)
when it is found t o not be valid.

• Choice - we have a decision

• Const raint s - we have some const raint s

• Goal - we have a goal.

Imagine recursive problems. Normally we can speed t hings up wit h dynamic programming, but
somet imes we don't even want t o consider a solut ion -- we just want t o t hrow it out .

That 's what backt racking is.

The way I t hink of backt racking is as follows:

1. Make a change
2. Recurse
3. Undo t he change

If at any point we reach t he goal st at e, ret urn t rue/print /what ever.

 • So for t he sudoku problem: For all possible squares on t he board see if we can add any value
bet ween 1-9. If we can, add t he value and recurse for t he rest of t he board. Then undo t he changes
by making t he board blank again. Goal st at e is when we have successfully filled in last square

• For n queens: It erat e t hrough t he first row. If we can place a queen at a given column place it and
recurse for t he remaining rows. Then undo t he change by removing t he queen and moving t o t he
next column. Goal is when we have placed queen on nt h row

• Print all possible permut at ions: Init ialize an empt y St ring for result s. In t he input st ring it erat e
t hrough each charact er. For each charact er, remove it from input and add it t o result and recurse.
Then remove t he charact er from result and insert it back in same posit ion in input st ring. Goal is
when result size = n.

• Given n print all set s of valid parent heses t hat amount t o n: St art wit h blank input st ring and 2
numbers i, j init ialized t o n t hat denot e number of opening/closing parent heses remaining - you can
add opening parent heses t o t he st ring if i>0. You can add closing parent heses if j>i. If you can add
opening parent heses, add it t o st ringbuilder, recurse and t hen remove it from end of st ringbuilder. If
you can add closing parent heses add it t o st ringbuilder, recurse and t hen remove it from end of
st ringbuilder. Goal is when bot h i, j =0.

• Print all subset s of a set : For each charact er in set , remove it from input set add it t o result set
and if it has not been print ed already, print (goal is any set t hat has not been print ed already). Then
recurse for remaining element s. Then remove element from result set and add it back t o input set .

Pret t y much all t he backt racking problems I have done follows t his pat t ern.

Previous Next
Int roduct ion Permut at ions

Last updat ed 4 years ago

Permutations
ht t ps://leet code.com/problems/permut at ions/

Question Answer

Given a collect ion of distinct int egers, ret urn all possible permut at ions.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Previous Next
Backt racking Int roduct ion

Last updat ed 4 years ago

Introduction
Not e: I have writ t en ext ensively about Dynamic Programming, and even a book on it ! This sect ion will
feat ure t hat , and more.

This sect ion is based off of t he famous Leet code post , Dynamic Programming Pat t erns.

Algorit hm_ Design.pdf

1MB pdf

Loading...
LeetCode

1. DP for Beginners [Problems | Pat t erns | Sample Solut ions] by @wh0ami

• [LIST]
2. DP Pat t erns by @aat alyk
3. How t o solve DP - St ring? Templat e and 4 St eps t o be followed by @igooglet hings
4. Dynamic Programming Quest ions t hread by @karansingh1559
5. DP Classificat ion helpful not es by @adit yakrverma
6. How t o approach DP problems by @heroes3001
7. It erat ive DP for subset sum problems by @yuxiangmusic
8. DP problems summary (problem cat egorizat ion) by @richenyunqi

Next
Previous
Minimum (Maximum) Pat h t o Reach
Permut at ions
a Target

Last updat ed 4 years ago

Minimum (Maximum) Path to Reach a Target
Given a t arget find minimum (maximum) cost / pat h / sum t o reach t he t arget .

We can do t his by choosing t he minimum (maximum) pat h among all possible pat hs before t he current
st at e, and t hen add t he value for t he current st at e.

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

An example is:

for i in range(2, len(cost)):

cost[i] = min(cost[i] + cost[i - 1], cost[i] + cost[i - 2])
return min(cost[-1], cost[-2])

Previous Next
Int roduct ion Min Cost Climbing St airs

Last updat ed 4 years ago

Min Cost Climbing Stairs
ht t ps://leet code.com/problems/min-cost -climbing-st airs/

Question Answer

On a st aircase, t he i -t h st ep has some non-negat ive cost cost[i] assigned (0 indexed).

Once you pay t he cost , you can eit her climb one or t wo st eps. You need t o find minimum cost t o
reach t he t op of t he floor, and you can eit her st art from t he st ep wit h index 0, or t he st ep wit h
index 1.

Previous
Next
Minimum (Maximum) Pat h t o Reach
Coin Change
a Target

Last updat ed 4 years ago

Coin Change
ht t ps://leet code.com/problems/coin-change/

Question Answer

You are given coins of different denominat ions and a t ot al amount of money amount . Writ e a
funct ion t o comput e t he fewest number of coins t hat you need t o make up t hat amount . If t hat
amount of money cannot be made up by any combinat ion of t he coins, ret urn -1 .

You may assume t hat you have an infinit e number of each kind of coin.

Input: coins = [1,2,5], amount = 11

Output: 3
Explanation: 11 = 5 + 5 + 1

Previous Next
Min Cost Climbing St airs Minimum Pat h Sum

Last updat ed 4 years ago

Minimum Path Sum
ht t ps://leet code.com/problems/minimum-pat h-sum/

Question Hint Answer

Given a m x n grid filled wit h non-negat ive numbers, find a pat h from t op left t o bot t om right which
minimizes t he sum of all numbers along it s pat h.

Note: You can only move eit her down or right at any point in t ime.

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Previous Next
Coin Change Triangle

Last updat ed 4 years ago

Triangle
ht t ps://leet code.com/problems/t riangle

We've seen dynamic programming by st art ing at t he t op of t he t ree and working down (t op-down
approach). What if we went from t he bot t om up (bot t om-up approach)?

Question Answer

Given a t riangle, find t he minimum pat h sum from t op t o bot t om. Each st ep you may move t o
adjacent numbers on t he row below.

For example, given t he following t riangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum pat h sum from t op t o bot t om is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Next
Previous
Minimum Cost t o Move Chips t o The
Minimum Pat h Sum
Same Posit ion

Last updat ed 4 years ago

Minimum Cost to Move
Chips to The Same Position
ht t ps://leet code.com/problems/minimum-cost -t o-move-chips-t o-t he-same-posit ion/

Question Answer

We have n chips, where t he posit ion of t he ith chip is position[i] .

We need t o move all t he chips t o the same position. In one st ep, we can change t he posit ion of
t he ith chip from position[i] t o:

• position[i] + 2 or position[i] - 2 wit h cost = 0 .

• position[i] + 1 or position[i] - 1 wit h cost = 1 .

Ret urn the minimum cost needed t o move all t he chips t o t he same posit ion.

Input: position = [1,2,3]

Output: 1
Explanation: First step: Move the chip at position 3 to position 1 with cost = 0.
Second step: Move the chip at position 2 to position 1 with cost = 1.
Total cost is 1.

Previous Next
Triangle Consecut ive Charact ers

Last updat ed 4 years ago

Consecutive Characters
ht t ps://leet code.com/problems/consecut ive-charact ers/

Question Answer

Given a st ring s , t he power of t he st ring is t he maximum lengt h of a non-empt y subst ring t hat
cont ains only one unique charact er.

Ret urn the power of t he st ring.

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Previous
Next
Minimum Cost t o Move Chips t o The
Perfect Squares
Same Posit ion

Last updat ed 4 years ago

Perfect Squares
ht t ps://leet code.com/problems/perfect -squares/

Question Hint Answer

Given a posit ive int eger n, find t he least number of perfect square numbers (for example,
1, 4, 9, 16, ... ) which sum t o n.

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Previous Next
Consecut ive Charact ers Dist inct Ways

Last updat ed 4 years ago

Distinct Ways
Given a t arget find a number of dist inct ways t o reach t he t arget .
We do t his by summing all possible ways t o reach t he current st at e.

𝑟𝑜𝑢𝑡𝑒𝑠[𝑖] = 𝑟𝑜𝑢𝑡𝑒𝑠[𝑖 − 1] + 𝑟𝑜𝑢𝑡𝑒𝑠[𝑖 − 2], ..., + 𝑟𝑜𝑢𝑡𝑒𝑠[𝑖 − 𝑘]

An example is:

d = [float("inf") for i in range(n)]

d[0] = 1
d[1] = 2
for i in range(2, n):
d[i] = d[i - 1] + d[i - 2]
return d[-1]

Previous Next
Perfect Squares Climbing St airs

Last updat ed 4 years ago

Climbing Stairs
ht t ps://leet code.com/problems/climbing-st airs/

Question Answer

You are climbing a st air case. It t akes n st eps t o reach t o t he t op.

Each t ime you can eit her climb 1 or 2 st eps. In how many dist inct ways can you climb t o t he t op?

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Previous Next
Dist inct Ways Unique Pat hs

Last updat ed 4 years ago

Unique Paths
ht t ps://leet code.com/problems/unique-pat hs/

Question Answer

A robot is locat ed at t he t op-left corner of a m x n grid (marked 'St art ' in t he diagram below).

The robot can only move eit her down or right at any point in t ime. The robot is t rying t o reach t he
bot t om-right corner of t he grid (marked 'Finish' in t he diagram below).

How many possible unique pat hs are t here?

Input: m = 3, n = 7
Output: 28

Example 2
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right c
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Previous Next
Climbing St airs Number of Dice Rolls wit h Target Sum
Last updat ed 4 years ago

Number of Dice Rolls with Target Sum

ht t ps://leet code.com/problems/number-of-dice-rolls-wit h-t arget -sum/

Question Answer
 You have d dice, and each die has f faces numbered 1, 2, ..., f .

Ret urn t he number of possible ways (out of fd t ot al ways) modulo 10^9 + 7 t o roll t he dice so
t he sum of t he face up numbers equals target .

Input: d = 1, f = 6, target = 3
Output: 1
Explanation:
You throw one die with 6 faces. There is only one way to get a sum of 3.

Previous Next
Unique Pat hs Merging Int ervals

Last updat ed 4 years ago

Merging Intervals
Given a set of numbers find an opt imal solut ion for a problem considering t he current number and t he
best you can get from t he left and right sides.

We can approach t his by finding all opt imal solut ions for every int erval and ret urn t he best possible
answer.

// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]

Get t he best from t he left and right sides and add a solut ion for t he current posit ion.

for(int l = 1; l<n; l++) {

for(int i = 0; i<n-l; i++) {
int j = i+l;
for(int k = i; k<j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);
}
}
}

return dp[0][n-1]

Previous Next
Number of Dice Rolls wit h Target Sum Minimum Cost Tree From Leaf Values

Last updat ed 4 years ago

Minimum Cost Tree From Leaf Values
ht t ps://leet code.com/problems/minimum-cost -t ree-from-leaf-values/

Question Answer

Given an array arr of posit ive int egers, consider all binary t rees such t hat :

• Each node has eit her 0 or 2 children;

• The values of arr correspond t o t he values of each leaf in an in-order t raversal of t he t ree.
(Recall that a node is a leaf if and only if it has 0 children.)

• The value of each non-leaf node is equal t o t he product of t he largest leaf value in it s left and
right subt ree respect ively.

Among all possible binary t rees considered, ret urn t he smallest possible sum of t he values of each
non-leaf node. It is guarant eed t his sum fit s int o a 32-bit int eger.

Input: arr = [6,2,4]

Output: 32
Explanation:
There are two possible trees. The first has non-leaf node sum 36, and the second

24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4

Previous Next
Merging Int ervals DP on St rings

Last updat ed 4 years ago

DP on Strings
Given t wo st rings s1 and s2, ret urn some result .

Most of t he problems on t his pat t ern requires a solut ion t hat can be accept ed in O(n^2) complexit y.

// i - indexing string s1
// j - indexing string s2
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = /*code*/;
} else {
dp[i][j] = /*code*/;
}
}
}

If you are given one st ring s t he approach may lit t le vary

for (int l = 1; l < n; ++l) {

for (int i = 0; i < n-l; ++i) {
int j = i + l;
if (s[i] == s[j]) {
dp[i][j] = /*code*/;
} else {
dp[i][j] = /*code*/;
}
}
}

Previous Next
Minimum Cost Tree From Leaf Values Levensht ein Dist ance

Last updat ed 4 years ago

Levenshtein Distance
ht t ps://leet code.com/problems/edit -dist ance/

This quest ion is a leet code hard, but in my opinion it is easier t han t he next problem which is a
leet code medium.

Question Answer

Given t wo st rings word1 and word2 , ret urn the minimum number of operations required to
convert word1 to word2 .

You have t he following t hree operat ions permit t ed on a word:

• Insert a charact er

• Delet e a charact er

• Replace a charact er

Input: word1 = "horse", word2 = "ros"

Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Previous Next
DP on St rings Longest Common Subsequence

Last updat ed 4 years ago

Longest Common Subsequence
ht t ps://leet code.com/problems/longest -common-subsequence/

Question Answer

Given t wo st rings text1 and text2 , ret urn t he lengt h of t heir longest common subsequence.

A subsequence of a st ring is a new st ring generat ed from t he original st ring wit h some
charact ers(can be none) delet ed wit hout changing t he relat ive order of t he remaining charact ers.
(eg, "ace" is a subsequence of "abcde" while "aec" is not ). A common subsequence of t wo st rings is
a subsequence t hat is common t o bot h st rings.

If t here is no common subsequence, ret urn 0.

Previous Next
Levensht ein Dist ance Int roduct ion

Last updat ed 4 years ago

Introduction
Based on t his:

Loading...
LeetCode

Binary Search is an algorit hm for searching for dat a in sort ed dat a.

We split t he search space int o t wo halves and only keep t he half t hat probably has t he search t arget
and t hrow away t he ot her half t hat cannot cont ain t he t arget .

In t his way, we reduce t he search sapce t o half at every st ep unt il we find t he t arget .

Binary search helps us reduce our O(n) linear search algorit hm int o O(log n).

We oft en want t o implement a slight ly modified binary search. Here are some t ypical problems we may
face:

• When do we exit t he loop? Should we use left < right or <= right ?

• How t o init ialise t he boundary variable left and right

• How t o updat e t he boundary? How t o choose t he appropriat e combinat ion from

left = mid, left = mid + 1 and right = mid, right = mid - 1 ?

A rat her common misunderst anding of binary search is t hat people oft en t hink t his t echnique could only
be used in simple scenario like "Given a sort ed array, find a specific value in it ". As a mat t er of fact , it
can be applied t o much more complicat ed sit uat ions.

Aft er a lot of pract ice in Leet Code, I've made a powerful binary search t emplat e and solved many Hard
problems by just slight ly t wist ing t his t emplat e. I'll share t he t emplat e wit h you guys in t his post . I
don't want t o just show off t he code and leave. Most import ant ly, I want t o share t he logical t hinking:
how t o apply t his general t emplat e t o all sort s of problems. Hopefully, aft er reading t his post , people
wouldn't be pissed off any more when Leet Coding, "Holy sh*t ! This problem could be solved wit h binary
search! Why didn't I t hink of t hat before!"

Generalised Binary Search

Suppose we have a search space. It could be an array, a range, et c. Usually it 's sort ed in ascend order.
For most t asks, we can t ransform t he requirement int o t he following generalized form:
Minimize k , s.t. condition(k) is True

This is a generalised binary search.

def binary_search(array) -> int:

def condition(value) -> bool:
pass

left, right = 0, len(array)

while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left

What 's really nice of t his t emplat e is t hat , for most of t he binary search problems, we only need t o
modify t hree part s aft er copy-past ing t his t emplat e, and never need t o worry about corner cases and
bugs in code any more:

• Correct ly init ialize t he boundary variables left and right . Only one rule: set up t he boundary t o
include all possible elements;

• Decide ret urn value. Is it return left or return left - 1 ? Remember t his: after exiting the
while loop, left is the minimal k​satisfying the condition function;

• Design t he condition funct ion. This is t he most difficult and most beaut iful part . Needs lot s of
pract ice.

Below I'll show you guys how t o apply t his powerful t emplat e t o many Leet Code problems.

Previous Next
Longest Common Subsequence First Bad Version

Last updat ed 4 years ago

First Bad Version
ht t ps://leet code.com/problems/first -bad-version/

Question Answer

You are a product manager and current ly leading a t eam t o develop a new product . Unfort unat ely,
t he lat est version of your product fails t he qualit y check. Since each version is developed based
on t he previous version, all t he versions aft er a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want t o find out t he first bad one, which
causes all t he following ones t o be bad.

You are given an API bool isBadVersion(version) which ret urns whet her version is bad.
Implement a funct ion t o find t he first bad version. You should minimize t he number of calls t o t he
API.

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

In Pyt hon, we can use bot h l + r // 2 or l + (right - l) // 2 .

Previous Next
Int roduct ion Sqrt (x)

Last updat ed 4 years ago

Sqrt(x)
ht t ps://leet code.com/problems/sqrt x/

Question Answer

Implement int sqrt(int x) .

Comput e and ret urn t he square root of x, where x is guarant eed t o be a non-negat ive int eger.

Since t he ret urn t ype is an int eger, t he decimal digit s are t runcat ed and only t he int eger part of
t he result is ret urned.

Input: 4
Output: 2

Previous Next
First Bad Version Search Insert Posit ion

Last updat ed 4 years ago

Search Insert Position
ht t ps://leet code.com/problems/search-insert -posit ion/

Question Answer

Given a sort ed array of dist inct int egers and a t arget value, ret urn t he index if t he t arget is found.
If not , ret urn t he index where it would be if it were insert ed in order.

Input: nums = [1,3,5,6], target = 5

Output: 2

Previous Next
Sqrt (x) Advanced

Last updat ed 4 years ago

Advanced
The above problems are quit e easy t o solve, because t hey already give us t he array t o be searched.
We'd know t hat we should use binary search t o solve t hem at first glance. However, more oft en are t he
sit uat ions where t he search space and search t arget are not so readily available. Somet imes we won't
even realize t hat t he problem should be solved wit h binary search -- we might just t urn t o dynamic
programming or DFS and get st uck for a very long t ime.

As for t he quest ion "When can we use binary search?", my answer is t hat , If we can discover some
kind of monotonicity, for example, if condition(k) is True then condition(k + 1) is True ,
then we can consider binary search.

Previous Next
Search Insert Posit ion KoKo Eat ing Banana

Last updat ed 4 years ago

KoKo Eating Banana
ht t ps://leet code.com/problems/koko-eat ing-bananas/

Question Answer

Koko loves t o eat bananas. There are N piles of bananas, t he i -t h pile has piles[i]
bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eat ing speed of K . Each hour, she chooses some pile of
bananas, and eat s K bananas from t hat pile. If t he pile has less t han K bananas, she eat s all of
t hem inst ead, and won't eat any more bananas during t his hour.

Koko likes t o eat slowly, but st ill want s t o finish eat ing all t he bananas before t he guards come
back.

Ret urn t he minimum int eger K such t hat she can eat all t he bananas wit hin H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8

Output: 4

Previous Next
Advanced Capacit y t o Ship Packages wit hin D Days

Last updat ed 4 years ago

Capacity to Ship Packages within D Days

ht t ps://leet code.com/problems/capacit y-t o-ship-packages-wit hin-d-days/

Question Answer

A conveyor belt has packages t hat must be shipped from one port t o anot her wit hin D days.

The i -t h package on t he conveyor belt has a weight of weights[i] . Each day, we load t he
ship wit h packages on t he conveyor belt (in t he order given by weights ). We may not load more
weight t han t he maximum weight capacit y of t he ship.

Ret urn t he least weight capacit y of t he ship t hat will result in all t he packages on t he conveyor
belt being shipped wit hin D days.

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5

Output: 15
Explanation:
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capaci

Next
Previous
Minimum Number of Days t o Make
KoKo Eat ing Banana
m Bouquet s

Last updat ed 4 years ago

Minimum Number of Days to Make m Bouquets
ht t ps://leet code.com/problems/minimum-number-of-days-t o-make-m-bouquet s/

Question Answer

Given an int eger array bloomDay , an int eger m and an int eger k .

We need t o make m bouquet s. To make a bouquet , you need t o use k adjacent flowers from
t he garden.

The garden consist s of n flowers, t he ith flower will bloom in t he bloomDay[i] and t hen can
be used in exactly one bouquet .

Ret urn the minimum number of days you need t o wait t o be able t o make m bouquet s from t he
garden. If it is impossible t o make m bouquet s ret urn -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1

Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloo
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.

Previous Next
Capacit y t o Ship Packages wit hin D Days Split array largest sum

Last updat ed 4 years ago

Split array largest sum
ht t ps://leet code.com/problems/split -array-largest -sum/

Question Answer

Given an array nums which consist s of non-negat ive int egers and an int eger m , you can split t he
array int o m non-empt y cont inuous subarrays.

Writ e an algorit hm t o minimize t he largest sum among t hese m subarrays.

Input: nums = [7,2,5,10,8], m = 2

Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Previous Next
Minimum Number of Days t o Make Minimum Number of Days t o Make
m Bouquet s m Bouquet s

Last updat ed 4 years ago

Minimum Number of Days to Make m Bouquets
ht t ps://leet code.com/problems/minimum-number-of-days-t o-make-m-bouquet s/

Question Answer

Given an int eger array bloomDay , an int eger m and an int eger k .

We need t o make m bouquet s. To make a bouquet , you need t o use k adjacent flowers from
t he garden.

The garden consist s of n flowers, t he ith flower will bloom in t he bloomDay[i] and t hen can
be used in exactly one bouquet .

Ret urn the minimum number of days you need t o wait t o be able t o make m bouquet s from t he
garden. If it is impossible t o make m bouquet s ret urn -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1

Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloo
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.

Previous Next
Split array largest sum Koko Eat ing Bananas

Last updat ed 4 years ago

Koko Eating Bananas
ht t ps://leet code.com/problems/koko-eat ing-bananas/

Question Answer

Koko loves t o eat bananas. There are N piles of bananas, t he i -t h pile has piles[i]
bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eat ing speed of K . Each hour, she chooses some pile of
bananas, and eat s K bananas from t hat pile. If t he pile has less t han K bananas, she eat s all of
t hem inst ead, and won't eat any more bananas during t his hour.

Koko likes t o eat slowly, but st ill want s t o finish eat ing all t he bananas before t he guards come
back.

Ret urn t he minimum int eger K such t hat she can eat all t he bananas wit hin H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8

Output: 4

Previous
Next
Minimum Number of Days t o Make
Find K-t h Smallest Pair Dist ance
m Bouquet s

Last updat ed 4 years ago

Find K-th Smallest Pair Distance
ht t ps://leet code.com/problems/find-k-t h-smallest -pair-dist ance/

Question Answer

Given an int eger array, ret urn t he k-t h smallest distance among all t he pairs. The dist ance of a pair
(A, B) is defined as t he absolut e difference bet ween A and B.

Example 1:

Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Previous Next
Koko Eat ing Bananas Ugly Number 3

Last updat ed 4 years ago

Ugly Number 3
ht t ps://leet code.com/problems/ugly-number-iii/

Question Answer

Writ e a program t o find t he n -t h ugly number.

Ugly numbers are positive integers which are divisible by a or b or c .

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Next
Previous
Find t he Smallest Divisor Given
Find K-t h Smallest Pair Dist ance
a Threshold

Last updat ed 4 years ago

Find the Smallest Divisor Given a Threshold
ht t ps://leet code.com/problems/find-t he-smallest -divisor-given-a-t hreshold/

Question Answer

Given an array of int egers nums and an int eger threshold , we will choose a posit ive int eger
divisor and divide all t he array by it and sum t he result of t he division. Find t he smallest divisor
such t hat t he result ment ioned above is less t han or equal t o threshold .

Each result of division is rounded t o t he nearest int eger great er t han or equal t o t hat element . (For
example: 7/3 = 3 and 10/2 = 5).

It is guarant eed t hat t here will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6

Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the s

Next
Previous
Kt h smallest number in
Ugly Number 3
mult iplicat ion t able

Last updat ed 4 years ago

Kth smallest number in multiplication table
ht t ps://leet code.com/problems/kt h-smallest -number-in-mult iplicat ion-t able/descript ion/

Question Answer

Nearly every one have used t he Mult iplicat ion Table. But could you find out t he k-th smallest
number quickly from t he mult iplicat ion t able?

Given t he height m and t he lengt h n of a m * n Mult iplicat ion Table, and a posit ive int eger
k , you need t o ret urn t he k-th smallest number in t his t able.

Example 1:

Input: m = 3, n = 3, k = 5
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Previous
Next
Find t he Smallest Divisor Given
Binary Trees
a Threshold

Last updat ed 4 years ago

Binary Trees

Preorder Traversal
Pre-order t raversal is t o visit t he root first . Then t raverse t he left subt ree. Finally, t raverse t he right
subt ree.

Basically, visit s it s current node before it s child node (hence pre-order)

Pre-order is implement ed as a queue in it erat ive.

Used t o creat e a copy of t he t ree or get prefix t raversal.

Queues

fn preOrderTrav(TreeNode Node){
if node != None:
visit(node);
preOrderTrav(node.left)
preOrderTrav(node.right)
}

In-order traversal
In-order t raversal is t o t raverse t he left subt ree first . Then visit t he root . Finally, t raverse t he right
subt ree.

In-order is implement ed as a stack in it erat ive.

When performed on a binary search t ree, it visits the nodes in ascending order (hence t he name in-
order)

St acks

fn inOrderTrav(TreeNode node){
if node != None:
inOrderTrav(node.left)
visit(node)
inOrderTrav(node.right)
}
Post Order
Visit s current node aft er it s child nodes (post -order, as it does it s node post )

In a post order, t he root is always visit ed last .

Used t o delet e t rees or post fix expression.

fn postTrav(TreeNode node){
postTrav(node.left)
postTrav(node.right)
visit(node)
}

Previous
Next
Kt h smallest number in
Merging Binary Trees
mult iplicat ion t able

Last updat ed 4 years ago

Merging Binary Trees
ht t ps://leet code.com/problems/merge-t wo-binary-t rees

Question Answer

Given t wo binary t rees node0 and node1 , ret urn a merge of t he t wo t rees where each value is
equal t o t he sum of t he values of t he corresponding nodes of t he input t rees. If only one input
t ree has a node in a given posit ion, t he corresponding node in t he new t ree should mat ch t hat input
node.

For example, given

0 7
/ \ / \
3 2 5 1
/
3

Ret urn

7
/ \
8 3
/
3

Constraints

• n ≤ 100,000 where n is t he number of nodes in node0

• m ≤ 100,000 where m is t he number of nodes in node1

Example 1

Input

node0 = [1, [0, null, null], null]

node1 = [1, null, null]

Output

[2, [0, null, null], null]

 Previous Next
Binary Trees Binary Tree Preorder Traversal

Last updat ed 4 years ago

Binary Tree Preorder Traversal

 ht t ps://leet code.com/problems/binary-t ree-preorder-t raversal/

Question Answer

Given t he root of a binary t ree, ret urn the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [1,2,3]

Previous Next
Merging Binary Trees Binary Tree Post order Traversal

Last updat ed 4 years ago

Binary Tree Postorder Traversal
ht t ps://leet code.com/problems/binary-t ree-post order-t raversal/

Question Answer

Given t he root of a binary t ree, ret urn the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [3,2,1]

Previous Next
Binary Tree Preorder Traversal Binary Tree Level Order Traversal

Last updat ed 4 years ago

Binary Tree Level Order Traversal
ht t ps://leet code.com/problems/binary-t ree-level-order-t raversal/

Question Answer

Given a binary t ree, ret urn t he level order t raversal of it s nodes' values. (ie, from left t o right , level
by level).

For example:
Given binary t ree [3,9,20,null,null,15,7] ,

3
/ \
9 20
/ \
15 7

ret urn it s level order t raversal as:

[
[3],
[9,20],
[15,7]
]

Previous Next
Binary Tree Post order Traversal Binary Tree Inorder Traversal

Last updat ed 4 years ago

Binary Tree Inorder Traversal
ht t ps://leet code.com/problems/binary-t ree-inorder-t raversal/

Question Answer

Given t he root of a binary t ree, ret urn the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Previous Next
Binary Tree Level Order Traversal Symmet ric Tree

Last updat ed 4 years ago

Symmetric Tree
ht t ps://leet code.com/problems/symmet ric-t ree/

Question Answer

Given a binary t ree, check whet her it is a mirror of it self (ie, symmet ric around it s cent er).

For example, t his binary t ree [1,2,2,3,4,4,3] is symmet ric:

1
/ \
2 2
/ \ / \
3 4 4 3

But t he following [1,2,2,null,3,null,3] is not :

1
/ \
2 2
\ \
3 3

Next
Previous
Populat ing Next Right Point ers in
Binary Tree Inorder Traversal
Each Node

Last updat ed 4 years ago

Populating Next Right Pointers in Each Node
ht t ps://leet code.com/problems/populat ing-next -right -point ers-in-each-node/

Question Answer

You are given a perfect binary tree where all leaves are on t he same level, and every parent has
t wo children. The binary t ree has t he following definit ion:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populat e each next point er t o point t o it s next right node. If t here is no next right node, t he next
point er should be set t o NULL .

Init ially, all next point ers are set t o NULL .

Follow up:

• You may only use const ant ext ra space.

• Recursive approach is fine, you may assume implicit st ack space does not count as ext ra space
for t his problem.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should
 Next
Previous
Populat ing Next Right Point ers in Each
Symmet ric Tree
Node II

Last updat ed 4 years ago

Populating Next Right Pointers in Each Node II

 ht t ps://leet code.com/problems/populat ing-next -right -point ers-in-each-node-ii/

Question Answer

Given a binary t ree

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populat e each next point er t o point t o it s next right node. If t here is no next right node, t he next
point er should be set t o NULL .

Init ially, all next point ers are set t o NULL .

Follow up:

• You may only use const ant ext ra space.

• Recursive approach is fine, you may assume implicit st ack space does not count as ext ra space
for t his problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]

Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populat

Previous Next
Populat ing Next Right Point ers in 106. Const ruct Binary Tree from Inorder
Each Node and Post order Traversal
Last updat ed 4 years ago

106. Construct Binary Tree from

Inorder and Postorder Traversal
ht t ps://leet code.com/problems/const ruct -binary-t ree-from-inorder-and-post order-t raversal/
 Question Answer

Given inorder and post order t raversal of a t ree, const ruct t he binary t ree.

Note:
You may assume t hat duplicat es do not exist in t he t ree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Ret urn t he following binary t ree:

3
/ \
9 20
/ \
15 7

Previous
Next
Populat ing Next Right Point ers in Each
Serialise and Deserialise a Linked List
Node II

Last updat ed 4 years ago

Serialise and Deserialise a Linked List
ht t ps://leet code.com/problems/serialize-and-deserialize-bst /

Question Answer

Serializat ion is convert ing a dat a st ruct ure or object int o a sequence of bit s so t hat it can be
st ored in a file or memory buffer, or t ransmit t ed across a net work connect ion link t o be
reconst ruct ed lat er in t he same or anot her comput er environment .

Design an algorit hm t o serialize and deserialize a binary search tree. There is no rest rict ion on
how your serializat ion/deserializat ion algorit hm should work. You need t o ensure t hat a binary
search t ree can be serialized t o a st ring, and t his st ring can be deserialized t o t he original t ree
st ruct ure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]

Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Previous
Next
106. Const ruct Binary Tree from Inorder
Maximum Dept h of Binary Tree
and Post order Traversal

Last updat ed 4 years ago

Maximum Depth of Binary Tree
ht t ps://leet code.com/problems/maximum-dept h-of-binary-t ree/

Question Answer

Given a binary t ree, find it s maximum dept h.

The maximum dept h is t he number of nodes along t he longest pat h from t he root node down t o
t he fart hest leaf node.

Note: A leaf is a node wit h no children.

Example:

Given binary t ree [3,9,20,null,null,15,7] ,

3
/ \
9 20
/ \
15 7

ret urn it s dept h = 3.

Next
Previous
Lowest Common Ancest or of a
Serialise and Deserialise a Linked List
Binary Tree

Last updat ed 4 years ago

Lowest Common Ancestor of a Binary Tree
ht t ps://leet code.com/problems/lowest -common-ancest or-of-a-binary-t ree/

Question Answer

Given a binary t ree, find t he lowest common ancest or (LCA) of t wo given nodes in t he t ree.

According t o t he definit ion of LCA on Wikipedia: “The lowest common ancest or is defined bet ween
t wo nodes p and q as t he lowest node in T t hat has bot h p and q as descendant s (where we allow
a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of i

Example 3:
 Input: root = [1,2], p = 1, q = 2
Output: 1

Previous Next
Maximum Dept h of Binary Tree n-ary Trees

Last updat ed 4 years ago

n-ary Trees
If you want t o writ e a short art icle on what t rees are, please edit t his page in Git Hub and submit a PR.

Else, read t his:

Tree (dat a st ruct ure)

Wikipedia

Tree Traversal

Previous
Next
Lowest Common Ancest or of a
Unt it led
Binary Tree

Last updat ed 4 years ago

Untitled
Previous Next
n-ary Trees Minimum Height Trees

Last updat ed 4 years ago

Minimum Height Trees
ht t ps://leet code.com/problems/minimum-height -t rees/

Problem Answer

A t ree is an undirect ed graph in which any t wo vert ices are connect ed by exact ly one pat h. In ot her
words, any connect ed graph wit hout simple cycles is a t ree.

Given a t ree of n nodes labelled from 0 t o n - 1 , and an array of n - 1 edges where

edges[i] = [ai, bi] indicat es t hat t here is an undirect ed edge bet ween t he t wo nodes ai
and bi in t he t ree, you can choose any node of t he t ree as t he root . When you select a node x
as t he root , t he result t ree has height h . Among all possible root ed t rees, t hose wit h minimum
height (i.e. min(h) ) are called minimum height trees (MHTs).

Ret urn a list of all MHTs' root labels. You can ret urn t he answer in any order.

The height of a root ed t ree is t he number of edges on t he longest downward pat h bet ween t he
root and a leaf.

Input: n = 4, edges = [[1,0],[1,2],[1,3]]

Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with

Previous Next
Unt it led Binary Search Trees

Last updat ed 4 years ago

Binary Search Trees
A binary t ree is a t ree dat a st ruct ure in which each node has at most t wo children, which are referred t o
as t he left child and t he right child

Binary Tree vs Binary Search Tree

A binary search tree is a binary t ree in which every node fit s a specific ordering propert y.

All left descendant s ≤ n < all right descendant s

This must be t rue for each node, n.

Basically, t he ent ire left side must always be smaller t han t he right on t he same level.

This definit ion can change slight ly. Under some condit ions, t he t ree cannot have duplicat e values. Or
t he duplicat e values will be on t he right side, or on t he left . All are valid, so check wit h your int erviewer.

When given a quest ion, many candidat es assume t he int erviewer means a binary search t ree.

Be sure t o ask!

A binary search tree implies that for each node, its left descendants are less than or equal to
the current node, which is less then the right descendants.

Balanced vs Unbalanced
Ask your int erviewer whet her t he t ree is balanced or unbalanced

Not e: balancing a t ree does not mean left and right subt rees are exact ly t he same size.

One way of t hinking about t his is t hat a balanced t ream means "not t erribly unbalanced". It 's balanced
enough t o ensure O(log n) insert and find, but it 's not necessarily as balanced as it could be.

Complete Binary Tree

Every level of t he t ree is fully filled, except for perhaps t he last level. The last level is filled left t o
right .
Full Binary Trees
Every node has eit her zero or t wo children. No nodes have only one child.

Perfect Binary Trees

Bot h full and complet e. All leaf nodes will be at t he same level, and t his level has t he maximum number
of nodes.

Perfect t rees are rare in int erviews and in real life. Do not assume a binary t ree is perfect in an
int erview.
 Next
Previous
Count ing Maximal Value Root s in
Minimum Height Trees
Binary Tree

Last updat ed 4 years ago

Counting Maximal Value Roots in Binary Tree
ht t ps://binarysearch.com/problems/Count ing-Maximal-Value-Root s-in-Binary-Tree

Question Answer

Given a binary t ree root , count and ret urn t he number of nodes where it s value is great er t han or
equal t o t he values of all of it s descendant s.

For example, given

6
/ \
3 2
/ \
6 4

Ret urn 4 since all nodes except for 2 meet t he crit eria.

Example 1

Input

root = [6, [3, null, null], [2, [6, null, null], [4, null, null]]]

Output

TODO write preorder s postorder vs in order

Previous Next
Binary Search Trees Count BST nodes in a range

Last updat ed 4 years ago

Count BST nodes in a range
ht t ps://binarysearch.com/problems/Count -BST-nodes-in-a-range

Question Answer

Given a binary search t ree root , and int egers lo and hi , ret urn t he count of all nodes in root
whose values are bet ween lo and hi (inclusive).

For example, wit h t his t ree and lo = 5 and hi = 10 , ret urn 3 since only 7, 8, 9 are bet ween
[5, 10] .

3
/ \
2 9
/ \
7 12
/ \
4 8

Example 1

Input

root = [3, null, [5, null, null]]

lo = 4
hi = 7

Output

Previous
Next
Count ing Maximal Value Root s in
Invert a Binary Tree
Binary Tree

Last updat ed 4 years ago

Invert a Binary Tree
Next
Previous
Maximum Difference Bet ween Node
Count BST nodes in a range
and Ancest or

Last updat ed 4 years ago

Maximum Difference
Between Node and Ancestor
ht t ps://leet code.com/problems/maximum-difference-bet ween-node-and-ancest or/

Question Answer

Given t he root of a binary t ree, find t he maximum value V for which t here exist different
nodes A and B where V = |A.val - B.val| and A is an ancest or of B .

A node A is an ancest or of B if eit her: any child of A is equal t o B , or any child of A is an

ancest or of B .

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]

Output: 7
Explanation: We have various ancestor-node differences, some of which are given b
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7
 Previous Next
Invert a Binary Tree Binary Tree Tilt

Last updat ed 4 years ago

Binary Tree Tilt

 ht t ps://leet code.com/problems/binary-t ree-t ilt /

Question Answer

Given t he root of a binary t ree, ret urn the sum of every tree node's tilt.

The tilt of a t ree node is t he absolute difference bet ween t he sum of all left subt ree node
values and all right subt ree node values. If a node does not have a left child, t hen t he sum of t he
left subt ree node values is t reat ed as 0 . The rule is similar if t here t he node does not have a
right child.

Input: root = [1,2,3]

Output: 1
Explanation:
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tile of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right s
Sum of every tilt : 0 + 0 + 1 = 1

Previous
Next
Maximum Difference Bet ween Node
Pract ice
and Ancest or

Last updat ed 4 years ago

Practice
Pract ice problems wit h no hint s on t he dat a st ruct ure / algorit hms t o use!

Previous Next
Binary Tree Tilt What is a Linked List ?

Last updat ed 4 years ago

What is a Linked List?
Linked list s are a dat a st ruct ure. They consist of nodes which hold 2 values:

• Dat a - The dat a t hat node st ores

• Next - The node next in t he list

You can also have doubly linked list s, which remembers it s previous node.

Advantages & Disadvantages

Linked lists are preferable over arrays when:

1. you need const ant -t ime insert ions/delet ions from t he list (such as in real-t ime comput ing where
t ime predict abilit y is absolut ely crit ical)
2. you don't know how many it ems will be in t he list . Wit h arrays, you may need t o re-declare and copy
memory if t he array grows t oo big

3. you don't need random access t o any element s

4. you want t o be able t o insert it ems in t he middle of t he list (such as a priorit y queue)

Arrays are preferable when:

1. you need indexed/random access t o element s

2. you know t he number of element s in t he array ahead of t ime so t hat you can allocat e t he correct
amount of memory for t he array
3. you need speed when it erat ing t hrough all t he element s in sequence. You can use point er mat h on
t he array t o access each element , whereas you need t o lookup t he node based on t he point er for
each element in linked list , which may result in page fault s which may result in performance hit s.

4. memory is a concern. Filled arrays t ake up less memory t han linked list s. Each element in t he array
is just t he dat a. Each linked list node requires t he dat a as well as one (or more) point ers t o t he
ot her element s in t he linked list .

Array List s (like t hose in .Net ) give you t he benefit s of arrays, but dynamically allocat e resources for
you so t hat you don't need t o worry t oo much about list size and you can delet e it ems at any index
wit hout any effort or re-shuffling element s around. Performance-wise, arraylist s are slower t han raw
arrays.

Previous Next
Pract ice Add Two Numbers

Last updat ed 4 years ago

Add Two Numbers
ht t ps://leet code.com/problems/add-t wo-numbers/

Question Answer

You are given t wo non-empty linked list s represent ing t wo non-negat ive int egers. The digit s are
st ored in reverse order, and each of t heir nodes cont ains a single digit . Add t he t wo numbers and
ret urn t he sum as a linked list .

You may assume t he t wo numbers do not cont ain any leading zero, except t he number 0 it self.

Previous Next
What is a Linked List ? Add Two Numbers 2

Last updat ed 4 years ago

Add Two Numbers 2
ht t ps://leet code.com/problems/add-t wo-numbers-ii/

Question Answer

You are given t wo non-empty linked list s represent ing t wo non-negat ive int egers. The most
significant digit comes first and each of t heir nodes cont ain a single digit . Add t he t wo numbers
and ret urn it as a linked list .

You may assume t he t wo numbers do not cont ain any leading zero, except t he number 0 it self.

Follow up:
What if you cannot modify t he input list s? In ot her words, reversing t he list s is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7

Previous Next
Add Two Numbers Reverse a Linked List

Last updat ed 4 years ago

Reverse a Linked List
ht t ps://leet code.com/problems/reverse-linked-list /

Question Answer

Reverse a singly linked list .

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Previous Next
Add Two Numbers 2 Tort oise & Hare Algorit hm

Last updat ed 4 years ago

Tortoise & Hare Algorithm
The Tort oise and t he Hare algorit hm implies we have 2 point ers which have t hese propert ies:

• Point er1 is fast er t han point er2 (t he hare)

• Point er2 is slower t han point er1 (t he t ort oise)

This algorit hm can be implement ed as a linked list like so:

class Solution {
public:
ListNode* middleNode(ListNode* head) {

ListNode* fast = head;

ListNode* slow = fast;

while (fast && fast->next) {

slow = slow->next;
fast = fast->next->next;
}

return slow;
}
};

Or as a regular list like so:

x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

pointer1 = 1
pointer2 = 1

while pointer1 < len(x):

if pointer2 * 2 == pointer1:
# update the position of pointer2 to pointer1
pointer2 = pointer1

Alt hough t his doesn't hit all nodes in t he list , it can be useful t o have a point er t railing behind our hare
point er.

Previous Next
Reverse a Linked List Middle of t he Linked List
Last updat ed 4 years ago

Middle of the Linked List

ht t ps://leet code.com/problems/middle-of-t he-linked-list /submissions/

Question Answer
 Given a non-empt y, singly linked list wit h head node head , ret urn a middle node of linked list .

If t here are t wo middle nodes, ret urn t he second middle node.

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge's serialization of this node is [3,4,5
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NU

Previous Next
Tort oise & Hare Algorit hm Int roduct ion

Last updat ed 4 years ago

Introduction

What is a number base?

Everyone in base2 is a power of 2.

Converting from Int to Binary

First Method
Second Method
This is my personal favourit e met hod, but t o do t his you need t o know your powers of 2.

Powers of 2 are very import ant in comput er science. Binary is represent ed as 2 numbers, so if you have
3 circuit s t hen you will have 2³ numbers, 0 t hrough t o 7.

The powers of 2 are:

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.

And t o make an odd number, we add 1 t o t he list so t he list of numbers we need t o know becomes: 1, 2,
4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.

Okay, say we want t o represent 15 as a binary number. First we need t o split up 15 so it can be made up
of powers of 2 + t he number 1. The nearest power of 2 t hat is less t han 15 is 8, so we’ll use t hat . 8 + 4
is 12. 8 + 4 + 2 is 14, so we’re very nearly t here! Now we just add a 1. 15 represent ed as powers of 2 is
8 + 4 + 2 + 1.

Now we know t his, we can convert t his simply.

The binary t o powers of 2 graph looks like t his.

If t he number uses an 8, put a 1 in t he binary box under it t o represent t hat it uses an 8. I much prefer
t o use t his met hod t hough:

And t hen normally we would need t o reverse t he binary numbers, but in t his case because it ’s all just 1’s
we don’t need t o reverse. If we don’t reverse t hem, we get t he wrong binary number as binary is read
wit h t he highest order of magnit ude t o t he left , not t he lowest . Much like how in “10”, t he 1 is a whole
place higher t han t he 0; t he same applies for binary.

You can convert binary t o decimal in t he opposit e met hod.

Binary Addition
Let ’s first review addit ion in decimal.

23 + 11

We first add 3 + 1, t hat equals 4. t hen we add 2 + 1, which is 3. So t he answer is 34. We add from t he
right t o t he left .

Binary addit ion works t he same.

We will begin wit h one bit (binary digit ) addit ion.

0 + 0 = 1

and

0 + 1 = 1

and

1 + 1 = 10

1 + 1 carries us int o t he next column.

Try it yourself:

111 + 110 = ???

Also, pret t y much every operat or works in t he same way it does wit h binary as wit h decimal.

Negative Numbers in Binary

We can represent a binary number by applying a “sign” t o it .

In Binary, numbers can be 4 bit , 8 bit , 16 bit , 32 bit and so on. If we have an 8 bit number, it ’ll be 8 digit s
long.

So let ’s say we have t he number 1 in 8-bit binary, t hat ’ll be represent ed as: 00000001 t o t urn t his
negat ive, we add a 1 t o t he front of it 10000001

Alt hough t his somet imes causes a problem. Given t he number 0 in 8-bit binary: 00000000 we can make
it negat ive by adding a 1 t o t he front of it . 10000000 But -0, what is t hat ? It ’s not hing. It ’s impossible.
And t hat ’s where t he problem comes from.
Two's Complement
We can make a binary number negat ive by applying two’s complement t o it wit hout t he need t o sign it .

Two’s complement is a really simple algorit hm:

• invert all t he digit s so 0 becomes 1 and 1 becomes 0

• add a +1 t o t he number

and t his makes it negat ive!

So given t he number 15, which is 1111, in 8-bit binary it ’ll be: 00001111 So t o make t his negat ive we
invert all t he digit s: 11110000 t hen we add a 1 t o t he end 11110001 and now t his represent s -15! How
creat ive and cool!

Addition with Negative Numbers

Let ’s say we have 2 numbers, -3 and -5. In binary t hese are: 11, 101 and we want t o add t hem t oget her.

But t his t ime we can ignore any carries t hat go off t he end.

So we use t he largest power of 2 t hat can fit bot h 5 and 3 int o it , which is 8. But t his t ime we make it
negat ive.

Now we simply add t hem. 1 + 1 is 0 carry 1, t he next line is 1 + 1 which is 0 so carry t hat , t he next line is
1 + 1 which is 0 so carry t hat , t he next line is 1 + 1 + 1 which is 1 carry 1, but t his t ime we can t hrow
away t he carry and we’re left wit h 1000 as an answer.

Many t hanks t o Jahan Ulhaque, Comput er Science St udent at Universit y of Liverpool for showing me
t his met hod.

Overflow
Overflow is when more bit s are st ored in t he binary value t han it could hold.

An example of t his is 4 + 7 in 4-bit binary.

 0100 + 0101 + 1001

The correct result , 9, is t oo big t o fit int o 4 bit represent at ion, as t he 1 on t he front makes it negat ive
1.

If bot h input s t o an addit ion have t he same sign, and t he out put sign is different , overflow has
occurred.

Overflow cannot occur if t he signs differ.

Subtraction in Binary
Treat t his as addit ion but negat e t he second operand. So 4–3 is just 4 + (-3)

Which is just

0100 + 1101 = 001as we ignore the carry again.

Adding Numbers
Sum of t wo bit s can be obt ained by performing XOR (^) of t he t wo bit s. Carry bit can be obt ained by
performing AND (&) of t wo bit s.

Sum of 2 bits

0001
xor
0000
=
0001

What if we need t o carry?

0001
xor
0001
=
0000

xor doesn't work. SO we use AND.

Carries
We can use & and t o calculat e whet her we need carries.

1
and
1
=
1

We can t hen use left shift ing, which moves t he number 1 t o t he left .

Right Shifting
The arit hmet ic right shift essent ially divides by 2. The logical right shift would visually shift t he bit s.

Imagine a negat ive number.

In a logical right shift , we shift t he bit s and put a 0 in t he most significant bit . The It is indicat ed wit h a
>>> operat or.

On an 8-bit int eger (where t he sign bit is t he most significant bit ), t his would look like t he image below
(t hat I st ole out of cracking t he coding int erview):

Left Shifting
Does t he opposit e of right shift ing.

Arit hmet ic left shift ing mult iplies by 2.

To mult iply a number, a binary shift moves all t he digit s in t he binary number along t o t he left and fills
t he gaps aft er t he shift wit h 0.
It also visually shift s t he bit s t o t he left .

00 << 1 = 100

Putting it together for adding 2 numbers without using + symbol

# Python3 Program to add two numbers

# without using arithmetic operator
def Add(x, y):

# Iterate till there is no carry

while (y != 0):

# carry now contains common

# set bits of x and y
carry = x & y

# Sum of bits of x and y where at

# least one of the bits is not set
x = x ^ y

# Carry is shifted by one so that

# adding it to x gives the required sum
y = carry << 1

return x

print(Add(15, 32))

# This code is contributed by

# Smitha Dinesh Semwal

Previous Next
Middle of t he Linked List Uncomplet ed

Last updat ed 4 years ago

Uncompleted
List of problems i am still working on. Will move them to the main sections when I figure out how
to explain the solutions better.

Previous Next
Int roduct ion Minimum Cost For Ticket s

Last updat ed 4 years ago

Minimum Cost For Tickets
ht t ps://leet code.com/problems/minimum-cost -for-t icket s/

Question Answer

In a count ry popular for t rain t ravel, you have planned some t rain t ravelling one year in advance.
The days of t he year t hat you will t ravel is given as an array days . Each day is an int eger from
1 t o 365 .

Train t icket s are sold in 3 different ways:

• a 1-day pass is sold for costs[0] dollars;

• a 7-day pass is sold for costs[1] dollars;

• a 30-day pass is sold for costs[2] dollars.

The passes allow t hat many days of consecut ive t ravel. For example, if we get a 7-day pass on
day 2, t hen we can t ravel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Ret urn t he minimum number of dollars you need t o t ravel every day in t he given list of days .

Input: days = [1,4,6,7,8,20], costs = [2,7,15]

Output: 11
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ...
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Previous Next
Uncomplet ed Minimum Falling Pat h Sum

Last updat ed 4 years ago

Minimum Falling Path Sum
ht t ps://leet code.com/problems/minimum-falling-pat h-sum/

Previous
Minimum Cost For Ticket s

Last updat ed 4 years ago