> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/array/sort.md).

# Sort

#### MergeSort

#### [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

```java
 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](https://leetcode.com/problems/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)*

```java
    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.* &#x20;

#### [973. K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/)

1\. Sort or Priority Queue: *T: O(n\*logn) S: O(n)*&#x20;

2\. Quick Selection: *T: O(n)  S: O(n)*&#x20;

```java
   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](https://leetcode.com/problems/kth-largest-element-in-an-array/)

```java
    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](https://leetcode.com/problems/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](https://leetcode.com/problems/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)`

```java
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](https://leetcode.com/problems/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.

```java
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](https://leetcode.com/discuss/interview-question/661336/Google-or-Onsite-or-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]

![](/files/-MLsI_5CQJybu7okeiVA)

> **Follow-up:**\
> Count number of increasing subsequences in the array `arr` of size `k`.

![](/files/-MLsIlH5OPzgZNF6y1mL)

Solution 1: dp  *O(k\*n^2)*&#x20;

```java
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

```java
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](https://leetcode.com/problems/reorder-data-in-log-files/)

```java
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](https://leetcode.com/submissions/detail/262023916/)

Sort all worker-bike distances in a PQ.

```java
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](https://leetcode.com/problems/h-index/)

Bucket sort, allocate to buckets and compare with values decreasingly.&#x20;

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