- Watch out for
- Questions
- Given an unsorted array of numbers, find the ‘K’ largest numbers in it.
- Given an unsorted array of numbers, find Kth smallest number in it. Please note that it is the Kth smallest number in the sorted order, not the Kth distinct element.
- Given an array of points in a 2D plane, find ‘K’ closest points to the origin.
- Given ‘N’ ropes with different lengths, we need to connect these ropes into one big rope with minimum cost. The cost of connecting two ropes is equal to the sum of their lengths.
- Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.
- Given a string, sort it based on the decreasing frequency of its characters.
- Given a sorted number array and two integers ‘K’ and ‘X’, find ‘K’ closest numbers to ‘X’ in the array. Return the numbers in the sorted order. ‘X’ is not necessarily present in the array.
- Given an array of numbers and a number ‘K’, we need to remove ‘K’ numbers from the array such that we are left with maximum distinct numbers.
- Given an array, find the sum of all numbers between the K1’th and K2’th smallest elements of that array.
- Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.
- Given a string and a number ‘K’, find if the string can be rearranged such that the same characters are at least ‘K’ distance apart from each other.
- You are given a list of tasks that need to be run, in any order, on a server. Each task will take one CPU interval to execute but once a task has finished, it has a cooling period during which it can’t be run again. If the cooling period for all tasks is ‘K’ intervals, find the minimum number of CPU intervals that the server needs to finish all tasks. If at any time the server can’t execute any task then it must stay idle.
- Design a class that simulates a Stack data structure, implementing the following two operations:

There are some greedy algorithms in this section that could use revision.

```
Example 1:
Input: [3, 1, 5, 12, 2, 11], K = 3
Output: [5, 12, 11]
Example 2:
Input: [5, 12, 11, -1, 12], K = 3
Output: [12, 11, 12]
```

**Implementation: KLargestElements**

We can use a max heap and get the top K.

Each `heapify()`

uses `O(logn)`

and there are `N`

elements. So time complexity, is `O(NlogK)`

.

`O(K)`

```
Example 1:
Input: [1, 5, 12, 2, 11, 5], K = 3
Output: 5
Explanation: The 3rd smallest number is '5', as the first two smaller numbers are [1, 2].
Example 2:
Input: [1, 5, 12, 2, 11, 5], K = 4
Output: 5
Explanation: The 4th smallest number is '5', as the first three small numbers are [1, 2, 5].
Example 3:
Input: [5, 12, 11, -1, 12], K = 3
Output: 11
Explanation: The 3rd smallest number is '11', as the first two small numbers are [5, -1].
```

**Implementation: KthSmallestNumber**

We can use a min-heap to store the numbers and keep polling till we get the Kth smallest number.

`O(nlogn)`

`O(n)`

```
Example 1:
Input: points = [[1,2],[1,3]], K = 1
Output: [[1,2]]
Explanation: The Euclidean distance between (1, 2) and the origin is sqrt(5).
The Euclidean distance between (1, 3) and the origin is sqrt(10).
Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.
Example 2:
Input: point = [[1, 3], [3, 4], [2, -1]], K = 2
Output: [[1, 3], [2, -1]]
```

`Dist = sqrt( (x^2) + (y^2) )`

We calculate all the distances, store them in a min-heap, and return the `K`

closest points to origin.

`O(N log K)`

`O(N)`

```
Example 1:
Input: [1, 3, 11, 5]
Output: 33
Explanation: First connect 1+3(=4), then 4+5(=9), and then 9+11(=20). So the total cost is 33 (4+9+20)
Example 2:
Input: [3, 4, 5, 6]
Output: 36
Explanation: First connect 3+4(=7), then 5+6(=11), 7+11(=18). Total cost is 36 (7+11+18)
Example 3:
Input: [1, 3, 11, 5, 2]
Output: 42
Explanation: First connect 1+2(=3), then 3+3(=6), 6+5(=11), 11+11(=22). Total cost is 42 (3+6+11+22)
```

**Implementation: ConnectRopes**

Follow a greedy approach to connect the smallest ropes first.

`O(nlogn)`

`O(n)`

```
Example 1:
Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]
Explanation: Both '11' and '12' apeared twice.
Example 2:
Input: [5, 12, 11, 3, 11], K = 2
Output: [11, 5] or [11, 12] or [11, 3]
Explanation: Only '11' appeared twice, all other numbers appeared once.
```

**Implementation: TopKFrequentNumbers**

We need to find the frequency of each number, we can do this using a map. Once we have the frequencies, we can use a max-heap to find the top k frequent numbers. We can also sort by the frequency values and return the top k.

`O(nlogk)`

`O(n)`

```
Example 1:
Input: "Programming"
Output: "rrggmmPiano"
Explanation: 'r', 'g', and 'm' appeared twice, so they need to appear before any other character.
Example 2:
Input: "abcbab"
Output: "bbbaac"
Explanation: 'b' appeared three times, 'a' appeared twice, and 'c' appeared only once.
```

**Implementation: StringSort**

Similar to previous, we can use a max heap but instead of adding the char to the result-list, we repeat the char the frequency number of time.

`O(nlogn)`

`O(n)`

```
Example 1:
Input: [5, 6, 7, 8, 9], K = 3, X = 7
Output: [6, 7, 8]
Example 2:
Input: [2, 4, 5, 6, 9], K = 3, X = 6
Output: [4, 5, 6]
Example 3:
Input: [2, 4, 5, 6, 9], K = 3, X = 10
Output: [5, 6, 9]
```

**Implementation: KClosestNumbers**

- Find the number closest to
`X`

using binary search. - The
`K`

closest numbers will be adjacent to the closest number. - We go K numbers in both directions and put it in min-heap based on the distance from
`X`

. - Then we poll the
`K`

numbers from the heap.

`O(logn)`

for binary search. `O(nlogn)`

for the heap operations. So total of `O(nlogn)`

.

`O(n)`

if we need to store all numbers in the heap.

```
Example 1:
Input: [7, 3, 5, 8, 5, 3, 3], and K=2
Output: 3
Explanation: We can remove two occurrences of 3 to be left with 3 distinct numbers [7, 3, 8], we have to skip 5 because it is not distinct and appeared twice.
Another solution could be to remove one instance of '5' and '3' each to be left with three distinct numbers [7, 5, 8], in this case, we have to skip 3 because it appeared twice.
Example 2:
Input: [3, 5, 12, 11, 12], and K=3
Output: 2
Explanation: We can remove one occurrence of 12, after which all numbers will become distinct. Then we can delete any two numbers which will leave us 2 distinct numbers in the result.
Example 3:
Input: [1, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5], and K=2
Output: 3
Explanation: We can remove one occurrence of '4' to get three distinct numbers.
```

**Implementation: MaxDistinctElements**

The trick to this question is figuring out the **greedy** approach to the solution.

So, there could be two groups of numbers in the array:

- Distinct numbers - in which case we simply count how many of them there are.
- Non-distinct numbers - we count the frequency of appearence of these numbers.

Now, we are allowed `K`

removals, so we take the first non-distinct number with the min frequency and see if we can remove all but one occurences. If we cant, aka, we dont have enough K's, the current count of distinct numbers is the solution. If we can we add that to our count of distinct numbers and keep doing the same for all non-distinct numbers.

`O(n)`

for frequency counting. `O(nlogn)`

for heap operations. So, total of `O(nlogn)`

.

`O(n)`

for the map.

```
Example 1:
Input: [1, 3, 12, 5, 15, 11], and K1=3, K2=6
Output: 23
Explanation: The 3rd smallest number is 5 and 6th smallest number 15. The sum of numbers coming
between 5 and 15 is 23 (11+12).
Example 2:
Input: [3, 5, 8, 7], and K1=1, K2=4
Output: 12
Explanation: The sum of the numbers between the 1st smallest number (3) and the 4th smallest
number (8) is 12 (5+7).
```

**Implementation: SumOfElements**

Taking example, `Input: [1, 3, 12, 5, 15, 11], and K1=3, K2=6`

, the sorted form of the array is `[1, 3, 5, 11, 12, 15]`

. The third smallest number is 5 and the 6th smallest is 15. Between them, we have 11 and 12 which sums up to 23.

So essentially, we need to keep track of the `k1`

smallest number, the `k2`

smallest number and the sum of all numbers in between.

We can take a min heap and keep polling till `k1=0`

. After that, we sum up the numbers till `k2`

becomes 0. The result sum is what we want.

`O(nlogn)`

`O(n)`

```
Example 1:
Input: "aappp"
Output: "papap"
Explanation: In "papap", none of the repeating characters come next to each other.
Example 2:
Input: "Programming"
Output: "rgmrgmPiano" or "gmringmrPoa" or "gmrPagimnor", etc.
Explanation: None of the repeating characters come next to each other.
Example 3:
Input: "aapa"
Output: ""
Explanation: In all arrangements of "aapa", atleast two 'a' will come together e.g., "apaa", "paaa".
```

**Implementation: RearrangeStrings**

The greedy algorithm here is:

- We create a max heap of the characters and their frequencies, heapify by their frequencies.
- We start with the element with the most frequency, we add it to our result string.
- But we dont put it back to the heap because we dont want to accidentally repeat it.
- We hold that element and add the next element.
- When we add the next element, we offer the previous element to the heap (
*as long as frequency > 0*) and hold the element just added to the result string.

`O(nlogn)`

`O(n)`

```
Example 1:
Input: "mmpp", K=2
Output: "mpmp" or "pmpm"
Explanation: All same characters are 2 distance apart.
Example 2:
Input: "Programming", K=3
Output: "rgmPrgmiano" or "gmringmrPoa" or "gmrPagimnor" and a few more
Explanation: All same characters are 3 distance apart.
Example 3:
Input: "aab", K=2
Output: "aba"
Explanation: All same characters are 2 distance apart.
Example 4:
Input: "aappa", K=3
Output: ""
Explanation: We cannot find an arrangement of the string where any two 'a' are 3 distance apart.
```

**Implementation: RearrangeStringKDistApart**

There are two considerations here: 1. Repeating characters. 2. And a certain number of counts till a character cannot be used, once it has been used.

- First, lets start with keeping a frequency of all characters.
- Next, we say every character can potentially be the first character. So we initialize a pair with
`<Char, 0>`

. - Then, we put all of these into a min-heap (min-heap, since our indices are in increasing order).
- Every time we poll a character, we (1) reduce the frequency and (2) put it at
`index+k`

, when it will be next pulled to be added to the result.

`O(nlogn)`

`O(n)`

```
Example 1:
Input: [a, a, a, b, c, c], K=2
Output: 7
Explanation: a -> c -> b -> a -> c -> idle -> a
Example 2:
Input: [a, b, a], K=3
Output: 5
Explanation: a -> b -> idle -> idle -> a
```

**Implementation: SchedulingTasks**

We can make the following observations from the question: 1. The tasks may execute in any order. 2. Each task takes 1 CPU interval. 3. If no tasks can run on a particular interval, the CPU simply remains idle for that interval. 4. We need to optimize for the min number of CPU intervals.

Since we need to optimize for the min number of CPU intervals, we need to interleave different tasks so we don't 'waste' CPU cycles. If we didn't needed to optimize for CPU intervals, we could have just picked a task and waited for it to finish, then move onto the next one and so on.

First, we need to know how many times a task needs to execute. This we can do by keeping a map of `task -> frequency`

.

Next, we need to keep track of a couple of things:
1. The current CPU interval. This we can do with a `index`

variable.
2. The interval on which the next task should run.

But how do we know which task should run on a particular interval, if any should run at all. The second concern is how do we identify the most immediate task that should be run.

We can keep a `min-heap`

of the task and the interval on which it should run. There can be two scenarios then:
1. The heap tells us that there is a task whose run interval is the current CPU interval or a CPU interval before the current one.
2. The heap tells us that there is a task whose run interval is greater than the current CPU interval and thus, cannot be run yet.

Thus, our algorithm becomes:
1. Create a frequency map of `task->count`

of the times the task should be run.
2. Create a min-heap of the task task and the interval at which it should run. We can start all tasks with `interval=0`

, aka, every task has a shot to run on the first CPU interval.
3. Whenever, we run a task, we put the task and interval back to the heap for the next run, iff, the frequency of the task is `>0`

.
4. We continue running till the heap runs out of tasks.

`O(nlogn)`

`O(1)`

```
push(int num): Pushes the number ‘num’ on the stack.
pop(): Returns the most frequent number in the stack. If there is a tie, return the number which was pushed later.
```

```
Example:
After following push operations: push(1), push(2), push(3), push(2), push(1), push(2), push(5)
1. pop() should return 2, as it is the most frequent number
2. Next pop() should return 1
3. Next pop() should return 2
```

**Implementation: FrequencyStack**

```
1 -> 2
2 -> 3
3 -> 1
5 -> 1
t0 t1 t2 t3 t4 t5 t6
push(1), push(2), push(3), push(2), push(1), push(2), push(5)
```

Taking the example, the expected output is:
1. Since there are 3 2's on the first `pop()`

call, we return 2. Now frequency of 2 is reduced to 2.
2. On the second `pop()`

call, we have both 1 and 2 with frequency 2. Since there's a clash, the input time takes over. We popped the second last 2 in the first `pop()`

call, and 1 was pushed after the 4th last push for 2, so we return 1.

Thus, we observe: 1. There are two conditions for popping. 2. If frequencies mismatch, we return the one with the higher frequency. 3. If frequencies match, we return the one with the higher sequence number.

We ofcourse are going to use a max heap. But how to design the comparator?

We need to keep track of the frequency, which we can do using a map. So our first comparison would be based on that frequency. Next, we need to keep a linked list of times (or sequence numbers), linked list to maintain order of insertion. As we pop elements, we need to keep removing from this list. So our second comparison (if frequencies are equal), would be based on the last element of the list.

A second, probably simpler, way could be to keep insert the map entries as we get new elements. So for instance, we get

```
push -> 2, 2, 1, 2, 1
first, map will have key -> 2, freq -> 1, seq -> 1. we insert this combination into heap as well.
next, map will have key -> 2, freq -> 2, seq -> 2. we insert this combination into heap as well.
at this point, the map has one element with key 2 but the heap has 2 elements, making our comparator simpler.
```

`O(nlogn)`

for both operations.

`O(n)`