Medium

![https://leetcode.com/problems/sort-characters-by-frequency/] Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. Example 2: Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together. Example 3: Input: "Aabb" Output: "bbAa" Explanation: “bbaA” is also a valid answer, but “Aabb” is incorrect. Note that ‘A’ and ‘a’ are treated as two different characters. ...

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result. If not possible, return the empty string. Example 1: Input: S = "aab" Output: "aba" Example 2: Input: S = "aaab" Output: "" Note: S will consist of lowercase letters and have length in range [1, 500]. class Solution { int n = 0; int[][] heap = new int[27][2]; // Queue<int[]> q = new PriorityQueue<int[]>((a, b) -> -Integer.compare(a[1], b[1])); public String reorganizeString(String S) { int[] freq = new int[26]; Arrays.fill(heap, new int[] {0, 0}); for (char c: S.toCharArray()) { freq[c - 'a']++; } for (int i = 0; i < freq.length; i++) { if (freq[i] != 0) { add(new int[]{i, freq[i]}); } } StringBuilder sb = new StringBuilder(); // while (!isEmpty()) { while (size() > 1) { int[] a = poll(); char aa = (char) ('a' + a[0]); int[] b = poll(); char bb = (char) ('a' + b[0]); char select; if (sb.length() == 0) { select = aa; a[1]--; } else if (sb.charAt(sb.length() - 1) == aa) { select = bb; b[1]--; } else { select = aa; a[1]--; } sb.append(select); if (a[1] != 0) { add(a); } if (b[1] != 0) { add(b); } } while (!isEmpty()) { // System.out.println(Arrays.deepToString(heap)); var a = poll(); char aa = (char) ('a' + a[0]); if (sb.length() > 0 && sb.charAt(sb.length() - 1) == aa) { sb.setLength(0); break; } else { a[1]--; sb.append(aa); if (a[1] != 0) { // System.out.println("add = " + Arrays.toString(a)); add(a); } } } return sb.toString(); } int[] poll() { // return q.poll(); int[] max = Arrays.copyOf(heap[1], 2); heap[1][0] = 0; heap[1][1] = 0; heap[1][0] = heap[n][0]; heap[1][1] = heap[n][1]; n--; heap[n + 1][0] = 0; heap[n + 1][1] = 0; sink(1); return max; } void add(int[] val) { // q.add(val); heap[++n] = Arrays.copyOf(val, 2); swim(n); } boolean isEmpty() { return size() == 0; } int size() { return n; // return q.size(); } // max heap parent > child; j > i // wrong j < i void swim(int i) { int j = i / 2; if (j > 0 && less(j, i)) { swap(i, j); swim(j); } } void swap(int i, int j) { int[] temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } void sink(int i) { int left = 2 * i; int right = 2 * i + 1; int largest = i; if (left < heap.length && less(largest, left)) { largest = left; } if (right < heap.length && less(largest, right)) { largest = right; } if (largest != i) { swap(i, largest); sink(largest); } } boolean less(int i, int j) { return heap[i][1] < heap[j][1]; } } Solution 2022-01-29 class Solution { public String reorganizeString(String s) { if (s.length() == 0) return ""; Queue<int[]> heap = buildQHeap(s); StringBuilder sb = new StringBuilder(); while (heap.size() > 0) { int[] first = heap.poll(); if (sb.length() == 0) { sb.append((char) ('a' + first[0])); first[1]--; if (first[1] != 0) { heap.add(first); } } else { int prev = sb.charAt(sb.length() - 1) - 'a'; if (prev != first[0]) { sb.append((char) ('a' + first[0])); first[1]--; if (first[1] != 0) { heap.add(first); } } else { if (heap.size() == 0) return ""; int[] second = heap.poll(); sb.append((char) ('a' + second[0])); second[1]--; if (second[1] != 0) { heap.add(second); } heap.add(first); } } } return sb.toString(); } Queue<int[]> buildHeap(String s) { int[] freq = new int[26]; for (char c: s.toCharArray()) { int index = (int)(c - 'a'); freq[index]++; } Queue<int[]> heap = new PriorityQueue <>((a, b) -> - a[1] + b[1]); for (int i = 0; i < 26; i++) { if (freq[i] > 0) { heap.add(new int[] {i, freq[i]}); } } return heap; } }

![https://leetcode.com/problems/last-stone-weight/] We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.) ...

![https://leetcode.com/problems/kth-largest-element-in-an-array/] Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note: You may assume k is always valid, 1 ≤ k ≤ array's length. class Solution { public int findKthLargest(int[] nums, int k) { MinPQ pq = new MinPQ(k); for (int a: nums) { pq.add(a); } return pq.min(); } static class MinPQ { final int[] pq; int n = 0; MinPQ(int size) { this.pq = new int[size + 1]; } int min() { return pq[1]; } void add(int i) { if (n < pq.length - 1) { pq[++n] = i; swim(n); } else { if (i > pq[1]) { pq[1] = i; sink(1); } } } void sink(int i) { int left = 2 * i; int right = 2 * i + 1; int smallest = i; if (left < pq.length && pq[left] < pq[i]) { smallest = left; } if (right < pq.length && pq[right] < pq[smallest]) { smallest = right; } if (smallest != i) { swap(i, smallest); sink(smallest); } } void swim(int i) { int j = i / 2; if (j > 0 && pq[i] < pq[j]) { swap(i, j); swim(j); } } void swap(int i, int j) { int t = pq[i]; pq[i] = pq[j]; pq[j] = t; } } } Solution 2 class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; sort(nums, 0, n - 1); return nums[n - k]; } void sort(int[] nums, int lo, int hi) { if (lo >= hi) return; int j = partition(nums, lo, hi); sort(nums, lo, j - 1); sort(nums, j + 1, hi); } int partition(int[] nums, int lo, int hi) { int i = lo; int j = hi + 1; while (true) { while (nums[++i] < nums[lo]) { if (i == hi) break; } while (nums[lo] < nums[--j]) { if (j == lo) break; } if (i < j) { swap(nums, i, j); } else { break; } } swap(nums, lo, j); return j; } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } Solution 3 class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); for (int value: nums) { pq.add(value); if (pq.size() == k + 1) { pq.poll(); } // System.out.println(pq); } return pq.peek(); } } Solution - Quick Select class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; int lo = 0; int hi = n - 1; while (lo < hi) { int j = partition(nums, lo, hi); if (j < n - k) { lo = j + 1; } else if (n - k < j) { hi = j - 1; } else { return nums[n - k]; } } return nums[n - k]; } int partition(int[] nums, int lo, int hi) { int i = lo; int j = hi + 1; while (true) { while (nums[++i] < nums[lo]) { if (i == hi) break; } while (nums[lo] < nums[--j]) { if (j == lo) break; } if (i < j) { swap(nums, i, j); } else { break; } } swap(nums, lo, j); return j; } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } Solution 2022-01-24 class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; int lo = 0; int hi = n - 1; k = n - k; while (lo < hi) { int m = partition(nums, lo, hi); if (m > k) { hi = m - 1; } else if (m < k) { lo = m + 1; } else { return nums[m]; } } return nums[lo]; } int partition(int[] nums, int lo, int hi) { int swapIndex = lo; while (lo < hi) { while (lo < hi && nums[hi] >= nums[swapIndex]) { hi--; } while (lo < hi && nums[lo] <= nums[swapIndex]) { lo++; } swap(nums, lo, hi); } swap(nums, lo, swapIndex); return lo; } void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }

![https://leetcode.com/problems/top-k-frequent-elements/] Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique. You can return the answer in any order. class Solution { public int[] topKFrequent(int[] nums, int k) { List<Integer>[] buckets = new List[nums.length + 1]; Map<Integer, Integer> freq = new HashMap<>(); for (int num: nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } for (var entry: freq.entrySet()) { List<Integer> bucket = buckets[entry.getValue()]; if (bucket == null) { bucket = new ArrayList<>(); } bucket.add(entry.getKey()); buckets[entry.getValue()] = bucket; } int[] res = new int[k]; int j = 0; for (int i = buckets.length - 1; i >= 0 && j < k; i--) { if (buckets[i] != null) { for (Integer val : buckets[i]) { res[j++] = val; } } } return res; } public int[] topKFrequent2(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); for (int num: nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue()); for (Map.Entry<Integer, Integer> entry: freq.entrySet()) { q.add(entry); if (q.size() > k) { q.poll(); } System.out.println(q); } int[] res = new int[q.size()]; int i = 0; for (var entry: q) { res[i++] = entry.getKey(); } return res; } }

![https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/] Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example 1: Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13 Example 2: Input: matrix = [[-5]], k = 1 Output: -5 Constraints: ...

![https://leetcode.com/problems/insert-interval/] Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10]. Example 3: Input: intervals = [], newInterval = [5,7] Output: [[5,7]] Example 4: Input: intervals = [[1,5]], newInterval = [2,3] Output: [[1,5]] Example 5: Input: intervals = [[1,5]], newInterval = [2,7] Output: [[1,7]] Constraints: ...

![https://leetcode.com/problems/sort-the-matrix-diagonally/] A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2]. Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix. ...

![https://leetcode.com/problems/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] Example 2: Input: nums = [2,0,1] Output: [0,1,2] Example 3: Input: nums = [0] Output: [0] Example 4: Input: nums = [1] Output: [1] Constraints: ...

![https://leetcode.com/problems/merge-intervals/] Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. Constraints: ...