Data Structures
Overview
Number
String
Array
Stack
Hash
Tree
Trie
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)