Sorting

Insertion Sort

Selection Sort

Merge Sort

Quick Sort

Bubble Sort

Longest Increasing Subsequence

Leetcode 300
Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

O(n^2):
Naive solution is use array T[] to track the LIS for each element in the original array. We have to track all the elements because the LIS can only increase for previous element which are smaller than current element.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // naive solution, keep another array to store the LIS so far. O(n^2)
        if (nums==null || nums.length == 0) return 0;
        int[] lens = new int[nums.length];
        int maxsofar = 1;
        for (int i = 0; i < nums.length; i++) {
            lens[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if ((lens[j]+1) > lens[i]) {
                        lens[i] = lens[j] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (lens[i] > maxsofar) maxsofar = lens[i];
        }
        return maxsofar;
    }
}

Dynamic Programming

Dynamic programming is a technique for solving problems with the following properties:

1. An instance is solved using the solutions for smaller instances.
2. The solution for a smaller instance might be needed multiple times.
3. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
4. Additional space is used to save time.

经典题目：

1. 买卖股票I II III IV

Leetcode 238 - Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
O(n), 所以只能扫一遍就得到该有的信息，自然想到的是左边扫一遍右边扫一遍。
省空间的话简单，右边扫的时候直接把答案存起来。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        //keep track of product of left elements in the array
        // then scan from right to left to multiply the right elements
        int n = nums.length;
        int[] results = new int[n];
        results[0] = 1;
        for (int i = 1; i < n; i++) {
            results[i] = results[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = n-1; i >= 0; i--) {
            results[i] *= right;
            right *= nums[i];
        }
        return results;
    }
}

Leetcode 73 - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Naive Approach:
For word1, use insert/delete/replace to generate all strings as its children, then for each children, generate all strings etc...
But the tree will expand too fast.
Solutions:
1. DP
2. Pruning (delete the nodes that are not actual English words).

Merge sort - Java

Basic algorithm:
1. If list has one element, return;
2. Divide list in half
3. Sort first half
    Sort second half    (use recursion)
4. Merge sorted lists.

Best = Worst = O(nlogn)

Quick sort best = average = O(nlogn), worst = O(n^2)

Insertion sorting - Java

Insertion sorting:

 public static void insertionSort( int[] vals ) {
  int currInd;
  for (int pos=1; pos < vals.length; pos++) {
   currInd = pos;
   while (currInd > 0 && vals[currInd] < vals[currInd-1] ) {
    swap(vals, currInd, currInd-1);
    currInd--;
   }
  }
 }

Best: O(n)
Worst: O(n^2)

Java Built-in Sorting

Mergesort

import java.util.*;

public class MyBuiltInSortingTest {
    public static void main (String[] args) {
        Random random = new Random();
        List numsToSort = new ArrayList();
        
        for (int i=0; i < 5; i++) {
            numsToSort.add( random.nextInt(100) );
        }
        
        Collection.sort(numsToSort);
        System.out.println("New array after builtin sort: " + numsToSort.toString());
    }
}

Seletion Sort - Java

Steps:
Find smallest element, swap it with element at location 0;
Find next smallest element, swap it with element at location 1;
etc.

public static void selectionSort( int[] vals ) {
    int indexmin;

    for (int i = 0; i < vals.length-1; i++) {
        indexmin = i;
        for (int j = i+1; j < vals.length-2; j++) {
            if (vals[j] < vals[indexmin]) { indexmin = j; }
        }
        swap( vals, indexmin, j );
    }
}

Correctness:
Left array is always sorted.

Performance:
Time: O(n^2)
Space: O(1)

Note:
Not sensitive to already almost sorted array (takes same amount of time)
So Best = Worst = O(n^2)

常见数据结构操作和算法复杂度

Source: http://bigocheatsheet.com/

Legend

Excellent

Good

Fair

Bad

Horrible

Data Structure Operations

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Singly-Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Doubly-Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Skip List	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)	O(n log(n))
Hash Table	-	O(1)	O(1)	O(1)	-	O(n)	O(n)	O(n)	O(n)
Binary Search Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)	O(n)
Cartesian Tree	-	O(log(n))	O(log(n))	O(log(n))	-	O(n)	O(n)	O(n)	O(n)
B-Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Red-Black Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Splay Tree	-	O(log(n))	O(log(n))	O(log(n))	-	O(log(n))	O(log(n))	O(log(n))	O(n)
AVL Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	O(n log(n))	O(n log(n))	O(n^2)	O(log(n))
Mergesort	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Timsort	O(n)	O(n log(n))	O(n log(n))	O(n)
Heapsort	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Bubble Sort	O(n)	O(n^2)	O(n^2)	O(1)
Insertion Sort	O(n)	O(n^2)	O(n^2)	O(1)
Selection Sort	O(n^2)	O(n^2)	O(n^2)	O(1)
Shell Sort	O(n)	O((nlog(n))^2)	O((nlog(n))^2)	O(1)
Bucket Sort	O(n+k)	O(n+k)	O(n^2)	O(n)
Radix Sort	O(nk)	O(nk)	O(nk)	O(n+k)

Graph Operations

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	O(|V|+|E|)	O(1)	O(1)	O(|V| + |E|)	O(|E|)	O(|V|)
Incidence list	O(|V|+|E|)	O(1)	O(1)	O(|E|)	O(|E|)	O(|E|)
Adjacency matrix	O(|V|^2)	O(|V|^2)	O(1)	O(|V|^2)	O(1)	O(1)
Incidence matrix	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|E|)

Heap Operations

Type	Time Complexity
	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	-	O(1)	O(1)	O(n)	O(n)	O(1)	O(m+n)
Linked List (unsorted)	-	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
Binary Heap	O(n)	O(1)	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(m+n)
Binomial Heap	-	O(1)	O(log(n))	O(log(n))	O(1)	O(log(n))	O(log(n))
Fibonacci Heap	-	O(1)	O(log(n))	O(1)	O(1)	O(log(n))	O(1)

Big-O Complexity Chart