public int crossSum(int[] nums, int left, int right, int p) {
if (left == right) return nums[left];
int leftSubsum = Integer.MIN_VALUE;
int currSum = 0;
for(int i = p; i > left - 1; --i) {
currSum += nums[i];
leftSubsum = Math.max(leftSubsum, currSum);
}
int rightSubsum = Integer.MIN_VALUE;
currSum = 0;
for(int i = p + 1; i < right + 1; ++i) {
currSum += nums[i];
rightSubsum = Math.max(rightSubsum, currSum);
}
return leftSubsum + rightSubsum;
}
public int helper(int[] nums, int left, int right) {
if (left == right) return nums[left];
int p = (left + right) / 2;
int leftSum = helper(nums, left, p);
int rightSum = helper(nums, p + 1, right);
int crossSum = crossSum(nums, left, right, p);
return Math.max(Math.max(leftSum, rightSum), crossSum);
}
public int maxSubArray(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
QuickSort
CountingSort
BucketSort
HeapSort
Count the appearance of each word by using a map. Use Priority Queue to rank by frequency of appearance and alphabetic. Pop the top k elements.
T: O(n * logk) where n is the length of array, add n words to heap, each takes logk time. S: O(n)
class WordEntry {
int freq;
String word;
WordEntry(String word, int freq) {
this.word = word;
this.freq = freq;
}
}
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> count = new HashMap<>();
for (String w : words) {
count.put(w, count.getOrDefault(w, 0) + 1);
}
PriorityQueue<WordEntry> pq = new PriorityQueue<>(new Comparator<WordEntry>(){
public int compare(WordEntry a, WordEntry b) {
if (a.freq == b.freq) return a.word.compareTo(b.word);
return b.freq - a.freq;
}
});
for (String key : count.keySet()) {
pq.offer(new WordEntry(key, count.get(key)));
}
List<String> list = new ArrayList<>();
while (!pq.isEmpty() && k-- > 0) {
list.add(pq.poll().word);
}
return list;
}
Follow up:
1) Input is a stream? TreeMap or Use Redis Sorted sets to store, keep good speed as well as store lots of steam data
2) Can't fit memory? Partially read data and count the frequency, cumulate on the map. Use MapReduce to split the data set into different machines and consolidate the results.
1. Sort or Priority Queue: T: O(n*logn) S: O(n)
2. Quick Selection: T: O(n) S: O(n)
public int[][] kClosest(int[][] points, int K) {
int left = 0, right = points.length - 1;
while (left < right) {
int mid = partition(left, right, points);
if (mid == K) {
break;
} else if (mid < K) {
left = mid + 1;
} else right = mid - 1;
}
int[][] r = new int[K][2];
for (int i = 0; i < K; i++) {
r[i] = points[i];
}
return r;
}
private int partition(int left, int right, int[][] points) {
int j = 0;
for (int i = 0; i < right; i++) {
if (less(points[i], points[right])) {
swap(i, j, points);
j++;
}
}
swap(j, right, points);
return j;
}
private boolean less(int[] p1, int[] p2) {
return p1[0] * p1[0] + p1[1] * p1[1] < p2[0] * p2[0] + p2[1] * p2[1];
}
private void swap(int i, int j, int[][] points) {
int[] temp = points[i];
points[i] = points[j];
points[j] = temp;
}
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
if (k > n) return -1;
int left = 0, right = n - 1;
while (left <= right) {
int pivot = partition(nums, left, right);
if (pivot + k == n) {
return nums[pivot];
} else if (pivot < n - k) {
left = pivot + 1;
} else {
right = pivot - 1;
}
}
return -1;
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right], j = 0;
for (int i = 0; i < right; i++) {
if (nums[i] <= pivot) {
swap(nums, i, j);
j++;
}
}
swap(nums, j, right);
return j;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
280. Wiggle Sort
164. Maximum Gap
Sort the numbers by using comparator:
public int compare(String s1, String s2) {
String a = s1 + s2;
String b = s2 + s1;
return b.compareTo(a);
}
Then construct.
public String largestNumber(int[] nums) {
List<String> list = new ArrayList<>();
for (int n : nums) {
list.add(String.valueOf(n));
}
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
String a = s1 + s2;
String b = s2 + s1;
return b.compareTo(a);
}
});
if (list.get(0).charAt(0) == '0') return "0";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
}
return sb.toString();
}
"Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible."
Start from current size equal to n and reduce current size by one while it’s greater than 1. Let the current size be n. Do following for every n:
Find index of the maximum element in arr[0..n-1] . Let the index be 'index'
Call flip(arr, index)
Call flip(arr, n-1)
public List<Integer> pancakeSort(int[] A) {
List<Integer> result = new ArrayList<>();
int n = A.length, largest = n;
for (int i = 0; i < n; i++) {
int index = find(A, largest);
flip(A, index);
flip(A, largest - 1);
result.add(index + 1);
result.add(largest--);
}
return result;
}
private int find(int[] A, int target) {
for (int i = 0; i < A.length; i++) {
if (A[i] == target) {
return i;
}
}
return -1;
}
private void flip(int[] A, int index) {
int i = 0, j = index;
while (i < j) {
int temp = A[i];
A[i++] = A[j];
A[j--] = temp;
}
}
Mergesort. For each number store the index and its value. When merge, count the number of the right is smaller than left, and append the count to the result.
class Item {
int index;
int val;
Item(int index, int val) {
this.index = index;
this.val = val;
}
}
public List<Integer> countSmaller(int[] nums) {
Item[] arr = new Item[nums.length];
for (int i = 0; i < nums.length; i++) {
arr[i] = new Item(i, nums[i]);
}
int[] count = new int[nums.length];
mergesort(0, nums.length - 1, arr, count);
List<Integer> res = new ArrayList<>();
for (int n : count) res.add(n);
return res;
}
private void mergesort(int start, int end, Item[] arr, int[] count) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
mergesort(start, mid, arr, count);
mergesort(mid + 1, end, arr, count);
merge(start, mid, end, arr, count);
}
private void merge(int start, int mid, int end, Item[] arr, int[] counts) {
Item[] temp = new Item[end - start + 1];
int count = 0;
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (arr[j].val < arr[i].val) {
temp[k++] = arr[j++];
count++;
} else {
counts[arr[i].index] += count;
temp[k++] = arr[i++];
}
}
while (i <= mid) {
counts[arr[i].index] += count;
temp[k++] = arr[i++];
}
while (j <= end) {
temp[k++] = arr[j++];
}
System.arraycopy(temp, 0, arr, start, end- start + 1);
}
Given an array arr of size n. Find the number of triples (i, j, k) where:
i < j < k
arr[i] < arr[j] < arr[k]
Follow-up:
Count number of increasing subsequences in the array arr of size k.
Solution 1: dp O(k*n^2)
private static int solve(int[] nums, int k) {
int[][] dp = new int[k][nums.length];
for (int i = 0; i < nums.length; i++)
dp[0][i] = 1;
for (int l = 1; l < k; l++) {
for (int i = l; i < nums.length; i++) {
for (int j = l - 1; j < i; j++) {
if (nums[j] < nums[i]) {
dp[l][i] += dp[l - 1][j];
}
}
}
}
int res = 0;
for (int i = k - 1; i < nums.length; i++) {
res += dp[k - 1][i];
}
return res;
}
Solution 2: Merge Sort
private int countTriplets(int[] nums) {
int[] pos = new int[nums.length];
for(int i = 0; i < pos.length; i++) {
pos[i] = i;
}
// first row - count of elements lesser than i-th element
// second row - count of elements greater than i-th element
int[][] leGr = new int[2][nums.length];
sort(nums, pos, leGr, 0, nums.length - 1);
int ans = 0;
for(int j = 0; j < nums.length; j++) {
ans += leGr[0][j] * leGr[1][j];
}
return ans;
}
private void sort(int[] nums, int[] pos, int[][] leGr, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
sort(nums, pos, leGr, lo, mid);
sort(nums, pos, leGr, mid + 1, hi);
merge(nums, pos, leGr, lo, mid, hi);
}
private void merge(int[] nums, int[] pos, int[][] leGr, int lo, int mid, int hi) {
int[] auxPos = new int[pos.length];
for(int i = 0; i < pos.length; i++)
auxPos[i] = pos[i];
int i = lo, j = mid + 1, k = lo;
while(i <= mid && j <= hi) {
if (nums[pos[i]] < nums[pos[j]]) {
leGr[1][pos[i]] += hi - j + 1;
auxPos[k++] = pos[i++];
} else {
leGr[0][pos[j]] += i - lo;
auxPos[k++] = pos[j++];
}
}
while(i <= mid) {
auxPos[k++] = pos[i++];
}
while(j <= hi) {
leGr[0][pos[j++]] += i - lo;
}
System.arraycopy(auxPos, 0, pos, 0, pos.length);
}
public String[] reorderLogFiles(String[] logs) {
List<String> list = new ArrayList<>();
List<String> numlist = new ArrayList<>();
for (int i = 0; i < logs.length; i++) {
int index = logs[i].indexOf(" ");
if (Character.isLetter(logs[i].charAt(index + 1))) { // letter log
list.add(logs[i]);
} else {
numlist.add(logs[i]);
}
}
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String s1 = o1.substring(o1.indexOf(" ") + 1);
String s2 = o2.substring(o2.indexOf(" ") + 1);
if (s1.equals(s2)) return o1.compareTo(o2);
return s1.compareTo(s2);
}
});
list.addAll(numlist);
String[] res = new String[list.size()];
for (int i = 0; i < res.length; i++) {
res[i] = list.get(i);
}
return res;
}
Sort all worker-bike distances in a PQ.
public int[] assignBikes(int[][] workers, int[][] bikes) {
PriorityQueue<Workerbikedist> pq = new PriorityQueue<>((o1,o2) -> {
if (o1.dist == o2.dist) {
if (o1.worker == o2.worker) {
return o1.bike - o2.bike;
}
return o1.worker - o2.worker;
}
return o1.dist - o2.dist;
});
for (int i = 0; i < workers.length; i++) {
for (int j = 0; j < bikes.length; j++) {
pq.offer(new Workerbikedist(i, j, getDist(workers[i], bikes[j])));
}
}
int n = workers.length;
int[] res = new int[n];
Arrays.fill(res, -1);
boolean[] visitedBikes = new boolean[bikes.length];
while (!pq.isEmpty()) {
Workerbikedist curt = pq.poll();
if (res[curt.worker] == -1 && !visitedBikes[curt.bike]) {
res[curt.worker] = curt.bike;
visitedBikes[curt.bike] = true;
}
}
return res;
}
private int getDist(int[] worker, int[] bike) {
return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
}
class Workerbikedist {
int bike;
int worker;
int dist;
Workerbikedist(int worker, int bike, int dist) {
this.worker = worker;
this.bike = bike;
this.dist = dist;
}
}
