Watch out for

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

Questions

Given an unsorted array of numbers, find the ‘K’ largest numbers in it.

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.

Time complexity

Each heapify() uses O(logn) and there are N elements. So time complexity, is O(NlogK).

Space complexity

O(K)

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.

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.

Time complexity

O(nlogn)

Space complexity

O(n)

Given an array of points in a 2D plane, find ‘K’ closest points to the origin.

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.

Time complexity

O(N log K)

Space complexity

O(N)

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.

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.

Time complexity

O(nlogn)

Space complexity

O(n)

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

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.

Time complexity

O(nlogk)

Space complexity

O(n)

Given a string, sort it based on the decreasing frequency of its characters.

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.

Time complexity

O(nlogn)

Space complexity

O(n)

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.

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

  1. Find the number closest to X using binary search.
  2. The K closest numbers will be adjacent to the closest number.
  3. We go K numbers in both directions and put it in min-heap based on the distance from X.
  4. Then we poll the K numbers from the heap.

Time complexity

O(logn) for binary search. O(nlogn) for the heap operations. So total of O(nlogn).

Space complexity

O(n) if we need to store all numbers in the heap.

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.

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:

  1. Distinct numbers - in which case we simply count how many of them there are.
  2. 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.

Time complexity

O(n) for frequency counting. O(nlogn) for heap operations. So, total of O(nlogn).

Space complexity

O(n) for the map.

Given an array, find the sum of all numbers between the K1’th and K2’th smallest elements of that array.

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.

Time complexity

O(nlogn)

Space complexity

O(n)

Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.

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:

  1. We create a max heap of the characters and their frequencies, heapify by their frequencies.
  2. We start with the element with the most frequency, we add it to our result string.
  3. But we dont put it back to the heap because we dont want to accidentally repeat it.
  4. We hold that element and add the next element.
  5. 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.

Time complexity

O(nlogn)

Space complexity

O(n)

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.

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.

Time complexity

O(nlogn)

Space complexity

O(n)

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.

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.

Time complexity

O(nlogn)

Space complexity

O(1)

Design a class that simulates a Stack data structure, implementing the following two operations:

    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.

Time complexity

O(nlogn) for both operations.

Space complexity

O(n)

Return to Index