Array

Last 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;
}

Binary Search

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

Solution 1: Naive Search

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)