Heap

1845. Seat Reservation Manager Design a system that manages the reservation state of n seats that are numbered from 1 to n. Implement the SeatManager class: SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available. int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number. void unreserve(int seatNumber) Unreserves the seat with the given seatNumber. Example 1: Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null] Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5]. ...

![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: ...

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Implement KthLargest class: KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums. int add(int val) Returns the element representing the kth largest element in the stream. Example 1: Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8] Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8 Constraints: ...