AlgoExpert Notes

Easy

Solution 1: HashMap

put all numbers x into HashMap O(n)
traversal array to find if y in the HashMap (y=tragetSum-x) O(n)

Time complexity: O(n)

Space complexity: O(n)

Solution 2: Two pointers

Sort the arrray. O(nLogn)
use Left and Right pointer shrinking the sum to targetSum. O(n)

Time complexity: O(n Log n) Space complexity: O(1)

// JavaScript: O(nlog(n)) | O(1) space 
function twoNumberSum(array, targetSum)

class Program

2. Validate Subsequence

Given a array arr and a sequence s, check if s is subsequence of arr.

Leetcode Problem

Solution: Two Pointers

Pointer a in array and one pointer b in sequence,
if arr[a]!=sequence[b] a++
else a++ & b++
check if b reach end of length of sequence.

Time complexity: O(n) n=array length

Space complexity: O(1)

function isValidSubsequence(array, sequence)

class Program

Solution 2: One Pointer in traversal array

  // O(n) time | O(1) space - where n is the length of the array
  function isValidSubsequence(array, sequence)

class Program

3. Find Closest Value In BST

Given BST and an Integer Value, find the closest value to the target value(12).

Solution: Binary search(while loop/recursion)

Two Integer target and closest
compare target and cur.value to decide go cur.left ot cur.right

Time complexity:O(log(n)) Space complexity: O(1)

While Loop:

 // Average: O(log(n)) time | O(1) space
 // Worst: O(n) time | O(1) space
 function findClosestValueInBst(tree, target) 

 function findClosestValueInBstHelper(tree, target, closest)

class Program

Recursion:

// Average: O(log(n)) time | O(log(n)) space
// Worst: O(n) time | O(n) space
function findClosestValueInBst(tree, target) 

function findClosestValueInBstHelper(tree, target, closest)

class Program

4. Branch Sums

Path Sum

Find all brach sum in the tree added into a list

Solution: Recursion

class BinaryTree 
// O(n) time | O(n) space - where n is the number of nodes in the Binay tree
function branchSums(root) 

function calculateBranchSums(node, runningSum, sums)

class Program

5. Node Depths

Find total depth of each node in Binary Tree.
104. Maximum Depth of Binary Tree

Solution: Recursion, Stack

Recursion:

  //Average case: when the tree is balanced
  // O(n) time | O(h) space - where n is the number of nodes in
  // the Binary Tree and h is the height of the Binary Tree
  function nodeDepths(root, depth = 0) 
  // This is the class of the input binary tree.

  class BinaryTree

class Program

Stack:

// Average case: when the tree is balanced
// O(n) time | O(h) space - where n is the number of nodes in
// the Binary Tree and h is the height of the Binary Tree
function nodeDepths(root) 

// This is the class of the input binary tree.
class BinaryTree

class Program

Solution: Recursion

Call and go Children Node before resolve itself.

class Node

class Program

7. Linked List Construction

Data Structure:

class Node 

class Program {
    static class DoublyLinkedList

8. Nth Fibonacci

Formula :

when n>2 Fib(n)=Fib(n-1)+Fib(n-2)
if n=2 return 1
if n=1 return 0

Solution to get Fib(n): recursion , Iteration (better)

1. recursion

Time complexity: O(n) Space Complexity: O(n)

When we want to Fib(n), use recursion function, and memorized calculated Fib(i) in HashTable.

// O(2^n) time | O(n) space
function getNthFib(n)

Java Code:

class Program

2.iteration (better)

Example: Fib(4)

initial fixed array [0,1]
Fib(2)=0+1=1 update array[1,1] (move index 1 to 0, Fib(2) = index 1)
Fib(3)=1+1=2 update array[1,2]
Fib(4)=1+2=3 return Fib(4)

Time complexity: O(n) Space complexity: O(1)

JavaScript:

// O(n) time | O(n) space
function getNthFib(n, memoize = )

Java Code:

class Program

While Loop

// O(n) time | O(1) space
function getNthFib(n)

9. Product Sum

Product Sum is sum of all the elements in the array.

Recursion:

[7,-1] sum=6, m(depth)=2
[-13,8] sum=5, m=3
Time = O(N), Space = O(D) D=depth of the array there is 3.

JavaScript:

function productSum(array, multiplier = 1)

Java:

class Program

10. Binary Search

Give a sorted array, use Binary Search to find a value val in O(LogN) time complexity, and return its index.

Solution: Left Pointer and Right Pointer

while(left<=right)
index middle=start + ( end – start )/2

JavaScript-Recommend(while loop):

// O(log(n)) time | O(1) space
function binarySearch(array, target) 

function binarySearchHelper(array, target, left, right)

JavaScript(Recursion):

// O(log(n)) time | O(log(n)) space
function binarySearch(array, target) 

function binarySearchHelper(array, target, left, right)

Java(Recursion):

class Program

11. Find Three Largest Numbers

Problem: Give a unsorted array, and return three largest numbers.

Solution: Heap/Fixed Length of array

Fixed Length of array:

initial int[] res =
traversal given array to keep three largest in res.

JavaScript:

// O(n) time | O(1) space
function findThreeLargestNumbers(array) 

function updateLargest(threeLargest, num) 

function shiftAndUpdate(array, num, idx)

Java:

class Program

Solution: Time: O(n²) Space:O(1)

First for loop can push the largest one to the index arr.length-1
Second round loop can push the 2nd Largest one to the index arr.length-2
So on so forth and Loop N times.

Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Java code:

class Program

13. Insertion Sort

Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

JavaScript:

// Best: O(n) time | O(1) space
// Average: O(n^2) time | O(1) space // Worst: O(n^2) time | O(1) space 
function insertionSort(array) 

function swap(i, j, array)

Java code:

class Program

14. Selection Sort

Algorithm:

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

PS: Bubble sort , insertion sort and selection sort may not most efficient sorting algorithm, but they are easy to implement.
Time: O(n) Space: O(1)

class Program

15. Palindrome Check

Solution: Two Pointers

Left Pointer=0, Right Pointer= arr.length-1
if ( arr[Left]=arr[Right]) keep moving to the middle, else return false

JavaScript:

// O(n) time | O(1) space
function isPalindrome(string)

Java:

class Program

16. Caesar Cipher Encryptor

Given String "zhy" and integer value 2. Shifted by 2 = "zab"

A:65 Z:90

a:97 z:122

JavaScript:

// O(n) time | O(n) space
function caesarCipherEncryptor(string, key) 

function getNewLetter(letter, key, alphabet)

Java code:

class Program

Middle

1. Three Number Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets.

Solution: Two Pointers | O(n^2) time | O(n) space

Sort the array in ascending order.
for loop to traverse array, initial Left=i+1, Right=arr.length-1
curSum = arr[i] + arr[left] + arr[right]
while(left
if (curSum>target) , right–, else left++
if(curSum==target) add to result List, then right– && left++

JavaScript Code:

// O(n^2) time | O(n) space
function threeNumberSum(array, targetSum)

Java Code:

class Program

2. Smallest Difference

Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference.

Examples :

Input : 
A[] =  
B[] =  
Output : 3 That is, the pair (11, 8)

Solution: Two Pointers || Time: O( N log( N ) + M log( M )) | Space: O( 1 )

Sort two array A, B with length N, M in ascending order.
while ( ismallest to get min difference.
Start two pointers i, j from A[ 0 ], B[ 0 ], then compare pointers
if A[ i ] < B[ j ], i++, else j++
if A[ i ] = B[ j ] return pair ( A[ i ], B[ j ] )

JavaScript Code:

// O(nlog(n) + mlog(m)) time | O(1) space
function smallestDifference(arrayOne, arrayTwo)

Java Code:

class Program

3. Move Element To End

Given an array and Integer toMove, move all the toMoves in array to the end in O(1) space complexity.

Example:

1 2	The original list is : ['3', '5', '7', '9', '11'] ToMove : 5 The modified element moved list is : ['3', '7', '9', '11', '5']

Solution: Two Pointers || Time : O ( N ) | Space : O ( 1 )

i = 0, j = arr.length – 1
while( i < j )
while( i < j and arr [ j ] = toMove) then j–
if ( arr[ i ]==toMove ) then swap ( arr[ i ] , arr[ j ] ) , i++
return array

JavaScript Code:

// O(n) time | O(1) space - where n is the length of the array 
function moveElementToEnd(array, toMove) 

function swap(i, j, array)

Java Code:

class Program

4. Monotonic Array

Give an array, return true or false if it's Monotonic Array. Monotonic can be entirely Non-Decreasing or Non-Increasing.

Tricky: Array may contain duplicate Integer.

896. Monotonic Array

Solution: || Time : O ( N ) | Space : O ( 1 )

determine the direction ( downward or upward trending )

JavaScript Code:

// O(n) time | O(1) space - n = length of the array 
function isMonotonic(array)

Java Code:

class Program

5. Spiral Traverse

Given an m x n matrix, return all elements of the matrix in spiral order. N: total number of vertices

54. Spiral Matrix

Solution: Iteration || Time : O ( N ) | Space : O ( 1 ) / Recursion || Time : O ( N ) | Space : O ( N )

initial four pointers:
startColomn = 0, endColomn = arr[0].length - 1, startRow = 0, endRow = arr.length-1
use iterative method (optimal) or recursive method to traverse 2D array.

Shrink to calculate inner perimeter:

Iterative method:

JavaScript Code:

// O(n) time | O(n) space - where n is the total number of elements in the array 
function spiralTraverse(array)

Java Code:

class Program

Recursive method:

JavaScript Code:

// O(n) time | O(n) space - where n is the total number of elements in the array 
function spiralTraverse(array)

Java Code:

class Program

6. Longest Peak

Peak i definitions:

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

845. Longest Mountain in Array

Solution: Time O(n) | Space O(1)

Iterate array to Find peeks in the array, once find a peek, expand its left and right to see how far this peek goes, then save its length to compare next length of finding peek. O(n)

Old Method：

Iterate array to Find all peeks in the array. O(n)
compare each peek length to get longest peek. O(n)

Example: Traversing the array, find 4 is one peek, expand its left and right to get length=3, save it and continue, find 10 is peek, expand to get it length =6, compare Math.max(4,6) =6…To the end of array. return the length.

JavaScript Code:

// O(n) time | O(1) space - where n is the length of the input array 
function longestPeak(array)

Java Code:

class Program

8. Validate BST

Problem : Return true or false to validate if it's Binary Search Tree.

Leetcode Link

JavaScript Code:

class BST 
// O(n) time | O(d) space 
function validateBst(tree) 

function validateBstHelper(tree, minValue, maxValue) 
exports.BST = BST;
exports.validateBst = validateBst;

Java Code:

class Program

9. BTS Traversal

Problem : use Pre-order, In-order, Post-order to traverse a Binary Search Tree

Solution : Recursion

Pre-order:

function preorder(root)
   if not root: return
   print(root.val)
   preorder(root.left)
   preorder(root.right)

In-order:

function preorder(root)
   if not root: return
   preorder(root.left)
   print(root.val)
   preorder(root.right)

Post-order:

function preorder(root)
   if not root: return
   preorder(root.left)
   preorder(root.right)
   print(root.val)

JavaScript Code:

// O(n) time | O(n) space
function inOrderTraverse(tree, array) 
// O(n) time | O(n) space
function preOrderTraverse(tree, array) 
// O(n) time | O(n) space
function postOrderTraverse(tree, array) 
exports.inOrderTraverse = inOrderTraverse;
exports.preOrderTraverse = preOrderTraverse;
exports.postOrderTraverse = postOrderTraverse;

Java Code:

class Program

10. Min Height BST

Problem : Given a distinct Sorted array, build a Minimum Height BST

Solution : Recursion

Find the middle value as root Node A, then all the values in the left of root will be placed in the left of BST, and all the values in the right of root will be placed in the right of BST. Use same function to find Left and Right Node of A…

JavaScript Code:

// O(n) time | O(n) space - where n is the length of the array 

function minHeightBst(array) 

function constructMinHeightBst(array, startIdx, endIdx) 
class BST

Java Code:

class Program

11. Invert Binary Tree

Problem: invert the BST

Solution: While loop && Recursion

BFS the tree into queue, use queue to traverse it, level by level from top.

poll root node from queue
swap (root.left, root.right), add into queue
repeat step one until queue is empty

While loop:
JavaScript:

// O(n) time | O(n) space
function invertBinaryTree(tree) 

function swapLeftAndRight(tree)

Recursion:
JavaScript:

// O(n) time | O(d) space
function invertBinaryTree(tree) 

function swapLeftAndRight(tree)

12. Max Subset Sum No Adjacent ( DP )

Problem : Given an array with only positive integers, find max subset sum no adjacent

Solution: DP

Formula :

Java Code ( Optimal ) Use 3 Integers : Current = Max ( First , Second ) instead of DP array :

JavaScript:

// O(n) time | O(1) space
function maxSubsetSumNoAdjacent(array)

Java:

class Program

13). Number Of Ways To Make Change ( DP )

Your Content Goes Here

14). Min Number Of Coins For Change

Your Content Goes Here

15. Levenshtein Distance ( DP )

Problem:

Formula:

Time Complexity (space in optimal solution based on 2rows or 2columns):

JavaScript(optimal):

// O(nm) time | O(min(n, m)) space
function levenshteinDistance(str1, str2)

Java Code :

class Program

Optimal:

class Program

16). Kadane's Algorithm ( DP )

Your Content Goes Here

17. Single Cycle Check

Problem:

Given an array , return boolean if it has a single cycle: number of forward steps are based on value in array, finally re-arrive to starting index by visiting all indices just once.

Leetcode:

457. Circular Array Loop

Solution: While loop

Extra space: use another array (initial vaule=0) to record number of visit, if any vaule >1, return false

No extra space:
Edge cases:

when we are back to starting index and total number of visited index
when total number of visited =N, and we are not back to starting index, return false

JavaScript:

// O(n) time | O(1) space - where n is the length of the input array 
function hasSingleCycle(array) 

function getNextIdx(currentIdx, array)

Java Code:

class Program

18. Breadth-first Search

Problem:

Use BFS to traverse all node of G (V,E), and put them into an array, then return the array.

Solution: Queue+While loop

Time complexity : O ( | V | + | E | ) ; Space complexity: O ( | V | )

JavaScript:

// O(n) time | O(1) space - where n is the length of the input array 
function hasSingleCycle(array) 

function getNextIdx(currentIdx, array)

Java Code :

class Program

19. River Sizes

Problem:

Given an m x n 2d grid map of '1's (river) and '0's (land), return the number of islands. Return an array, each value = length of a river.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Leetcode: 200. Number of Islands

Solution:

Traverse matrix

if matrix [ x ] [ y ]=1, apply BFS or DFS to find length of this river

push length into result array, then mark them as visited… Next, continue traverse matrix

Finally, return the result array.

JavaScript:

// O(wh) time | O(wh) space
function riverSizes(matrix) 

function traverseNode(i, j, matrix, visited, sizes) 

function getUnvisitedNeighbors(i, j, matrix, visited)

Java Code:

class Program

20. Youngest Common Ancestor ( Graph )

Problem:

Given three Nodes: top_Ancestor, descendant_One, descendant_Two. find and return the youngest common ancestor of One and Two.

Leetcode:

235. Lowest Common Ancestor of a Binary Search Tree

236. Lowest Common Ancestor of a Binary Tree

Solution: Time: O( D ) || Space: O( 1 )

D=depth of lowest node of One and Two

Bring two nodes to the same level ,

then go up step by step using while loop

return if go up step are the same.

find the depth of two nodes a, b, steps to same level= |a-b|

JavaScript:

class AncestralTree 
// O(d) time | O(1) space - where d is the depth (height) of the ancestral tree 
function getYoungestCommonAncestor(topAncestor, descendantOne, descendantTwo) 

function getDescendantDepth(descendant, topAncestor) 

function backtrackAncestralTree(lowerDescendant, higherDescendant, diff) 

exports.AncestralTree = AncestralTree;
exports.getYoungestCommonAncestor = getYoungestCommonAncestor;

Java Code:

class Program

21. Min Heap Construction

22. Remove Nth Node From End

Problem: Given head of Linked List, Remove Nth Node From End.

Solution: Two Pointers || Time: O(N) Space: O(1)

let Slow Fast Pointer =head, let fast pointer move N steps, Now Fast Point is N nodes ahead of Slow Pointer.
Continuing move both Pointers to traverse Linked List until Fast.Next=null, remove slow pointer node: slow.previous=slow.next.

Edge case: N=length of Linked List, when Fast move N node, Fast=null, return slow.next node.
JavaScript:

class LinkedList  

// O(n) time | O(1) space
function removeKthNodeFromEnd(head, k) 
exports.LinkedList = LinkedList;
exports.removeKthNodeFromEnd = removeKthNodeFromEnd;

Java Code:

class Program

23. Permutations

Problem: Given an array with unique integers, return all possible array.

Solution: Swap in Array (Optimal), Recursion.

Swap Code:

JavaScript:

// Upper Bound: O(n^2*n!) time | O(n*n!) space
// Roughly: O(n*n!) time | O(n*n!) space
function getPermutations(array) 

function permutationsHelper(array, currentPermutation, permutations) 
exports.getPermutations = getPermutations;

Java:

class Program

Recursion Code:
JavaScript:

// O(n*n!) time | O(n*n!) space
function getPermutations(array) 

function permutationsHelper(i, array, permutations) 

function swap(i, j, array) 
exports.getPermutations = getPermutations;

Java:

class Program

24. Powerset

Problem: Given an array, return the Powerset. it's defined as the set of all sub of another set.

Solution: Iteration or Recursion

Iteration: Time,Space=O(2^n*n)

[]
add 1,
add 2,
add 3,

JavaScript:

// O(n*2^n) time | O(n*2^n) space
function powerset(array) 
exports.powerset = powerset;

Java Code:

class Program

25. Search In Sorted Matrix

Problem: Given a sorted Matrix and an Integer, return the index of the Integer in that Matrix.

Solution: While lopp

Martix[row][col]
starts from Top Left
if(Martix[row][col] >targer) col--;
if(Martix[row][col]


else return Martix[row][col]


JavaScript:






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// O(n + m) time | O(1) space
function searchInSortedMatrix(matrix, target) 
exports.searchInSortedMatrix = searchInSortedMatrix;





Java:







 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Program

`26. Min Max Stack Construction`


Problem: Define Min Max Stack Data Structure with peek(), pop(), push(), getMin(), getMax().
Solution:

Use List> minMaxStack to store history min and max value.
Use List stack to store Stack Values



JavaScript:






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class MinMaxStack 





Java Code:






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class MinMaxStack

`27. Balanced Brackets`

`28. Longest Palindromic Substring`


Problem: Given a String, return  the Longest Palindromic Substring.
A palindrome [pælin'drɔmik] is defined as a string that's written the same forward as backward.
Solution: Iteration || Time=O(n^2)  Space=O(1)
Traverse the String to check each center and expand from them.

At index i, if (Str[i-1]==Str[i+1]) odd
else if(Str[i]==Str[i-1]) even

Palindrome can be either if even length or odd length.


JavaScript:






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// O(n^2) time | O(1) space
function longestPalindromicSubstring(string) 

function getLongestPalindromeFrom(string, leftIdx, rightIdx) 
exports.longestPalindromicSubstring = longestPalindromicSubstring;





JavaScript:






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// O(w * n * log(n)) time | O(wn) space - where w is the number of words and n is 
function groupAnagrams(words) 
exports.groupAnagrams = groupAnagrams;





Java Code:






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


class Program

`29. Group Anagrams`


Problem:
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Leetcode: 49. Group Anagrams
Solution: check out comments in Code
Java Code:






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Program

`30. Suffix Trie Construction`


Problem : Construct Suffix Trie Tree in order to recognize if given string a is suffix of string b
Asterisk means end of the string.


JavaScript:






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


class SuffixTrie 





Java Code:







 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


class TrieNode

AlgoExpert Notes

Solution 1: HashMap

Solution 2: Two pointers

Solution: Two Pointers

Solution 2: One Pointer in traversal array

Solution: Binary search(while loop/recursion)

Solution: Recursion

Solution: Recursion, Stack

Solution: Recursion

Solution to get Fib(n): recursion , Iteration (better)

1. recursion

2.iteration (better)

While Loop

Recursion:

Solution: Left Pointer and Right Pointer

Solution: Heap/Fixed Length of array

Fixed Length of array:

Solution: Time: O(n2) Space:O(1)

Algorithm:

Solution: Two Pointers

Solution: Two Pointers | O(n^2) time | O(n) space

Solution: Two Pointers || Time: O( N log( N ) + M log( M )) | Space: O( 1 )

Solution: || Time : O ( N ) | Space : O ( 1 )

Solution: Iteration || Time : O ( N ) | Space : O ( 1 ) / Recursion || Time : O ( N ) | Space : O ( N )

Solution: Time O(n) | Space O(1)

Problem : use Pre-order, In-order, Post-order to traverse a Binary Search Tree

Solution : Recursion

Problem : Given a distinct Sorted array, build a Minimum Height BST

Solution : Recursion

Find the middle value as root Node A, then all the values in the left of root will be placed in the left of BST, and all the values in the right of root will be placed in the right of BST. Use same function to find Left and Right Node of A…

JavaScript Code:

Java Code:

Problem: invert the BST

Solution: While loop && Recursion

BFS the tree into queue, use queue to traverse it, level by level from top.

Problem : Given an array with only positive integers, find max subset sum no adjacent

Solution: DP

Formula :

Java Code ( Optimal ) Use 3 Integers : Current = Max ( First , Second ) instead of DP array :

Problem:

Formula:

Time Complexity (space in optimal solution based on 2*rows or 2*columns):

Java Code :

Optimal:

Problem:

Leetcode:

Solution: While loop

Java Code:

Problem:

Solution: Queue+While loop

Problem:

Solution:

Java Code:

Problem:

Leetcode:

Solution: Time: O( D ) || Space: O( 1 )

Java Code:

Problem: Given head of Linked List, Remove Nth Node From End.

Solution: Two Pointers || Time: O(N) Space: O(1)

Java Code:

Problem: Given an array with unique integers, return all possible array.

Solution: Swap in Array (Optimal), Recursion.

Swap Code:

Recursion Code: JavaScript: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 // O(n*n!) time | O(n*n!) space function getPermutations(array) function permutationsHelper(i, array, permutations) function swap(i, j, array) exports.getPermutations = getPermutations; Java:

Problem: Given an array, return the Powerset. it's defined as the set of all sub of another set.

Solution: Iteration or Recursion

Java Code:

Problem: Given a sorted Matrix and an Integer, return the index of the Integer in that Matrix.

Solution: While lopp

Problem: Define Min Max Stack Data Structure with peek(), pop(), push(), getMin(), getMax().

Solution:

Java Code:

Problem: Given a String, return the Longest Palindromic Substring.

Solution: Iteration || Time=O(n^2) Space=O(1)

Java Code:

Problem:

Solution: check out comments in Code

Java Code:

Problem : Construct Suffix Trie Tree in order to recognize if given string a is suffix of string b

Share This Story, Choose Your Platform!

Solution: Time: O(n²) Space:O(1)

Time Complexity (space in optimal solution based on 2rows or 2columns):

Recursion Code:
JavaScript:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// O(nn!) time | O(nn!) space function getPermutations(array) function permutationsHelper(i, array, permutations) function swap(i, j, array) exports.getPermutations = getPermutations;

Java:

Problem: Define Min Max Stack Data Structure with `peek(), pop(), push(), getMin(), getMax()`.

Problem: Given a `String`, return the Longest Palindromic Substring.

Problem : Construct Suffix Trie Tree in order to recognize if given `string a` is suffix of `string b`