Sort
Quicksort
Quicksort: not stable
Lomuto Partition Scheme
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int low, int high) {
if (low < high) {
int p = partition(nums, low, high);
quickSort(nums, low, p - 1);
quickSort(nums, p + 1, high);
}
}
private int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] < pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, high);
return i;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Hoare Partition Scheme
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int partition(int[] nums, int low, int high) {
int pivot = nums[(low + high) >>> 1];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (nums[i] < pivot) ;
do {
j--;
} while (nums[j] > pivot);
if (i >= j) {
return j;
}
swap(nums, i, j);
}
}
Merge Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Top-down
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] nums, int low, int high) {
if (low < high) {
int mid = (low + high) >>> 1;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums, low, high);
}
}
// nums[low...mid] and nums[mid + 1...high] are sorted
private void merge(int[] nums, int low, int high) {
int[] tmp = new int[high - low + 1];
int mid = (low + high) >>> 1;
int i = low, j = mid + 1;
for (int k = 0; k < tmp.length; k++) {
if (i <= mid && (j > high || nums[i] <= nums[j])) {
tmp[k] = nums[i++];
} else {
tmp[k] = nums[j++];
}
}
System.arraycopy(tmp, 0, nums, low, tmp.length);
}
Another implementation of the merge() function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void merge(int[] nums, int low, int high) {
int[] tmp = new int[high - low + 1];
int mid = (low + high) >>> 1;
int i = low, j = mid + 1, k = 0;
while (i <= mid) {
while (j <= high && nums[i] >= nums[j]) {
tmp[k++] = nums[j++];
}
tmp[k++] = nums[i++];
}
while (j <= high) {
tmp[k++] = nums[j++];
}
System.arraycopy(tmp, 0, nums, low, tmp.length);
}
Count of Smaller Numbers After Self
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort.
counts[i] = count of nums[j] - nums[i] < 0 with j > i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
private int[] counts;
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
this.counts = new int[n];
// nums[indices[i]] is the element at position i in the virtual sorted array
// so that the order of nums remains the same
int[] indices = new int[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
// sorts indices by the corresponding elements in nums: nums[indices[i]]
mergeSort(nums, indices, 0, n - 1);
return Arrays.stream(counts).boxed().collect(Collectors.toList());
}
private void mergeSort(int[] nums, int[] indices, int low, int high) {
if (low < high) {
int mid = (low + high) >>> 1;
mergeSort(nums, indices, low, mid);
mergeSort(nums, indices, mid + 1, high);
merge(nums, indices, low, high);
}
}
private void merge(int[] nums, int[] indices, int low, int high) {
int mid = (low + high) >>> 1;
int i = low, j = mid + 1;
int[] tmp = new int[high - low + 1];
// running sum of count of smaller numbers after each number (i.e. nums[indices[i]])
int count = 0;
for (int k = 0; k < tmp.length; k++) {
// for a indices[i], the right partition nums[mid + 1...high] is sorted
// so the merge function handles all smaller numbers in the right array first (else-block)
// then handles the other numbers (>= nums[indices[i]]) in the partition (if-block)
if (i <= mid && (j > high || nums[indices[i]] <= nums[indices[j]])) {
// all smaller numbers in the right partition have been handled in the else-block
// so the running `count` already includes the count of smaller numbers than nums[indices[i]]
//
// the running `count` also includes the counts of smaller numbers than previous nums[indices[h]]
// where h < i
// since the left partition is also sorted, nums[indices[h]] < nums[indices[i]]
// we can conclude if a number is smaller than nums[indices[h]], it's also smaller than nums[indices[i]]
// therefore, the numbers represented by the running `count` are all smaller than nums[indices[i]]
//
// adds the running count to the global array at the position for indices[i]
// the final result at each position is the sum of running counts of all sub merge functions
counts[indices[i]] += count;
tmp[k] = indices[i++];
} else {
// nums[indices[i]] > nums[indices[j]]
if (i <= mid) {
count++;
}
tmp[k] = indices[j++];
}
}
System.arraycopy(tmp, 0, indices, low, tmp.length);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
nums: [5,2,6,1]
low: 0, high: 1
indices: [0,1,2,3] -> [1,0,2,3]
counts: [0,0,0,0] -> [1,0,0,0]
low: 2, high: 3
indices: [1,0,2,3] -> [1,0,3,2]
counts: [1,0,0,0] -> [1,0,1,0]
low: 0, high: 3
indices: [1,0,3,2] -> [3,1,0,2]
counts: [1,0,1,0] -> [2,1,1,0]
We can also leverage Fenwick Tree to solve the problem. See Fenwick Tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int low, int high) {
int count = 0;
if (low < high) {
int mid = (low + high) >>> 1;
count += mergeSort(nums, low, mid);
count += mergeSort(nums, mid + 1, high);
count += merge(nums, low, high);
}
return count;
}
private int merge(int[] nums, int low, int high) {
int[] tmp = new int[high - low + 1];
int mid = (low + high) >>> 1;
int i = low, j = mid + 1, k = 0, p = mid + 1;
int count = 0;
while (i <= mid) {
// finds all nums in the right half that can form a reverse pair with nums[i]
while (p <= high && nums[i] > 2l * nums[p]) {
p++;
}
count += p - (mid + 1);
while (j <= high && nums[i] >= nums[j]) {
tmp[k++] = nums[j++];
}
tmp[k++] = nums[i++];
}
while (j <= high) {
tmp[k++] = nums[j++];
}
System.arraycopy(tmp, 0, nums, low, tmp.length);
return count;
}
count = count of lower <= p[j] - p[i] <= higher with j > i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
private int lower, upper;
// 315. Count of Smaller Numbers After Self
public int countRangeSum(int[] nums, int lower, int upper) {
this.lower = lower;
this.upper = upper;
int n = nums.length;
long[] p = new long[n + 1];
for (int i = 0; i < n; i++) {
p[i + 1] = p[i] + nums[i];
}
return mergeSort(p, 0, n);
}
private int mergeSort(long[] p, int low, int high) {
int count = 0;
if (low < high) {
int mid = (low + high) >>> 1;
count += mergeSort(p, low, mid);
count += mergeSort(p, mid + 1, high);
count += merge(p, low, high);
}
return count;
}
private int merge(long[] p, int low, int high) {
int mid = (low + high) >>> 1;
long[] tmp = new long[high - low + 1];
int count = 0;
// finds the j, k index in the right array
int j = mid + 1, k = mid + 1;
// index is for the tmp array
int index = 0, rightIndex = mid + 1;
for (int i = low; i <= mid; i++) {
// k is the first index satisfies sums[k] - sums[i] >= lower
while (k <= high && p[k] - p[i] < lower) {
k++;
}
// j is the first index satisfies sums[j] - sums[i] > upper
while (j <= high && p[j] - p[i] <= upper) {
j++;
}
// merge
while (rightIndex <= high && p[rightIndex] < p[i]) {
tmp[index++] = p[rightIndex++];
}
tmp[index++] = p[i];
// then the number of p in [lower, upper] is j - k
count += j - k;
}
// tmp was assigned up to rightIndex
// the remaining right array of p was not modified
// so we only need to copy (rightIndex - low) length
System.arraycopy(tmp, 0, p, low, rightIndex - low);
return count;
}
Create Target Array in the Given Order
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Similar to 315. Count of Smaller Numbers After Self
public int[] createTargetArray(int[] nums, int[] index) {
// counts no greater elements after self,
// and updates the original index array on the fly
// index[pos[i]] is the index element at position i in the array
int[] pos = new int[index.length];
for (int i = 0; i < pos.length; i++) {
pos[i] = i;
}
// sorts pos by the corresponding elements in index: index[pos[i]]
mergeSort(index, pos, 0, nums.length - 1);
int[] target = new int[nums.length];
for (int i = 0; i < target.length; i++) {
target[index[i]] = nums[i];
}
return target;
}
private void mergeSort(int[] index, int[] pos, int low, int high) {
if (low < high) {
int mid = (low + high) >>> 1;
mergeSort(index, pos, low, mid);
mergeSort(index, pos, mid + 1, high);
merge(index, pos, low, high);
}
}
private void merge(int[] index, int[] pos, int low, int high) {
int mid = (low + high) >>> 1;
int i = low, j = mid + 1;
int[] tmp = new int[high - low + 1];
// counts right elements index[pos[j]] that are no greater than the current left element index[pos[i]]
int count = 0;
for (int k = 0; k < tmp.length; k++) {
// compares updated index[pos[i]] with index[pos[j]]
if (i <= mid && (j > high || index[pos[i]] + count < index[pos[j]])) {
// increments index[post[i]] by the count of no greater elements on the right
// the order of sorting is maintained despite the increment
index[pos[i]] += count;
tmp[k] = pos[i++];
} else {
// index[pos[i]] + count >= index[pos[j]]
if (i <= mid) {
count++;
}
tmp[k] = pos[j++];
}
}
System.arraycopy(tmp, 0, pos, low, tmp.length);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
index: [0,0,1,3,1]
low: 0, high: 1
pos: [0,1,2,3,4] -> [1,0,2,3,4]
index: [0,0,1,3,1] -> [1,0,1,3,1]
low: 0, high: 2
pos: [1,0,2,3,4] -> [1,2,0,3,4]
index: [1,0,1,3,1] -> [2,0,1,3,1]
low: 3, high: 4
pos: [1,2,0,3,4] -> [1,2,0,4,3]
index: [2,0,1,3,1] -> [2,0,1,4,1]
low: 0, high: 4
pos: [1,2,0,4,3] -> [3,0,2,4,1]
index: [2,0,1,4,1] -> [3,0,2,4,1]
Bubble Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String orderlyQueue(String s, int k) {
// bubble sort - swaps adjacent pairs
if (k > 1) {
char chars[] = s.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
String min = s;
for (int i = 1; i < s.length(); i++) {
String tmp = s.substring(i) + s.substring(0, i);
if (tmp.compareTo(min) < 0) {
min = tmp;
}
}
return min;
}
Bucket Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int hIndex(int[] citations) {
int[] count = new int[citations.length + 1];
for (int c : citations) {
if (c >= citations.length) {
count[citations.length]++;
} else {
count[c]++;
}
}
int sum = 0;
for (int i = count.length - 1; i > 0; i--) {
sum += count[i];
if (sum >= i) {
return i;
}
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean carPooling(int[][] trips, int capacity) {
Map<Integer, Integer> map = new TreeMap<>();
for (int[] t : trips) {
map.put(t[1], map.getOrDefault(t[1], 0) + t[0]);
map.put(t[2], map.getOrDefault(t[2], 0) - t[0]);
}
for (int v : map.values()) {
capacity -= v;
if (capacity < 0) {
return false;
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public int maximumGap(int[] nums) {
int n = nums.length;
if (n == 1) {
return 0;
}
int min = nums[0], max = nums[0];
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
// Pigeonhold Principle
// max gap must be no less than bucketSize
// so we can safely focus on inter-bucket gaps only
int bucketSize = Math.max(1, (max - min) / (n - 1));
int bucketCount = (max - min) / bucketSize + 1;
// stores the min/max value in buckets
int[] bucketsMin = new int[bucketCount], bucketsMax = new int[bucketCount];
Arrays.fill(bucketsMin, Integer.MAX_VALUE);
Arrays.fill(bucketsMax, Integer.MIN_VALUE);
// puts numbers into buckets
for (int num : nums) {
// locates the correct bucket
int index = (num - min) / bucketSize;
bucketsMin[index] = Math.min(bucketsMin[index], num);
bucketsMax[index] = Math.max(bucketsMax[index], num);
}
// scans the buckets for the max gap.
// at least one of the gaps between adjacent buckets would be the max gap
int maxGap = Integer.MIN_VALUE, prev = min;
for (int i = 0; i < bucketCount; i++) {
// skips empty buckets
if (bucketsMin[i] == Integer.MAX_VALUE && bucketsMax[i] == Integer.MIN_VALUE) {
continue;
}
maxGap = Math.max(maxGap, bucketsMin[i] - prev);
prev = bucketsMax[i];
}
return maxGap;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private static final int MAX_DISTANCE = 2000;
public int[] assignBikes(int[][] workers, int[][] bikes) {
List<int[]>[] buckets = new ArrayList[MAX_DISTANCE + 1];
int n = workers.length, m = bikes.length;
// implicitly sorts first by workers, then by bikes
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int d = distance(workers[i], bikes[j]);
if (buckets[d] == null) {
buckets[d] = new ArrayList<>();
}
buckets[d].add(new int[] {i, j});
}
}
boolean[] bikeVisited = new boolean[m];
int[] result = new int[n];
Arrays.fill(result, -1);
for (int d = 0; d < buckets.length; d++) {
if (buckets[d] == null) {
continue;
}
for (int i = 0; i < buckets[d].size(); i++) {
int w = buckets[d].get(i)[0], b = buckets[d].get(i)[1];
if (bikeVisited[b] == true || result[w] >= 0) {
continue;
}
result[w] = b;
bikeVisited[b] = true;
}
}
return result;
}
private int distance(int[] p1, int[] p2) {
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
Counting Sort
Find Lucky Integer in an Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 0 <= arr[i] <= max
public int countingSort(int[] arr) {
// histogram
int[] count = new int[max + 1];
for (int a : arr) {
count[a]++;
}
// computes prefix sum
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
int[] result = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return result;
}
Special Array With X Elements Greater Than or Equal X
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int MAX_LENGTH = 100;
public int specialArray(int[] nums) {
int[] count = new int[MAX_LENGTH + 2];
// x <= nums.length
for (int num : nums) {
count[Math.min(num, nums.length)]++;
}
for (int i = nums.length; i >= 0; i--) {
count[i] += count[i + 1];
if (count[i] == i) {
return i;
}
}
return -1;
}
Dutch National Flag Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void sortColors(int[] nums) {
int red = 0, blue = nums.length - 1;
int i = red;
while (i <= blue) {
if (nums[i] == 0) {
swap(nums, i++, red++);
} else if (nums[i] == 2) {
swap(nums, i, blue--);
} else {
i++;
}
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
1
2
3
4
5
6
7
8
9
10
public void wiggleSort(int[] nums) {
int[] copy = Arrays.copyOf(nums, nums.length);
Arrays.sort(copy);
int median = (nums.length + 1) / 2 - 1;
int high = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
nums[i] = copy[i % 2 == 0 ? median-- : high--];
}
}
Multiple Dimensions
The Number of Weak Characters in the Game
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numberOfWeakCharacters(int[][] properties) {
// sorts the defense in descending order,
// so [1,2] is not a weak character in [[1,2],[1,3]]
Arrays.sort(properties, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int max = 0, count = 0;
for (int i = properties.length - 1; i >= 0; i--) {
if (properties[i][1] < max) {
count++;
}
max = Math.max(max, properties[i][1]);
}
return count;
}
Find the Number of Ways to Place People II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int numberOfPairs(vector<vector<int>>& points) {
ranges::sort(points, [](const auto &p1, const auto &p2){
return p1[0] == p2[0] ? p1[1] > p2[1] : p1[0] < p2[0];
});
int cnt = 0, n = points.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1, y = numeric_limits<int>::min(); j < n; j++)
if (points[i][1] >= points[j][1] && y < points[j][1]) {
cnt++;
y = points[j][1];
}
}
return cnt;
}
Index Mapping
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = findKthLargest(nums, (n + 1) / 2);
// dutch national flag sort on the virtual array
int left = 0, right = n - 1;
int i = 0;
while (i <= right) {
// puts smaller half of the numbers on the even indexes,
// and the larger half on the odd indexes,
// both from right to left
if (nums[mapIndex(i, n)] > median) {
swap(nums, mapIndex(i++, n), mapIndex(left++, n));
} else if (nums[mapIndex(i, n)] < median) {
swap(nums, mapIndex(i, n), mapIndex(right--, n));
} else {
i++;
}
}
}
/**
* Maps the virtual index to array index.
* e.g. if n == 6,
* 0 -> 1
* 1 -> 3
* 2 -> 5
* 3 -> 0
* 4 -> 2
* 5 -> 4
* @param index virtual index
* @param n array size
*/
private int mapIndex(int index, int n) {
// (n | 1) is the least odd that's no less than n
return (1 + 2 * index) % (n | 1);
}
// O(n) on average
private int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, k);
}
private int quickSelect(int[] nums, int low, int high, int k) {
int p = partition(nums, low, high);
// count of nums greater than or equal to nums[p]
int count = high - p + 1;
if (count == k) {
return nums[p];
}
if (count > k) {
return quickSelect(nums, p + 1, high, k);
}
return quickSelect(nums, low, p - 1, k - count);
}
private int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] < pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, high);
return i;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxWidthRamp(int[] nums) {
int n = nums.length;
Integer[] indices = new Integer[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
Arrays.sort(indices, Comparator.comparingInt(i -> nums[i]));
int max = 0, minIndex = n;
for (int i : indices) {
max = Math.max(max, i - minIndex);
minIndex = Math.min(minIndex, i);
}
return max;
}
This post is licensed under CC BY 4.0 by the author.