merge two sorted array - two array into one new array:

    public int[] mergeSortedArray(int[] A, int[] B) {
        if (A == null || B == null) return null;

        int[] rst = new int[A.length + B.length];
        int i = 0;
        int j = 0;
        int index = 0;

        while (i < A.length && j < B.length) {
            if (A[i] < B[j]) {
                rst[index++] = A[i++];
            } else {
                rst[index++] = B[j++];
            }
        }

        while (j < B.length) {
            rst[index++] = B[j++];
        }

        while (i < A.length) {
            rst[index++] = A[i++];
        }

        return rst;
    }

merge sorted arrays - merge B into A

• from end to start

    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;

        while (i >= 0 && j >=0) {
            if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }

        while (j >= 0) {
            A[index--] = B[j--];
        }
    }

merge two sorted linked list:

• merge two sorted list into a new sorted list
• dummy, while (curr != null && curr !=null) {}

merge k sorted linked list

• approach 1: heap
• approach 2: divide & conquer
• approach 3: merge list 2 by 2

merge k sorted array

• heap; optimized heap; min heap

intersection of two arrays

• approach 1: hashmap, hashset
• approach 2: binary search: sort array1, then search in array2
• approach 3: sort array1 and array2, then merge

median of sorted array

• approach 1: merge A & B, get median o(m+n)
• approach 2: findKth o(log n)