sorting

QuickSelect (for K-th Largest/Smallest & K-Closest, etc)

• Main difference with quicksort is that in QuickSelect, we only need to go either left or right
• In QuickSort, we do it in both directions (divide and conquer)
• In partition function, we have 3 sections - elements that should come before Pivot, pivot, and elements that should be after Pivot
• Some clarifications before doing anything
  • Define the comparator logic for sorting elements correctly
  • Define which Array should we do quickselect on - sometimes, it's the input array itself BUT sometimes on a new array (like creating array of unique elemnts from the input array which may contain duplicates)
• During the actual partition, we have two variables i and j, where i is the first unsolved element
  • we do a forloop j (from l to r), whenever we find a j that's out of place, we swap i and j. Then, i++
  • j is the scanner, and it THROWS a misplaced element to i
• After partition, we have pivot in its final sorted position

973. K Closest Points to Origin

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int l = 0, r = points.length - 1;
        while(l <= r){
            int pivotIdx = rand.nextInt(r - l + 1) + l;
            int[] pivot = points[pivotIdx];
            swap(points, pivotIdx, r);

            int i = l;
            for(int j = l; j < r; j++)
                if(compare(points[j], pivot) <= 0)
                    swap(points, i++, j);
            swap(points, i, r);

            // if pivot is k, all elements to left are sorted.
            // return immediately as order doesn't matter
            if(i == k) break; 
            if(i < k) l = i + 1;
            else r = i - 1;
        }
        return Arrays.copyOfRange(points, 0, k);
    }
}

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: Sort elements with ascending order freq [3,2,1]
        return last 2 elements

class Solution {
    private Map<Integer, Integer> map = new HashMap<>(); // num -> freq
    int[] uniq;
    private Random rand = new Random();

    public int[] topKFrequent(int[] nums, int k) {
        for(int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        int idx = 0, n = map.size();
        // sort uniq number array not the input array itself
        uniq = new int[n]; 
        for(int num: map.keySet()) uniq[idx++] = num;

        // the uniq array will be sorted ascending frequency of elements
        // stop when uniq.length - k is in it's correct pos
        int l = 0, r = n - 1;
        while(l <= r){
            int pivotIdx = rand.nextInt(r - l + 1) + l;
            int pivotFreq = map.get(uniq[pivotIdx]);
            swap(pivotIdx, r); // pivot goes to the end

            int i = l; // L not 0!!
            for(int j = l; j < r; j++)
                if(map.get(uniq[j]) <= pivotFreq)
                    swap(i++, j);
            swap(i, r);

            // elements to the right of i has higher freqs
            if(i == n-k) break;
            if(i < n-k) l = i + 1; // go right towards n-k
            else r = i - 1;
        }
        return Arrays.copyOfRange(uniq, n-k, n);
    }
}

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

class Solution {
    /* credits: @meganlee
        quicksort 3-way partition
        +------+---------+------------+------+
        |  < p |  = p    |  unseen.   | > p  |
        +------+---------+------------+------+
               ↑         ↑            ↑
               lt        i            gt 
        lt: 1st elem == pivot
        i:  1st unseen elem
        gt: last unseen elem

        When nums[i] == 0, swap it with lt(which is 1)
        lt is now 0 so advance lt, i is now 1 advance i

        When nums[i] == 2, swap it with gt (which is unprocessed)
        gt is now 2, decrement gt
        don't increment i because the value is unprocessed (previously on gt)
    */
    public void sortColors(int[] nums) {
        int zeros = 0, i = 0, twos = nums.length - 1;

        while(i <= twos){
            // throw back 0s
            if(nums[i] == 0)
                swap(nums, i++, zeros++);
    
            // throw forward 2s
            else if(nums[i] == 2)
                swap(nums, i, twos--);
    
            // let 1s stay in the middle
            else i++;
        }
    }
}