Sort

MergeSort

53. Maximum Subarray

 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

692. Top K Frequent Words

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.

973. K Closest Points to Origin

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

215. Kth Largest Element in an Array

    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

179. Largest Number

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();
}

969. Pancake Sorting

"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:

1. Find index of the maximum element in arr[0..n-1] . Let the index be 'index'

2. Call flip(arr, index)

3. 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;
    }
}

315. Count of Smaller Numbers After Self

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

Count Increasing Subsequences

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

937. Reorder Data in Log Files

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

1057. Campus Bikes

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

274. H-Index

Bucket sort, allocate to buckets and compare with values decreasingly.

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] buckets = new int[n + 1];
    for (int c : citations) {
        if (c >= n) {
            buckets[n]++;
        } else {
            buckets[c]++;
        }
    }
    int count = 0;
    for (int i = n; i >= 0; i--) {
        count += buckets[i];
        if (count >= i) {
            return i;
        }
    }
    return 0;
}