AlgoExpert Notes

Easy

Solution 1: HashMap

put all numbers x into HashMap<Integer,Boolean> 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) {
    array.sort((a, b) => a - b);
    let left = 0;
    let right = array.length - 1;
    while (left < right) {
        const currentSum = array[left] + array[right];
        if (currentSum === targetSum) {
            return [array[left], array[right]];
        } else if (currentSum < targetSum) {
            left++;
        } else if (currentSum > targetSum) {
            right--;
        }
    }
    return [];
}

class Program {
        // O(nlog(n)) | O(1) space
        public static int[] twoNumberSum(int[] array, int targetSum) {
            Arrays.sort(array);
            int left = 0;
            int right = array.length - 1;
            while (left < right) {
                int currentSum = array[left] + array[right];
                if (currentSum == targetSum) {
                    return new int[]{array[left], array[right]};
                } else if (currentSum < targetSum) {
                    left++;
                } else if (currentSum > targetSum) {
                    right--;
                }
            }
            return new int[0];
        }
    }

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) {
    let arrIdx = 0;
    let seqIdx = 0;
    while (arrIdx < array.length && seqIdx < sequence.length) {
        if (array[arrIdx] === sequence[seqIdx]) seqIdx++;
        arrIdx++;
    }
    return seqIdx === sequence.length;
}

class Program {
        // O(n) time | O(1) space - where n is the length of the array 
        public static boolean isValidSubsequence(List<Integer> array, List<Integer> sequence) {
            int arrIdx = 0;
            int seqIdx = 0;
            while (arrIdx < array.size() && seqIdx < sequence.size()) {
                if (array.get(arrIdx) == sequence.get(seqIdx)) {
                    seqIdx++;
                }
                arrIdx++;
            }
            return seqIdx == sequence.size();
        }
    }

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) {
      let seqIdx = 0;
      for (const value of array) {
          if (seqIdx === sequence.length) break;
          if (sequence[seqIdx] === value) seqIdx++;
      }
      return seqIdx === sequence.length;
  }

class Program {
        // O(n) time | O(1) space - where n is the length of the array 
        public static boolean isValidSubsequence(List<Integer> array, List<Integer> sequence) {
            int seqIdx = 0;
            for (var value : array) {
                if (seqIdx == sequence.size()) {
                    break;
                }
                if (sequence.get(seqIdx) == value) {
                    seqIdx++;
                }
            }
            return seqIdx == sequence.size();
        }
    }

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) {
     return findClosestValueInBstHelper(tree, target, Infinity);
 }

 function findClosestValueInBstHelper(tree, target, closest) {
     let currentNode = tree;
     while (currentNode !== null) {
         if (Math.abs(target - closest) > Math.abs(target - currentNode.val)) {
             closest = currentNode.value;
         }
         if (target < currentNode.value) {
             currentNode = currentNode.left;
         } else if (target > currentNode.value) {
             currentNode = currentNode.right;
         } else {
             break;
         }
     }
     return closest;
 }

class Program {
        // Average: O(log(n)) time | O(1) space // Worst: O(n) time | O(1) space
        public static int findClosestValueInBst(BST tree, int target) {
            return findClosestValueInBst(tree, target, Double.MAX_VALUE);
        }

        public static int findClosestValueInBst(BST tree, int target, double closest) {
            BST currentNode = tree;
            while (currentNode != null) {
                if (Math.abs(target - closest) > Math.abs(target - currentNode.value) {
                    closest = currentNode.value;
                }
                if (target < currentNode.value) {
                    currentNode = currentNode.left;
                } else if (target > currentNode.value) {
                    currentNode = currentNode.right;
                } else {
                    break;
                }
                return (int) closest;
            }
        }

        static class BST {
            public int value;
            public BST left;
            public BST right;

            public BST(int value) {
                this.value = value;
            }
        }

    }

Recursion:

// Average: O(log(n)) time | O(log(n)) space
// Worst: O(n) time | O(n) space
function findClosestValueInBst(tree, target) {
    return findClosestValueInBstHelper(tree, target, Infinity);
}

function findClosestValueInBstHelper(tree, target, closest) {
    if (tree === null) return closest;
    if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
        closest = tree.value;
    }
    if (target < tree.value) {
        return findClosestValueInBstHelper(tree.left, target, closest);
    } else if (target > tree.value) {
        return findClosestValueInBstHelper(tree.right, target, closest);
    } else {
        return closest;
    }
}

class Program {
        // Average: O(log(n)) time | O(log(n)) space // Worst: O(n) time | O(n) space
        public static int findClosestValueInBst(BST tree, int target) {
            return findClosestValueInBst(tree, target, Double.MAX_VALUE);
        }

        public static int findClosestValueInBst(BST tree, int target, double closest) {
            if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
                closest = tree.value;
            }
            if (target < tree.value && tree.left != null) {
                return findClosestValueInBst(tree.left, target, closest);
            } else if (target > tree.value && tree.right != null) {
                return findClosestValueInBst(tree.right, target, closest);
            } else {
                return (int) closest;
            }
        }

        static class BST {
            public int value;
            public BST left;
            public BST right;

            public BST(int value) {
                this.value = value;
            }
        }
    }

4. Branch Sums

Path Sum

Find all brach sum in the tree added into a list

Solution: Recursion

class BinaryTree {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
// O(n) time | O(n) space - where n is the number of nodes in the Binay tree
function branchSums(root) {
    const sums = [];
    calculateBranchSums(root, 0, sums);
    return sums;
}

function calculateBranchSums(node, runningSum, sums) {
    if (!node) return;
    const newRunningSum = runningSum + node.value;
    if (!node.left && !node.right) {
        sums.push(newRunningSum);
        return;
    }
    calculateBranchSums(node.left, newRunningSum, sums);
    calculateBranchSums(node.right, newRunningSum, sums);
}

class Program {
        public static class BinaryTree {
            int value;
            BinaryTree left;
            BinaryTree right;

            BinaryTree(int value) {
                this.value = value;
                this.left = null;
                this.right = null;
            }
        }

        // O(n) time | O(n) space - where n is the number of nodes in the Bi
        public static List<Integer> branchSums(BinaryTree root) {
            List<Integer> sums = new ArrayList<Integer>();
            calculateBranchSums(root, 0, sums);
            return sums;
        }

        public static void calculateBranchSums(BinaryTree node, int runningSum, List<Integer> sums) {
            if (node == null) return;
            int newRunningSum = runningSum + node.value;
            if (node.left == null && node.right == null) {
                sums.add(newRunningSum);
                return;
            }
        }
    }

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) {
      if (root === null) return 0;
      return depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1);
  }
  // This is the class of the input binary tree.

  class BinaryTree {
      constructor(value) {
          this.value = value;
          this.left = null;
          this.right = null;
      }
  }

class Program {
    // 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
    public static int nodeDepths(BinaryTree root) {
        return nodeDepthsHelper(root, 0);
    }

    public static int nodeDepthsHelper(BinaryTree root, int depth) {
        if (root == null) return 0;
        return depth + nodeDepthsHelper(root.left, depth + 1) + nodeDepthsHelper(root.right, depth + 1);
    }

    static class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        public BinaryTree(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
}

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) {
    let sumOfDepths = 0;
    const stack = [{
        node: root,
        depth: 0
    }];
    while (stack.length > 0) {
        const {
            node,
            depth
        } = stack.pop();
        if (node === null) continue;
        sumOfDepths += depth;
        stack.push({
            node: node.left,
            depth: depth + 1
        });
        stack.push({
            node: node.right,
            depth: depth + 1
        });
    }
    return sumOfDepths;
}

// This is the class of the input binary tree.
class BinaryTree {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class Program {
    // 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
    public static int nodeDepths(BinaryTree root) {
        int sumOfDepths = 0;
        List<Level> stack = new ArrayList<Level>();
        stack.add(new Level(root, 0));
        while (stack.size() > 0) {
            Level top = stack.remove(stack.size() - 1);
            BinaryTree node = top.root;
            int depth = top.depth;
            if (node == null) continue;
            sumOfDepths += depth;
            stack.add(new Level(node.left, depth + 1));
            stack.add(new Level(node.right, depth + 1));
        }
        return sumOfDepths;
    }

    static class Level {
        public BinaryTree root;
        int depth;

        public Level(BinaryTree root, int depth) {
            this.root = root;
            this.depth = depth;
        }
    }

    static class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        public BinaryTree(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
}

Solution: Recursion

Call and go Children Node before resolve itself.

class Node {
    constructor(name) {
        this.name = name;
        this.children = [];
    }
    addChild(name) {
        this.children.push(new Node(name));
        return this;
    }
    // O(v + e) time | O(v) space
    depthFirstSearch(array) {
        array.push(this.name);
        for (const child of this.children) {
            child.depthFirstSearch(array);
        }
        return array;
    }
}

class Program {
    static class Node {
        String name;
        List<Node> children = new ArrayList<Node>();

        public Node(String name) {
            this.name = name;
        }

        // O(v + e) time | O(v) space 
        public List<String> depthFirstSearch(List<String> array) {
            array.add(this.name);
            for (int i = 0; i < children.size(); i++) {
                children.get(i).depthFirstSearch(array);
            }
            return array;
        }

        public Node addChild(String name) {
            Node child = new Node(name);
            children.add(child);
            return this;
        }
    }
}

7. Linked List Construction

Data Structure:

class Node {
    public int value;
    public Node prev;
    public Node next;

    public Node(int value) {
        this.value = value;
    }
}

class Program {
    static class DoublyLinkedList {
        public Node head;
        public Node tail;

        // O(1) time | O(1) space
        public void setHead(Node node) {
            if (head == null) {
                head = node;
                tail = node;
                return;
            }
            insertBefore(head, node);
        }

        // O(1) time | O(1) space
        public void setTail(Node node) {
            if (tail == null) {
                setHead(node);
                return;
            }

            insertAfter(tail, node);

        }

        // O(1) time | O(1) space
        public void insertBefore(Node node, Node nodeToInsert) {
            if (nodeToInsert == head && nodeToInsert == tail) return;
            remove(nodeToInsert);
            nodeToInsert.prev = node.prev;
            nodeToInsert.next = node;
            if (node.prev == null) {
                head = nodeToInsert;
            } else {
                node.prev.next = nodeToInsert;
            }
            node.prev = nodeToInsert;
        }

        // O(1) time | O(1) space
        public void insertAfter(Node node, Node nodeToInsert) {
            if (nodeToInsert == head && nodeToInsert == tail) return;
            remove(nodeToInsert);
            nodeToInsert.prev = node;
            nodeToInsert.next = node.next;
            if (node.next == null) {
                tail = nodeToInsert;
            } else {
                node.next.prev = nodeToInsert;
            }
            node.next = nodeToInsert;
        }

        // O(p) time | O(1) space
        public void insertAtPosition(int position, Node nodeToInsert) {
            if (position == 1) {
                setHead(nodeToInsert);
                return;
            }
            Node node = head;
            int currentPosition = 1;
            while (node != null && currentPosition++ != position) node = nod if (node != null) {
                insertBefore(node, nodeToInsert);
            } else {
                setTail(nodeToInsert);
            }
        }

        // O(n) time | O(1) space
        public void removeNodesWithValue(int value) {
            Node node = head;
            while (node != null) {
                Node nodeToRemove = node;
                node = node.next;
                if (nodeToRemove.value == value) remove(nodeToRemove);
            }
        }

        // O(1) time | O(1) space
        public void remove(Node node) {
            if (node == head) head = head.next;
            if (node == tail) tail = tail.prev;
            removeNodeBindings(node);
        }

        // O(n) time | O(1) space
        public boolean containsNodeWithValue(int value) {
            Node node = head;
            while (node != null && node.value != value) node = node.next;
            return node != null;
        }

        public void removeNodeBindings(Node node) {
            if (node.prev != null) node.prev.next = node.next;
            if (node.next != null) node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }
    }

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) {
    if (n === 2) {
        return 1;
    } else if (n === 1) {
        return 0;
    } else {
        return getNthFib(n - 1) + getNthFib(n - 2);
    }
}

Java Code:

class Program {
    // O(n) time | O(n) space
    public static int getNthFib(int n) {
        Map<Integer, Integer> memoize = new HashMap<Integer, Integer>();
        memoize.put(1, 0);
        memoize.put(2, 1);
        return getNthFib(n, memoize);
    }

    public static int getNthFib(int n, Map<Integer, Integer> memoize) {
        if (memoize.containsKey(n)) {
            return memoize.get(n);
        } else {
            memoize.put(n, getNthFib(n - 1, memoize) + getNthFib(n - 2, memoize); 
            return memoize.get(n);
        }
    }
}

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 = {
    1: 0,
    2: 1
}) {
    if (n in memoize) {
        return memoize[n];
    } else {
        memoize[n] = getNthFib(n - 1, memoize) + getNthFib(n - 2, memoize)
        return memoize[n];
    }
}

Java Code:

class Program {
    // O(n) time | O(1) space 
    public static int getNthFib(int n) {
        int[] lastTwo = {0, 1};
        int counter = 3;
        while (counter <= n) {
            int nextFib = lastTwo[0] + lastTwo[1];
            lastTwo[0] = lastTwo[1];
            lastTwo[1] = nextFib;
            counter++;
        }
        return n > 1 ? lastTwo[1] : lastTwo[0];
    }
}

While Loop

// O(n) time | O(1) space
function getNthFib(n) {
    const lastTwo = [0, 1];
    let counter = 3;
    while (counter <= n) {
        const nextFib = lastTwo[0] + lastTwo[1];
        lastTwo[0] = lastTwo[1];
        lastTwo[1] = nextFib;
        counter++;
    }
    returnn > 1 ? lastTwo[1] : lastTwo[0];
}

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) {
    letsum = 0;
    for (const element of array) {
        if (Array.isArray(element)) {
            sum += productSum(element, multiplier + 1);
        } else {
            sum += element;
        }
    }
    return sum * multiplier;
}

Java:

class Program {
    // O(n) time | O(d) space - where n is the total number of elements // including sub-elements, and d is the greatest depth of "special"
    public static int productSum(List<Object> array) {
        return productSumHelper(array, 1);
    }

    public static int productSumHelper(List<Object> array, int multiplie int sum=0;for(Object el:array) {
        if (el instanceof ArrayList) {
            @SuppressWarnings("unchecked") 
            ArrayList<Object> ls = (ArrayList<Object>) el;
            sum += productSumHelper(ls, multiplier + 1);
        } else {
            sum += (int) el;
        }
        return sum *multiplier;
    }
}

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) {
    return binarySearchHelper(array, target, 0, array.length - 1);
}

function binarySearchHelper(array, target, left, right) {
    while (left <= right) {
        const middle = Math.floor((left + right) / 2);
        const potentialMatch = array[middle];
        if (target === potentialMatch) {
            return middle;
        } else if (target < potentialMatch) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}

JavaScript(Recursion):

// O(log(n)) time | O(log(n)) space
function binarySearch(array, target) {
    return binarySearchHelper(array, target, 0, array.length - 1);
}

function binarySearchHelper(array, target, left, right) {
    if (left > right) return -1;
    const middle = Math.floor((left + right) / 2);
    const potentialMatch = array[middle];
    if (target === potentialMatch) {
        return middle;
    } else if (target < potentialMatch) {
        return binarySearchHelper(array, target, left, middle - 1);
    } else {
        return binarySearchHelper(array, target, middle + 1, right);
    }
}

Java(Recursion):

class Program {
    // O(log(n)) time | O(1) space
    public static int binarySearch(int[] array, int target) {
        return binarySearch1(array, target, 0, array.length - 1);
    }
    
    public static int binarySearch1(int[] array, int target, int left, int right) {
        while (left <= right) {
            int middle = left+(right-left)/2;
            int potentialMatch = array[middle];
            if (target == potentialMatch) {
                return middle;
            } else if (target < potentialMatch) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return -1;
    }
}

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 ={INT_MIN,INT_MIN,INT_MIN}
traversal given array to keep three largest in res.

JavaScript:

// O(n) time | O(1) space
function findThreeLargestNumbers(array) {
    const threeLargest = [null, null, null];
    for (const num of array) {
        updateLargest(threeLargest, num);
    }
    return threeLargest;
}

function updateLargest(threeLargest, num) {
    if (threeLargest[2] === null || num > threeLargest[2]) {
        shiftAndUpdate(threeLargest, num, 2);
    } else if (threeLargest[1] === null || num > threeLargest[1]) {
        shiftAndUpdate(threeLargest, num, 1);
    } else if (threeLargest[0] === null || num > threeLargest[0]) {
        shiftAndUpdate(threeLargest, num, 0);
    }
}

function shiftAndUpdate(array, num, idx) {
    for (let i = 0; i <= idx; i++) {
        if (i === idx) {
            array[i] = num;
        } else {
            array[i] = array[i + 1];
        }
    }
}

Java:

class Program {
    // O(n) time | O(1) space
    public static int[] findThreeLargestNumbers(int[] array) {
        int[] threeLargest = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE}
        for (int num : array) {
            updateLargest(threeLargest, num);
        }
        return threeLargest;
    }

    public static void updateLargest(int[] threeLargest, int num) {
        if (num > threeLargest[2]) {
            shiftAndUpdate(threeLargest, num, 2);
        } else if (num > threeLargest[1]) {
            shiftAndUpdate(threeLargest, num, 1);
        } else if (num > threeLargest[0]) {
            shiftAndUpdate(threeLargest, num, 0);
        }
    }

    public static void shiftAndUpdate(int[] array, int num, int idx) {
        for (int i = 0; i <= idx; i++) {
            if (i == idx) {
                array[i] = num;
            } else {
                array[i] = array[i + 1];
            }
        }
    }
}

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 {
    // Best: O(n) time | O(1) space // Average: O(n^2) time | O(1) space
    // Worst: O(n^2) time | O(1) space
    public static int[] bubbleSort(int[] array) {
        if (array.length == 0) {
            return new int[]{};
        }
        boolean isSorted = false;
        int counter = 0;
        while (!isSorted) {
            isSorted = true;
            for (int i = 0; i < array.length - 1 - counter; i++) {
                if (array[i] > array[i + 1]) {
                    swap(i, i + 1, array);
                    isSorted = false;
                }
            }
            counter++;
        }
        return array;
    }

    public static void swap(int i, int j, int[] array) {
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
}

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) {
    for (let i = 1; i < array.length; i++) {
        let j = i;
        while (j > 0 && array[j] < array[j - 1]) {
            swap(j, j - 1, array);
            j -= 1;
        }
    }
    return array;
}

function swap(i, j, array) {
    const temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

Java code:

class Program {
    // Best: O(n) time | O(1) space
    // Average: O(n^2) time | O(1) space
    // Worst: O(n^2) time | O(1) space
    public static int[] insertionSort(int[] array) {
        if (array.length == 0) {
            return new int[]{};
        }
        for (int i = 1; i < array.length; i++) {
            int j = i;
            while (j > 0 && array[j] < array[j - 1]) {
                swap(j, j - 1, array);
                j -= 1;
            }
        }
        return array;
    }

    public static void swap(int i, int j, int[] array) {
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
}

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 {
    // Best: O(n^2) time | O(1) space
    // Average: O(n^2) time | O(1) space
    // Worst: O(n^2) time | O(1) space
    public static int[] selectionSort(int[] array) {
        if (array.length == 0) {
            return new int[]{};
        }
        int startIdx = 0;
        while (startIdx < array.length - 1) {
            int smallestIdx = startIdx;
            for (int i = startIdx + 1; i < array.length; i++) {
                if (array[smallestIdx] > array[i]) {
                    smallestIdx = i;
                }
            }
            swap(startIdx, smallestIdx, array);
            startIdx++;
        }
        return array;
    }

    public static void swap(int i, int j, int[] array) {
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
}

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) {
    let leftIdx = 0;
    let rightIdx = string.length - 1;
    while (leftIdx < rightIdx) {
        if (string[leftIdx] !== string[rightIdx]) return false;
        leftIdx++;
        rightIdx--;
    }
    return true;
}

Java:

class Program {
    // O(n) time | O(1) space 
    public static boolean isPalindrome(String str) {
        int leftIdx = 0;
        int rightIdx = str.length() - 1;
        while (leftIdx < rightIdx) {
            if (str.charAt(leftIdx) != str.charAt(rightIdx)) {
                return false;
            }
            leftIdx++;
            rightIdx--;
        }
        return true;
    }
}

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) {
    const newLetters = [];
    const newKey = key % 26;
    const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
    for (const letter of string) {
        newLetters.push(getNewLetter(letter, newKey, alphabet));
    }
    return newLetters.join('');
}

function getNewLetter(letter, key, alphabet) {
    const newLetterCode = alphabet.indexOf(letter) + key;
    return newLetterCode <= 25 ? alphabet[newLetterCode] : alphabet[-1 + newLetterCode % 25];
}

Java code:

class Program {
    // O(n) time | O(n) space
    public static String caesarCypherEncryptor(String str, int key) {
        char[] newLetters = new char[str.length()];
        int newKey = key % 26;
        String alphabet = "abcdefghijklmnopqrstuvwxyz";
        for (int i = 0; i < str.length(); i++) {
            newLetters[i] = getNewLetter(str.charAt(i), newKey, alphabet);
        }
        return new String(newLetters);
    }
    public static char getNewLetter(char letter, int key, String alphabet) {
        int newLetterCode = alphabet.indexOf(letter) + key;
        return newLetterCode <= 25 ? alphabet.charAt(newLetterCode) : alphabet.charAt(-1 + newLetterCode % 25);
    }
}

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<right)
if (curSum>target) , right–, else left++
if(curSum==target) add { arr[i], arr[left], arr[right] } to result List, then right– && left++

JavaScript Code:

// O(n^2) time | O(n) space
function threeNumberSum(array, targetSum) {
    array.sort((a, b) => a - b);
    const triplets = [];
    for (let i = 0; i < array.length - 2; i++) {
        let left = i + 1;
        let right = array.length - 1;
        while (left < right) {
            const currentSum = array[i] + array[left] + array[right];
            if (currentSum === targetSum) {
                triplets.push([array[i], array[left], array[right]]);
                left++;
                right--;
            } else if (currentSum < targetSum) {
                left++;
            } else if (currentSum > targetSum) {
                right--;
            }
        }
    }
    return triplets;
}

Java Code:

class Program {
    // O(n^2) time | O(n) space 
    public static List<Integer[]> threeNumberSum(int[] array, int targetSum) {
        Arrays.sort(array);
        List<Integer[]> triplets = new ArrayList<Integer[]>();
        for (int i = 0; i < array.length - 2; i++) {
            int left = i + 1;
            int right = array.length - 1;
            while (left < right) {
                int currentSum = array[i] + array[left] + array[right];
                if (currentSum == targetSum) {
                    Integer[] newTriplet = {array[i], array[left], array[right]};
                    triplets.add(newTriplet);
                    left++;
                    right--;
                } else if (currentSum < targetSum) {
                    left++;
                } else if (currentSum > targetSum) {
                    right--;
                }
            }
        }
        return triplets;
    }
}

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[] = {1, 3, 15, 11, 2} 
B[] = {23, 127, 235, 19, 8} 
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) {
    arrayOne.sort((a, b) => a - b);
    arrayTwo.sort((a, b) => a - b);
    let idxOne = 0;
    let idxTwo = 0;
    let smallest = Infinity;
    let current = Infinity;
    let smallestPair = [];
    while (idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
        let firstNum = arrayOne[idxOne];
        let secondNum = arrayTwo[idxTwo];
        if (firstNum < secondNum) {
            current = secondNum - firstNum;
            idxOne++;
        } else if (secondNum < firstNum) {
            current = firstNum - secondNum;
            idxTwo++;
        } else {
            return [firstNum, secondNum];
        }
        if (smallest > current) {
            smallest = current;
            smallestPair = [firstNum, secondNum];
        }
    }
    return smallestPair;
}

Java Code:

class Program {
    // O(nlog(n) + mlog(m)) time | O(1) space
    public static int[] smallestDifference(int[] arrayOne, int[] arrayTwo) {
        Arrays.sort(arrayOne);
        Arrays.sort(arrayTwo);
        int idxOne = 0;
        int idxTwo = 0;
        int smallest = Integer.MAX_VALUE;
        int current = Integer.MAX_VALUE;
        int[] smallestPair = new int[2];
        while (idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
            int firstNum = arrayOne[idxOne];
            int secondNum = arrayTwo[idxTwo];
            if (firstNum < secondNum) {
                current = secondNum - firstNum;
                idxOne++;
            } else if (secondNum < firstNum) {
                current = firstNum - secondNum;
                idxTwo++;
            } else {
                return new int[]{firstNum, secondNum};
            }
            if (smallest > current) {
                smallest = current;
                smallestPair = new int[]{firstNum, secondNum};
            }
        }
        return smallestPair;
    }
}

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) {
    let i = 0;
    let j = array.length - 1;
    while (i < j) {
        while (i < j && array[j] === toMove) j--;
        if (array[i] === toMove) swap(i, j, array);
        i++;
    }
    return array;
}

function swap(i, j, array) {
    const temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

Java Code:

class Program {
    // O(n) time | O(1) space - where n is the length of the array
    public static List<Integer> moveElementToEnd(List<Integer> array, int toMove) {
        int i = 0;
        int j = array.size() - 1;
        while (i < j) {
            while (i < j && array.get(j) == toMove) j--;
            if (array.get(i) == toMove) swap(i, j, array);
            i++;
        }
        return array;
    }

    public static void swap(int i, int j, List<Integer> array) {
        int temp = array.get(j);
        array.set(j, array.get(i));
        array.set(i, temp);
    }
}

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) {
    let isNonDecreasing = true;
    let isNonIncreasing = true;
    for (let i = 1; i < array.length; i++) {
        if (array[i] < array[i - 1]) isNonDecreasing = false;
        if (array[i] > array[i - 1]) isNonIncreasing = false;
    }
    return isNonDecreasing || isNonIncreasing;
}

Java Code:

class Program {
    // O(n) time | O(1) space - where n is the length of the array
    public static boolean isMonotonic(int[] array) {
        boolean isNonDecreasing = true;
        boolean isNonIncreasing = true;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                isNonDecreasing = false;
            }
            if (array[i] > array[i - 1]) {
                isNonIncreasing = false;
            }
        }
        return isNonDecreasing || isNonIncreasing;
    }
}

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) {
    const result = [];
    let startRow = 0,
        endRow = array.length - 1;
    let startCol = 0,
        endCol = array[0].length - 1;
    while (startRow <= endRow && startCol <= endCol) {
        for (let col = startCol; col <= endCol; col++) {
            result.push(array[startRow][col]);
        }
        for (let row = startRow + 1; row <= endRow; row++) {
            result.push(array[row][endCol]);
        }
        for (let col = endCol - 1; col >= startCol; col--) {
            if (startRow === endRow) break;
            result.push(array[endRow][col]);
        }
        for (let row = endRow - 1; row > startRow; row--) {
            if (startCol === endCol) break;
            result.push(array[row][startCol]);
        }
        startRow++;
        endRow--;
        startCol++;
        endCol--;
    }
    return result;
}

Java Code:

class Program {
    // O(n) time | O(n) space - where n is the total number of elements in the array 
    public static List<Integer> spiralTraverse(int[][] array) {
        if (array.length == 0) return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<Integer>();
        int startRow = 0;
        int endRow = array.length - 1;
        int startCol = 0;
        int endCol = array[0].length - 1;
        while (startRow <= endRow && startCol <= endCol) {
            for (int col = startCol; col <= endCol; col++) {
                result.add(array[startRow][col]);
            }
            for (int row = startRow + 1; row <= endRow; row++) {
                result.add(array[row][endCol]);
            }
            for (int col = endCol - 1; col >= startCol; col--) {
                if (startRow == endRow) break;
                result.add(array[endRow][col]);
            }
            for (int row = endRow - 1; row > startRow; row--) {
                if (startCol == endCol) break;
                result.add(array[row][startCol]);
            }
            startRow++;
            endRow--;
            startCol++;
            endCol--;
        }
        return result;
    }
}

Recursive method:

JavaScript Code:

// O(n) time | O(n) space - where n is the total number of elements in the array 
function spiralTraverse(array) {
    const result = [];
    let startRow = 0,
        endRow = array.length - 1;
    let startCol = 0,
        endCol = array[0].length - 1;
    while (startRow <= endRow && startCol <= endCol) {
        for (let col = startCol; col <= endCol; col++) {
            result.push(array[startRow][col]);
        }
        for (let row = startRow + 1; row <= endRow; row++) {
            result.push(array[row][endCol]);
        }
        for (let col = endCol - 1; col >= startCol; col--) {
            if (startRow === endRow) break;
            result.push(array[endRow][col]);
        }
        for (let row = endRow - 1; row > startRow; row--) {
            if (startCol === endCol) break;
            result.push(array[row][startCol]);
        }
        startRow++;
        endRow--;
        startCol++;
        endCol--;
    }
    return result;
}

Java Code:

class Program {
    // O(n) time | O(n) space - where n is the total number of elements in the array
    public static List<Integer> spiralTraverse(int[][] array) {
        if (array.length == 0) return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<Integer>();
        spiralFill(array, 0, array.length - 1, 0, array[0].length - 1, result);
        return result;
    }

    public static void spiralFill(int[][] array,
                                  int startRow, int endRow, int startCol,
                                  int endCol, ArrayList<Integer> result) {
        if (startRow > endRow || startCol > endCol) {
            return;
        }
        for (int col = startCol; col <= endCol; col++) {
            result.add(array[startRow][col]);
        }
        for (int row = startRow + 1; row <= endRow; row++) {
            result.add(array[row][endCol]);
        }
        for (int col = endCol - 1; col >= startCol; col--) {
            if (startRow == endRow) break;
            result.add(array[endRow][col]);
        }
        for (int row = endRow - 1; row >= startRow + 1; row--) {
            if (startCol == endCol) break;
            result.add(array[row][startCol]);
        }
        spiralFill(array, startRow + 1, endRow - 1, startCol + 1, endCol - 1, result);
    }
}

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) {
    let longestPeakLength = 0;
    let i = 1;
    while (i < array.length - 1) {
        const isPeak = array[i - 1] < array[i] && array[i + 1] < array[i];
        if (!isPeak) {
            i++;
            continue;
        }
        let leftIdx = i - 2;
        while (leftIdx >= 0 && array[leftIdx] < array[leftIdx + 1]) {
            leftIdx--;
        }
        let rightIdx = i + 2;
        while (rightIdx < array.length && array[rightIdx] < array[rightIdx - 1]) {
            rightIdx++;
        }
        const currentPeakLength = rightIdx - leftIdx - 1;
        longestPeakLength = Math.max(longestPeakLength, currentPeakLength);
        i = rightIdx;
    }
    return longestPeakLength;
}

Java Code:

class Program {
    // O(n) time | O(1) space - where n is the length of the input array 
    public static int longestPeak(int[] array) {
        int longestPeakLength = 0;
        int i = 1;
        while (i < array.length - 1) {
            boolean isPeak = array[i - 1] < array[i] && array[i] > array[i + 1];
            if (!isPeak) {
                i += 1;
                continue;
            }
            int leftIdx = i - 2;
            while (leftIdx >= 0 && array[leftIdx] < array[leftIdx + 1]) {
                leftIdx -= 1;
            }
            int rightIdx = i + 2;
            while (rightIdx < array.length && array[rightIdx] < array[rightIdx - 1]) {
                rightIdx += 1;
            }
            int currentPeakLength = rightIdx - leftIdx - 1;
            if (currentPeakLength > longestPeakLength) {
                longestPeakLength = currentPeakLength;
            }
            i = rightIdx;
        }
        return longestPeakLength;
    }
}

8. Validate BST

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

Leetcode Link

JavaScript Code:

class BST {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
// O(n) time | O(d) space 
function validateBst(tree) {
    return validateBstHelper(tree, -Infinity, Infinity);
}

function validateBstHelper(tree, minValue, maxValue) {
    if (tree === null) return true;
    if (tree.value < minValue || tree.value >= maxValue) return false;
    const leftIsValid = validateBstHelper(tree.left, minValue, tree.value);
    return leftIsValid && validateBstHelper(tree.right, tree.value, maxValue);
}
exports.BST = BST;
exports.validateBst = validateBst;

Java Code:

class Program {
    // O(n) time | O(d) space
    public static boolean validateBst(BST tree) {
        return validateBst(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public static boolean validateBst(BST tree, int minValue, int maxValue) {
        if (tree.value < minValue || tree.value >= maxValue) {
            return false;
        }
        if (tree.left != null && !validateBst(tree.left, minValue, tree.value)) {
            return false;
        }
        if (tree.right != null && !validateBst(tree.right, tree.value, maxValue)) {
            return false;
        }
        return true;
    }

    static class BST {
        public int value;
        public BST left;
        public BST right;

        public BST(int value) {
            this.value = value;
        }
    }
}

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) {
    if (tree !== null) {
        inOrderTraverse(tree.left, array);
        array.push(tree.value);
        inOrderTraverse(tree.right, array);
    }
    return array;
}
// O(n) time | O(n) space
function preOrderTraverse(tree, array) {
    if (tree !== null) {
        array.push(tree.value);
        preOrderTraverse(tree.left, array);
        preOrderTraverse(tree.right, array);
    }
    return array;
}
// O(n) time | O(n) space
function postOrderTraverse(tree, array) {
    if (tree !== null) {
        postOrderTraverse(tree.left, array);
        postOrderTraverse(tree.right, array);
        array.push(tree.value);
    }
    return array;
}
exports.inOrderTraverse = inOrderTraverse;
exports.preOrderTraverse = preOrderTraverse;
exports.postOrderTraverse = postOrderTraverse;

Java Code:

class Program {
    // O(n) time | O(n) space
    public static List<Integer> inOrderTraverse(BST tree, List<Integer> array) {
        if (tree.left != null) {
            inOrderTraverse(tree.left, array);
        }
        array.add(tree.value);
        if (tree.right != null) {
            inOrderTraverse(tree.right, array);
        }
        return array;
    }

    // O(n) time | O(n) space
    public static List<Integer> preOrderTraverse(BST tree, List<Integer> array) {
        array.add(tree.value);
        if (tree.left != null) {
            preOrderTraverse(tree.left, array);
        }
        if (tree.right != null) {
            preOrderTraverse(tree.right, array);
        }
        return array;
    }

    // O(n) time | O(n) space
    public static List<Integer> postOrderTraverse(BST tree, List<Integer> array) {
        if (tree.left != null) {
            postOrderTraverse(tree.left, array);
        }
        if (tree.right != null) {
            postOrderTraverse(tree.right, array);
        }
        array.add(tree.value);
        return array;
    }

    static class BST {
        public int value;
        public BST left;
        public BST right;

        public BST(int value) {
            this.value = value;
        }
    }
}

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) {
    return constructMinHeightBst(array, 0, array.length - 1);
}

function constructMinHeightBst(array, startIdx, endIdx) {
    if (endIdx < startIdx) return null;
    const midIdx = Math.floor((startIdx + endIdx) / 2);
    const bst = new BST(array[midIdx]);
    bst.left = constructMinHeightBst(array, startIdx, midIdx - 1);
    bst.right = constructMinHeightBst(array, midIdx + 1, endIdx);
    return bst;
}
class BST {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    // We don't use this method for this solution.   
    insert(value) {
        if (value < this.value) {
            if (this.left === null) {
                this.left = new BST(value);
            } else {
                this.left.insert(value);
            }
        } else {
            if (this.right === null) {
                this.right = new BST(value);
            } else {
                this.right.insert(value);
            }
        }
    }
}

Java Code:

class Program {
    
    // O(n) time | O(n) space - where n is the length of the array
    public static BST minHeightBst(List<Integer> array) {
        return constructMinHeightBst(array, 0, array.size() - 1);
    }

    public static BST constructMinHeightBst(List<Integer> array, int startIdx, int endIdx) {
        if (endIdx < startIdx) return null;
        int midIdx = (startIdx + endIdx) / 2;
        BST bst = new BST(array.get(midIdx));
        bst.left = constructMinHeightBst(array, startIdx, midIdx - 1);
        bst.right = constructMinHeightBst(array, midIdx + 1, endIdx);
        return bst;
    }

    static class BST {
        public int value;
        public BST left;
        public BST right;

        public BST(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
}

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) {
    const queue = [tree];
    while (queue.length) {
        const current = queue.shift();
        if (current === null) continue;
        swapLeftAndRight(current);
        queue.push(current.left);
        queue.push(current.right);
    }
}

function swapLeftAndRight(tree) {
    const left = tree.left;
    tree.left = tree.right;
    tree.right = left;
}

Recursion:
JavaScript:

// O(n) time | O(d) space
function invertBinaryTree(tree) {
    if (tree === null) return;
    swapLeftAndRight(tree);
    invertBinaryTree(tree.left);
    invertBinaryTree(tree.right);
}

function swapLeftAndRight(tree) {
    const left = tree.left;
    tree.left = tree.right;
    tree.right = left;
}

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) {
    if (!array.length) return 0;
    if (array.length === 1) return array[0];
    let second = array[0];
    let first = Math.max(array[0], array[1]);
    for (let i = 2; i < array.length; i++) {
        const current = Math.max(first, second + array[i]);
        second = first;
        first = current;
    }
    return first;
}

Java:

class Program {
    // O(n) time | O(1) space
    public static int maxSubsetSumNoAdjacent(int[] array) {
        if (array.length == 0) {
            return 0;
        } else if (array.length == 1) {
            return array[0];
        }
        int second = array[0];
        int first = Math.max(array[0], array[1]);
        for (int i = 2; i < array.length; i++) {
            int current = Math.max(first, second + array[i]);
            second = first;
            first = current;
        }
        return first;
    }
}

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) {
    const small = str1.length < str2.length ? str1 : str2;
    const big = str1.length >= str2.length ? str1 : str2;
    const evenEdits = [];
    const oddEdits = new Array(small.length + 1);
    for (let j = 0; j < small.length + 1; j++) {
        evenEdits.push(j);
    }
    for (let i = 1; i < big.length + 1; i++) {
        let currentEdits, previousEdits;
        if (i % 2 === 1) {
            currentEdits = oddEdits;
            previousEdits = evenEdits;
        } else {
            currentEdits = evenEdits;
            previousEdits = oddEdits;
        }
        currentEdits[0] = i;
        for (let j = 1; j < small.length + 1; j++) {
            if (big[i - 1] === small[j - 1]) {
                currentEdits[j] = previousEdits[j - 1];
            } else {
                currentEdits[j] = 1 + Math.min(previousEdits[j - 1], previousEdits[j], currentEdits[j - 1]);
            }
        }
    }
    return big.length % 2 === 0 ? evenEdits[small.length] : oddEdits[small.length];
}

Java Code :

class Program {
    // O(nm) time | O(nm) space
    public static int levenshteinDistance(String str1, String str2) {
        int[][] edits = new int[str2.length() + 1][str1.length() + 1];
        for (int i = 0; i < str2.length() + 1; i++) {
            for (int j = 0; j < str1.length() + 1; j++) {
                edits[i][j] = j;
            }
            edits[i][0] = i;
        }
        for (int i = 1; i < str2.length() + 1; i++) {
            for (int j = 1; j < str1.length() + 1; j++) {
                if (str2.charAt(i - 1) == str1.charAt(j - 1)) {
                    edits[i][j] = edits[i - 1][j - 1];
                } else {
                    edits[i][j] =
                            1 + Math.min(edits[i - 1][j - 1], Math.min(edits[i - 1][j], edits[i-1][j-1]));
                }
            }
        }
        return edits[str2.length()][str1.length()];
    }
}

Optimal:

class Program {
    // O(nm) time | O(min(n, m)) space
    public static int levenshteinDistance(String str1, String str2) {
        String small = str1.length() < str2.length() ? str1 : str2;
        String big = str1.length() >= str2.length() ? str1 : str2;
        int[] evenEdits = new int[small.length() + 1];
        int[] oddEdits = new int[small.length() + 1];
        for (int j = 0; j < small.length() + 1; j++) {
            evenEdits[j] = j;
        }
        int[] currentEdits;
        int[] previousEdits;
        for (int i = 1; i < big.length() + 1; i++) {
            if (i % 2 == 1) {
                currentEdits = oddEdits;
                previousEdits = evenEdits;
            } else {
                currentEdits = evenEdits;
                previousEdits = oddEdits;
            }
            currentEdits[0] = i;
            for (int j = 1; j < small.length() + 1; j++) {
                if (big.charAt(i - 1) == small.charAt(j - 1)) {
                    currentEdits[j] = previousEdits[j - 1];
                } else {
                    currentEdits[j] = 1 + Math.min(previousEdits[j - 1],
                            Math.min(previousEdits[j], currentEdits[j-1]));
                }
            }
        }
        return big.length() % 2 == 0 ? evenEdits[small.length()] : oddEdits[small.length()];
    }
}

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 <N, N is the length of the array, return false
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) {
    let numElementsVisited = 0;
    let currentIdx = 0;
    while (numElementsVisited < array.length) {
        if (numElementsVisited > 0 && currentIdx === 0) return false;
        numElementsVisited++;
        currentIdx = getNextIdx(currentIdx, array);
    }
    return currentIdx === 0;
}

function getNextIdx(currentIdx, array) {
    const jump = array[currentIdx];
    const nextIdx = (currentIdx + jump) % array.length;
    return nextIdx >= 0 ? nextIdx : nextIdx + array.length;
}

Java Code:

class Program {
    // O(n) time | O(1) space - where n is the length of the input array 
    public static boolean hasSingleCycle(int[] array) {
        int numElementsVisited = 0;
        int currentIdx = 0;
        while (numElementsVisited < array.length) {
            if (numElementsVisited > 0 && currentIdx == 0) return false;
            numElementsVisited++;
            currentIdx = getNextIdx(currentIdx, array);
        }
        return currentIdx == 0;
    }

    public static int getNextIdx(int currentIdx, int[] array) {
        int jump = array[currentIdx];
        int nextIdx = (currentIdx + jump) % array.length;
        return nextIdx >= 0 ? nextIdx : nextIdx + array.length;
    }
}

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) {
    let numElementsVisited = 0;
    let currentIdx = 0;
    while (numElementsVisited < array.length) {
        if (numElementsVisited > 0 && currentIdx === 0) return false;
        numElementsVisited++;
        currentIdx = getNextIdx(currentIdx, array);
    }
    return currentIdx === 0;
}

function getNextIdx(currentIdx, array) {
    const jump = array[currentIdx];
    const nextIdx = (currentIdx + jump) % array.length;
    return nextIdx >= 0 ? nextIdx : nextIdx + array.length;
}

Java Code :

class Program {
    static class Node {
        String name;
        List<Node> children = new ArrayList<Node>();

        public Node(String name) {
            this.name = name;
        }

        // O(v + e) time | O(v) space
        public List<String> breadthFirstSearch(List<String> array) {
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(this);
            while (!queue.isEmpty()) {
                Node current = queue.poll();
                array.add(current.name);
                queue.addAll(current.children);
            }
            return array;
        }

        public Node addChild(String name) {
            Node child = new Node(name);
            children.add(child);
            return this;
        }
    }
}

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) {
    const sizes = [];
    const visited = matrix.map(row => row.map(value => false));
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            if (visited[i][j]) continue;
            traverseNode(i, j, matrix, visited, sizes);
        }
    }
    return sizes;
}

function traverseNode(i, j, matrix, visited, sizes) {
    let currentRiverSize = 0;
    const nodesToExplore = [
        [i, j]
    ];
    while (nodesToExplore.length) {
        const currentNode = nodesToExplore.pop();
        i = currentNode[0];
        j = currentNode[1];
        if (visited[i][j]) continue;
        visited[i][j] = true;
        if (matrix[i][j] === 0) continue;
        currentRiverSize++;
        const unvisitedNeighbors = getUnvisitedNeighbors(i, j, matrix, visited);
        for (const neighbor of unvisitedNeighbors) {
            nodesToExplore.push(neighbor);
        }
    }
    if (currentRiverSize > 0) sizes.push(currentRiverSize);
}

function getUnvisitedNeighbors(i, j, matrix, visited) {
    const unvisitedNeighbors = [];
    if (i > 0 && !visited[i - 1][j]) unvisitedNeighbors.push([i - 1, j]);
    if (i < matrix.length - 1 && !visited[i + 1][j]) unvisitedNeighbors.push([i + 1, j]);
    if (j > 0 && !visited[i][j - 1]) unvisitedNeighbors.push([i, j - 1]);
    if (j < matrix[0].length - 1 && !visited[i][j + 1]) unvisitedNeighbors.push([i, j + 1]);
    return unvisitedNeighbors;
}

Java Code:

class Program {
    // O(wh) time | O(wh) space
    public static List<Integer> riverSizes(int[][] matrix) {
        List<Integer> sizes = new ArrayList<Integer>();
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (visited[i][j]) {
                    continue;
                }
                traverseNode(i, j, matrix, visited, sizes);
            }
        }
        return sizes;
    }

    public static void traverseNode(
            int i, int j, int[][] matrix, boolean[][] visited, List<Integer> sizes) {
        int currentRiverSize = 0;
        List<Integer[]> nodesToExplore = new ArrayList<Integer[]>();
        nodesToExplore.add(new Integer[]{i, j});
        while (!nodesToExplore.isEmpty()) {
            Integer[] currentNode = nodesToExplore.get(nodesToExplore.size() - 1);
            nodesToExplore.remove(nodesToExplore.size() - 1);
            i = currentNode[0];
            j = currentNode[1];
            if (visited[i][j]) {
                continue;
            }
            visited[i][j] = true;
            if (matrix[i][j] == 0) {
                continue;
            }
            currentRiverSize++;
            List<Integer[]> unvisitedNeighbors = 
                    getUnvisitedNeighbors(i, j, matrix, visited);
            for (Integer[] neighbor : unvisitedNeighbors) {
                nodesToExplore.add(neighbor);
            }
        }
        if (currentRiverSize > 0) {
            sizes.add(currentRiverSize);
        }
    }

    public static List<Integer[]> getUnvisitedNeighbors(int i, int j, int[][] matrix, boolean[][] visited) {
        List<Integer[]> unvisitedNeighbors = new ArrayList<Integer[]>();
        if (i > 0 && !visited[i - 1][j]) {
            unvisitedNeighbors.add(new Integer[]{i - 1, j});
        }
        if (i < matrix.length - 1 && !visited[i + 1][j]) {
            unvisitedNeighbors.add(new Integer[]{i + 1, j});
        }
        if (j > 0 && !visited[i][j - 1]) {
            unvisitedNeighbors.add(new Integer[]{i, j - 1});
        }
        if (j < matrix[0].length - 1 && !visited[i][j + 1]) {
            unvisitedNeighbors.add(new Integer[]{i, j + 1});
        }
        return unvisitedNeighbors;
    }
}

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 {
    constructor(name) {
        this.name = name;
        this.ancestor = null;
    }
}
// O(d) time | O(1) space - where d is the depth (height) of the ancestral tree 
function getYoungestCommonAncestor(topAncestor, descendantOne, descendantTwo) {
    const depthOne = getDescendantDepth(descendantOne, topAncestor);
    const depthTwo = getDescendantDepth(descendantTwo, topAncestor);
    if (depthOne > depthTwo) {
        return backtrackAncestralTree(descendantOne, descendantTwo, depthOne - depthTwo);
    } else {
        return backtrackAncestralTree(descendantTwo, descendantOne, depthTwo - depthOne);
    }
}

function getDescendantDepth(descendant, topAncestor) {
    let depth = 0;
    while (descendant !== topAncestor) {
        depth++;
        descendant = descendant.ancestor;
    }
    return depth;
}

function backtrackAncestralTree(lowerDescendant, higherDescendant, diff) {
    while (diff > 0) {
        lowerDescendant = lowerDescendant.ancestor;
        diff--;
    }
    while (lowerDescendant !== higherDescendant) {
        lowerDescendant = lowerDescendant.ancestor;
        higherDescendant = higherDescendant.ancestor;
    }
    return lowerDescendant;
}

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

Java Code:

class Program {
    // O(d) time | O(1) space - where d is the depth (height) of the ancestral tree
    public static AncestralTree getYoungestCommonAncestor(
            AncestralTree topAncestor,
            AncestralTree descendantOne,
            AncestralTree descendantTwo)
    {
        int depthOne = getDescendantDepth(descendantOne, topAncestor);
        int depthTwo = getDescendantDepth(descendantTwo, topAncestor);

        if (depthOne > depthTwo) {
            return backtrackAncestralTree(
                    descendantOne, descendantTwo, depthOne - depthTwo);
        } else {
            return backtrackAncestralTree(
                    descendantTwo, descendantOne, depthTwo - depthTwo);
        }
    }

    public static int getDescendantDepth(AncestralTree descendant,
                                         AncestralTree topAncestor) {
        int depth = 0;
        while (descendant != topAncestor) {
            depth++;
            descendant = descendant.ancestor;
        }
        return depth;
    }

    public static AncestralTree backtrackAncestralTree(
            AncestralTree lowerDescendant,
            AncestralTree higherDescendant,
            int diff)
    {
        //to same level
        while (diff > 0) {
            lowerDescendant = lowerDescendant.ancestor;
            diff--;
        }
        // go up to find same ancestor
        while (lowerDescendant != higherDescendant) {
            lowerDescendant = lowerDescendant.ancestor;
            higherDescendant = higherDescendant.ancestor;
        }
        return lowerDescendant;
    }

    //Ancestral Tree structure
    static class AncestralTree {
        public char name;
        public AncestralTree ancestor;

        AncestralTree(char name) {
            this.name = name;
            this.ancestor = null;
        }

        // This method is for testing only.
        void addAsAncestor(AncestralTree[] descendants) {
            for (AncestralTree descendant : descendants) {
                descendant.ancestor = this;
            }
        }
    }
}

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 {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
} 

// O(n) time | O(1) space
function removeKthNodeFromEnd(head, k) {
    let counter = 1;
    let first = head;
    let second = head;
    while (counter <= k) {
        second = second.next;
        counter++;
    }
    if (second === null) {
        head.value = head.next.value;
        head.next = head.next.next;
        return;
    }
    while (second.next !== null) {
        second = second.next;
        first = first.next;
    }
    first.next = first.next.next;
}
exports.LinkedList = LinkedList;
exports.removeKthNodeFromEnd = removeKthNodeFromEnd;

Java Code:

class Program {
    // O(n) time | O(1) space
    public static void removeKthNodeFromEnd(LinkedList head, int k) {
        int counter = 1;
        LinkedList first = head;
        LinkedList second = head;
        while (counter <= k) {
            second = second.next;
            counter++;
        }
        if (second == null) {
            head.value = head.next.value;
            head.next = head.next.next;
            return;
        }
        while (second.next != null) {
            second = second.next;
            first = first.next;
        }
        first.next = first.next.next;
    }

    static class LinkedList {
        int value;
        LinkedList next = null;

        public LinkedList(int value) {
            this.value = value;
        }
    }
}

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) {
    const permutations = [];
    permutationsHelper(array, [], permutations);
    return permutations;
}

function permutationsHelper(array, currentPermutation, permutations) {
    if (!array.length && currentPermutation.length) {
        permutations.push(currentPermutation);
    } else {
        for (let i = 0; i < array.length; i++) {
            const newArray = array.slice(0, i).concat(array.slice(i + 1));
            const newPermutation = currentPermutation.concat([array[i]]);
            permutationsHelper(newArray, newPermutation, permutations);
        }
    }
}
exports.getPermutations = getPermutations;

Java:

class Program {
    // O(n*n!) time | O(n*n!) space
    public static List<List<Integer>> getPermutations(List<Integer> array) {
        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
        getPermutations(0, array, permutations);
        return permutations;
    }

    public static void getPermutations(
            int i,
            List<Integer> array,
            List<List<Integer>> permutations) {

        if (i == array.size() - 1) {
            permutations.add(new ArrayList<Integer>(array));
        } else {
            for (int j = i; j < array.size(); j++) {
                swap(array, i, j);
                //go next position
                getPermutations(i + 1, array, permutations);
                //undo swap
                swap(array, i, j);
            }
        }

    }

    public static void swap(List<Integer> array, int i, int j) {
        Integer tmp = array.get(i);
        array.set(i, array.get(j));
        array.set(j, tmp);
    }
}

Recursion Code:
JavaScript:

// O(n*n!) time | O(n*n!) space
function getPermutations(array) {
    const permutations = [];
    permutationsHelper(0, array, permutations);
    return permutations;
}

function permutationsHelper(i, array, permutations) {
    if (i === array.length - 1) {
        permutations.push(array.slice());
    } else {
        for (let j = i; j < array.length; j++) {
            swap(i, j, array);
            permutationsHelper(i + 1, array, permutations);
            swap(i, j, array);
        }
    }
}

function swap(i, j, array) {
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
exports.getPermutations = getPermutations;

Java:

class Program {
    // Upper Bound: O(n^2*n!) time | O(n*n!) space
    // Roughly: O(n*n!) time | O(n*n!) space
    public static List<List<Integer>> getPermutations(List<Integer> array) {
        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
        getPermutations(array, new ArrayList<Integer>(), permutations);
        return permutations;
    }

    public static void getPermutations(
            List<Integer> array,
            List<Integer> currentPermutation,
            List<List<Integer>> permutations) {

        if (array.size() == 0 && currentPermutation.size() > 0) {
            permutations.add(currentPermutation);
        } else {
            for (int i = 0; i < array.size(); i++) {
                List<Integer> newArray = new ArrayList<Integer>(array);
                newArray.remove(i);
                List<Integer> newPermutation = new ArrayList<Integer>(currentPermutation);
                newPermutation.add(array.get(i));
                getPermutations(newArray, newPermutation, permutations);
            }
        }
    }
}

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, {[],[1]}
add 2, {[],[1], [2], [1,2]}
add 3, {[],[1], [2], [1,2], [3],[1,3], [2,3], [1,2,3]}

JavaScript:

// O(n*2^n) time | O(n*2^n) space
function powerset(array) {
    const subsets = [[]];
    for (const ele of array) {
        const length = subsets.length;
        for (let i = 0; i < length; i++) {
            const currentSubset = subsets[i];
            subsets.push(currentSubset.concat(ele));
        }
    }
    return subsets;
}
exports.powerset = powerset;

Java Code:

class Program {
    // O(n*2^n) time | O(n*2^n) space
    public static List<List<Integer>> powerset(List<Integer> array) {
        List<List<Integer>> subsets = new ArrayList<List<Integer>>();
        subsets.add(new ArrayList<Integer>());
        for (Integer ele : array) {
            int length = subsets.size();
            for (int i = 0; i < length; i++) {
                List<Integer> currentSubset = new ArrayList<Integer>(subsets.get(i));
                currentSubset.add(ele);
                subsets.add(currentSubset);
            }
        }
        return subsets;
    }
}

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] <targer) row++;
else return Martix[row][col]

JavaScript:

// O(n + m) time | O(1) space
function searchInSortedMatrix(matrix, target) {
    let row = 0;
    let col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] > target) {
            col--;
        } else if (matrix[row][col] < target) {
            row++;
        } else {
            return [row, col];
        }
    }
    return [-1, -1];
}
exports.searchInSortedMatrix = searchInSortedMatrix;

Java:

class Program {
    // O(n) time | O(1) space
    public static int[] searchInSortedMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {

            // go left, down or return
            if (matrix[row][col] > target) {
                col--;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                return new int[]{row, col};
            }
        }
        return new int[]{-1, -1};
    }

}

26. Min Max Stack Construction

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

Solution:

Use List<Map<String, Integer>> minMaxStack to store history min and max value.
Use List stack to store Stack Values

JavaScript:

class MinMaxStack {
    constructor() {
        this.minMaxStack = [];
        this.stack = [];
    }
    // O(1) time | O(1) space   
    peek() {
        return this.stack[this.stack.length - 1];
    }
    // O(1) time | O(1) space
    pop() {
        this.minMaxStack.pop();
        return this.stack.pop();
    }
    // O(1) time | O(1) space   
    push(number) {
        const newMinMax = {
            min: number,
            max: number
        };
        if (this.minMaxStack.length) {
            const lastMinMax = this.minMaxStack[this.minMaxStack.length - 1];
            newMinMax.min = Math.min(lastMinMax.min, number);
            newMinMax.max = Math.max(lastMinMax.max, number);
        }
        this.minMaxStack.push(newMinMax);
        this.stack.push(number);
    }
    // O(1) time | O(1) space   
    getMin() {
        return this.minMaxStack[this.minMaxStack.length - 1].min;
    }
    // O(1) time | O(1) space
    getMax() {
        return this.minMaxStack[this.minMaxStack.length - 1].max;
    }
}

Java Code:

class MinMaxStack {
    List<Map<String, Integer>> minMaxStack = new ArrayList<Map<String, Integer>>();
    List<Integer> stack = new ArrayList<Integer>();

    // O(1) time | O(1) space
    public int peek() {
        return stack.get(stack.size() - 1);
    }

    // O(1) time | O(1) space
    public int pop() {
        minMaxStack.remove(minMaxStack.size() - 1);
        return stack.remove(stack.size() - 1);
    }

    // O(1) time | O(1) space
    public void push(int number) {
        Map<String, Integer> newMinMax = new HashMap<String, Integer>();
        newMinMax.put("min", number);
        newMinMax.put("max", number);
        if (minMaxStack.size() > 0) {
            Map<String, Integer> lastMinMax =
                    new HashMap<String, Integer>(minMaxStack.get(minMaxStack.size() - 1));
            newMinMax.replace("min", Math.min(lastMinMax.get("min"), number));
            newMinMax.replace("max", Math.max(lastMinMax.get("max"), number));
        }
        minMaxStack.add(newMinMax);
        stack.add(number);
    }

    // O(1) time | O(1) space
    public int getMin() {
        return minMaxStack.get(minMaxStack.size() - 1).get("min");
    }

    // O(1) time | O(1) space
    public int getMax() {
        return minMaxStack.get(minMaxStack.size() - 1).get("max");
    }
}

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:

// O(n^2) time | O(1) space
function longestPalindromicSubstring(string) {
    let currentLongest = [0, 1];
    for (let i = 1; i < string.length; i++) {
        const odd = getLongestPalindromeFrom(string, i - 1, i + 1);
        const even = getLongestPalindromeFrom(string, i - 1, i);
        const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even;
        currentLongest = currentLongest[1] - currentLongest[0] > longest[1] - longest[0] ? currentLongest : longest;
    }
    return string.slice(currentLongest[0], currentLongest[1]);
}

function getLongestPalindromeFrom(string, leftIdx, rightIdx) {
    while (leftIdx >= 0 && rightIdx < string.length) {
        if (string[leftIdx] !== string[rightIdx]) break;
        leftIdx--;
        rightIdx++;
    }
    return [leftIdx + 1, rightIdx];
}
exports.longestPalindromicSubstring = longestPalindromicSubstring;

JavaScript:

// O(w * n * log(n)) time | O(wn) space - where w is the number of words and n is 
function groupAnagrams(words) {
    const anagrams = {};
    for (const word of words) {
        const sortedWord = word.split('').sort().join('');
        if (sortedWord in anagrams) {
            anagrams[sortedWord].push(word);
        } else {
            anagrams[sortedWord] = [word];
        }
    }
    return Object.values(anagrams);
}
exports.groupAnagrams = groupAnagrams;

Java Code:

class Program {
    // O(n^2) time | O(1) space
    public static String longestPalindromicSubstring(String str) {
        int[] currentLongest = {0, 1};
        for (int i = 1; i < str.length(); i++) {
            int[] odd = getLongestPalindromeFrom(str, i - 1, i + 1);
            int[] even = getLongestPalindromeFrom(str, i - 1, i);
            int[] longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even;
            currentLongest =
                    currentLongest[1] - currentLongest[0] >
                            longest[1] - longest[0] ? currentLongest : longest;
        }
        return str.substring(currentLongest[0], currentLongest[1]);
    }

    public static int[] getLongestPalindromeFrom(String str, int leftIdx, int rightIdx) {
        while (leftIdx >= 0 && rightIdx < str.length()) {
            if (str.charAt(leftIdx) != str.charAt(rightIdx)) {
                break;
            }
            leftIdx--;
            rightIdx++;
        }
        return new int[]{leftIdx + 1, rightIdx};
    }
}

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:

class Program {
    // O(w * n * log(n)) time | O(wn) space - where w is the number of words and n 
    // the longest word
    public static List<List<String>> groupAnagrams(List<String> words) {
        // <String,List of Index>
        Map<String, List<String>> anagrams = new HashMap<String, List<String>>();
        //Sort each string then compare to decide add the string or append index in Map.
        for (String word : words) {
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sortedWord = new String(charArray);
            if (anagrams.containsKey(sortedWord)) {
                anagrams.get(sortedWord).add(word);
            } else {
                anagrams.put(sortedWord, new ArrayList<String>(Arrays.asList(word)));
            }
        }
        List<List<String>> output = new ArrayList<List<String>>();
        //push into result list
        for (Map.Entry<String, List<String>> entry : anagrams.entrySet()) {
            output.add(entry.getValue());
        }
        return output;
    }
}

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:

class SuffixTrie {
    constructor(string) {
        this.root = {};
        this.endSymbol = '*';
        this.populateSuffixTrieFrom(string);
    }
    // O(n^2) time | O(n^2) space   
    populateSuffixTrieFrom(string) {
        for (let i = 0; i < string.length; i++) {
            this.insertSubstringStartingAt(i, string);
        }
    }
    insertSubstringStartingAt(i, string) {
        let node = this.root;
        for (let j = i; j < string.length; j++) {
            const letter = string[j];
            if (!(letter in node)) node[letter] = {};
            node = node[letter];
        }
        node[this.endSymbol] = true;
    }
    // O(m) time | O(1) space   
    contains(string) {
        let node = this.root;
        for (const letter of string) {
            if (!(letter in node)) return false;
            node = node[letter];
        }
        return this.endSymbol in node;
    }
}

Java Code:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();

    static class SuffixTrie {
        TrieNode root = new TrieNode();
        char endSymbol = '*';

        public SuffixTrie(String str) {
            populateSuffixTrieFrom(str);
        }


        // Creation: O(n^2) time | O(n^2) space
        public void populateSuffixTrieFrom(String str) {
            //traverse str to construct suffix Trie
            for (int i = 0; i < str.length(); i++) {
                insertSubstringStartingAt(i, str);
            }
        }

        public void insertSubstringStartingAt(int i, String str) {
            TrieNode node = root;
            //construct from index i
            for (int j = i; j < str.length(); j++) {
                char letter = str.charAt(j);
                if (!node.children.containsKey(letter)) {
                    TrieNode newNode = new TrieNode();
                    node.children.put(letter, newNode);
                }
                node = node.children.get(letter);
            }
            node.children.put(endSymbol, null);
        }

        // Search: O(m) time | O(1) space
        public boolean contains(String str) {
            TrieNode node = root;
            for (int i = 0; i < str.length(); i++) {
                char letter = str.charAt(i);
                if (!node.children.containsKey(letter)) {
                    return false;
                }
                node = node.children.get(letter);
            }
            return node.children.containsKey(endSymbol);
        }
    }
}

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:

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!

About the Author: Huanyu

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

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

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`