Data Structures
    Overview
    Number
    String
    Array
    Linked List
    Stack
    Hash
    Tree
    Trie
    Advanced Data Structure
    Probabilistic Data Structures
    Big O

Array

Updated: 2022-02-12

MaxDiff

Given an array, find the max diff between one integer and the integers to its right. e.g. [1, 5, 3, 65, 7, 43], the max is 65 - 7 = 58.

int maxdiff(int *a, int len)
{
    int m = a[0];
    int mdiff = 0x80000000;
    int i;
    for (i = 1; i < len; i++) {
        if (m - a[i] > mdiff) {
            mdiff = m - a[i];
        }
        if (a[i] > m) {
            m = a[i];
        }
    }
    return mdiff;
}
public class BinarySearch {

    public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid])
                hi = mid - 1;
            else if (key > a[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6};
        System.out.println(rank(5,a));
    }

}

Shuffle

public static void shuffle(int[] a) {
    for (int i = 0; i < a.length; i++){
        int k = (int) (Math.random() * (a.length - i)) + i;
        int tmp = a[k];
        a[k] = a[i];
        a[i] = tmp;
    }
}

Find Peak In 2D Array

Find any peak in a 2D integer array.

1 3 6 4 2 4
5 9 3 5 1 3
2 6 3 7 9 3
3 4 7 2 7 2

Search every position until a peak is found. O(n^2).

Solution 2: Binary Search Rows

Take the middle 3 rows, find the maximum of each row (3 * O(n)), drop the lower side half. Since the maximum of one row is larger than the other, it is guaranteed to be larger than any number in the other row. O(n log n).

Solution 3: Binary Search Alternating Rows and Columns

Similar to solution 2, but alternating between rows and columns, so first half of the rows are dropped, then half of the columns, then half of the rows.

O(N) + O(N/2) + O(N/4) + ... = O(N)