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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/array/sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.