Asymptotic Analysis (Easy/Medium)

Question 1

Two Number Sum

Answer 1

Time: O(n log(n))

Space: O(1)

Question 2

Find Closest Value in BST

Answer 2

Time: O(log(n))

Space: O(1)

Question 3

Depth First Search

Answer 3

Time: O(v + e)

Space: O(v)

Question 4

Nth Fibonacci

Answer 4

Time: O(n)

Space: O(1)

Question 5

Product Sum

Answer 5

Time: O(n)

Space: O(d)
Where d = greatest depth of the ‘special’ arrays

Question 6

Binary Search

Answer 6

Time: O(log(n))

Space: O(1)

Question 7

Find Three Largest Numbers

Answer 7

Time: O(n)

Space: O(1)

Question 8

Bubble Sort

Answer 8

Time: O(n^2)

Space: O(1)

Question 9

Insertion Sort

Answer 9

Time: O(n^2)

Space: O(1)

Question 10

Palindrome Check

Answer 10

Time: O(n)

Space: O(1)

Question 11

Caesar Cipher Encryptor

Answer 11

Time: O(n)

Space: O(n)

Question 12

Branch Sums

Answer 12

Time: O(n)

Space: O(n)

Question 13

Three Number Sum

Answer 13

Time: O(n^2)

Space: O(n)
Remember that the result is all ‘triplets’

Question 14

Smallest Difference

Answer 14

Time: O(n log(n) + m log(m))

Space: O(1)

Question 15

Move Element to End

Answer 15

Time: O(n)

Space: O(1)

Question 16

Validate BST

Answer 16

Time: O(n)

Space: O(d) where d = depth

Question 17

Invert Binary Tree

Answer 17

Time: O(n)

Space: O(d) where d is depth of BST

Question 18

Max Subset Sum No Adjacent

Answer 18

Time: O(n)

Space: O(1)

Question 19

Group Anagrams

Answer 19

Time: O(wn log(n))

Space: O(wn)

Question 20

Levenshstein Distance

Answer 20

Time: O(mn)

Space: O(min(m,n))

Question 21

Kadane’s Algorithm

Answer 21

Time: O(n)

Space: O(1)

Question 22

Minimum number of coins for change

Answer 22

Time: O(nd) where n is target amount and d is number of denominations

Space: O(n)

Question 23

Remove Kth node from the end

Answer 23

Time: O(n)

Space: O(1)

Question 24

Permutations

Answer 24

Time: O(n * n!)

Space: O(n * n!)

Question 25

Balanced Brackets

Answer 25

Time: O(n)

Space: O(n)

Question 26

BST Traversal

Answer 26

Time: O(n)

Space: O(n)

Question 27

RiverSizes

Answer 27

Time: O(wh)

Space: O(wh)

where w = width and h = height of input matrix

Question 28

Youngest Common Ancestor

Answer 28

Time: O(d)

Space: O(1)

Question 29

ZigZag Traverse

Answer 29

Time: O(n)

Space: O(n)

Question 30

Suffix Trie

Answer 30

Creation:
Time: O(n^2)
Space: O(n^2)

Searching:
Time: O(m) where m is length of input string
Space: O(1)

Question 31

Search Sorted Matrix

Answer 31

Time: O(n + m) where n is #rows and m is #columns in matrix

Space: O(1)