11 Greedy Algorithm Problems you must attempt
In this article, we have listed 11 important Coding Problems which is solved efficiently using Greedy Algorithms that you must practice for Coding Interviews.
Problem 1
Given an array of N integer, we have to maximize the sum of arr[i] * i, where i is the index of the element (i = 0, 1, 2, ..., N). We can rearrange the position of the integer in the array to maximize the sum.
- Time complexity of Brute Force Approach: O(N x N!)
- Time complexity of Greedy Algorithm: O(N logN)
Consider the following array:
arr[] = {2,5,3,4,0}
In this arrangement, the sum of products will be:
2 * 0 + 5 * 1 + 3 * 2 + 4 * 3 + 0 * 5
= 0 + 5 + 6 + 12 + 0
= 23
To maximize the sum we have to arrange the array as [0,2,3,4,5]
So the sum will be
0 * (0) + 2 * (1) + 3 * (2) + 4 * (3) + 5 * (4)
= 0 + 2 + 6 + 12 + 20
= 40
So, 40 is the maximum for the given array.
Problem 2
Given two arrays array_One[] and array_Two[] of same size N. We need to first rearrange the arrays such that the sum of the product of pairs( 1 element from each) is minimum. That is SUM (A[i] * B[i]) for all i is minimum.
- Time complexity of Brute Force Approach: O((N!)^2)
- Time complexity of Greedy Algorithm: O(N logN)
Consider the following two arrays:
array_one[] = {7,5,1,4};
array_two[] = {6,17,9,3};
If we arrange the array_one like {1,4,5,7} and array_two like {17,9,6,3}
Then the sum of products is: (17 * 1) + (9 * 4) + (6 * 5) + (7 * 3) = 17 + 36 + 30 + 21 = 104 which is the minimun sum of products.
The minimum sum of product is 104
Problem 3
Given an array of non-negative integers. Our task is to find minimum number of elements (subset) such that their sum should be greater than the sum of rest of the elements of the array.
- Time complexity of Brute Force Approach: O(2^N)
- Time complexity of Greedy Algorithm: O(N logN)
Example 1:
arr[] = {5,2,9,1}
output: 1
Explanation:
{8} is the subset which have sum greater then other elements sum.
Problem 4
For a given array of elements, we have to find the non-empty subset having the minimum product.
- Time complexity of Brute Force Approach: O(2^N)
- Time complexity of Greedy Algorithm: O(N)
Given an array { 1, -1, 2, 0, -10, -2}
The subset {1, -1, 2, -10, -2} will have the maximum product that is -40.
All other subsets will have product greater than -40.
Problem 5
For numbers from 1 to given n, we have to find the division of the elements into two groups having minimum absolute sum difference. We will explore two techniques:
- Time complexity of Brute Force Approach: O(2^N)
- Time complexity of Greedy Algorithm: O(N)
Problem 6
For a given array, find the largest lexicographic array which can be obtained from it after performing K consecutive swaps. Given two arrays A1 and A2, A1 is defined to be lexicographically larger than A2 if for the first i (from 0 to length of smaller array), element at index i is greater than element at index i of A2.
- Time complexity of Brute Force Approach: O(N!)
- Time complexity of Greedy Algorithm: O(N)
Consider the following array:
A1 = [1, 33, 44, 11, 2, 5]
A2 = [1, 39, 20, 1, 0, 4]
A2 is lexicographically larger than A1 as for index 1, 39 > 33.
A3 = [2, 99, 100]
A3 is lexicographically smaller than A1 and A2 as length of A3 is smaller than length of A1 and A2.
Problem 7
Given a number N, our task is to find the largest perfect cube that can be formed by deleting minimum digits (possibly 0) from the number. Any digit can be removed from the given number to reach the goal.
- Time complexity of Brute Force Approach: O(2^N)
- Time complexity of Greedy Algorithm: O(N^(1/3)log(N)log(N))
et N = 1205;
if we remove 0 from the above number we will get 125 as remaning number, which is cube root of 5(5 * 5 * 5 = 125).
Problem 8
Given a set of n activities with their start and finish times, we need to select maximum number of non-conflicting activities that can be performed by a single person, given that the person can handle only one activity at a time.
- Time complexity of Brute Force Approach: O(2^N)
- Time complexity of Greedy Algorithm: O(N logN)
Problem 9
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. The problem is to find a single Maximal Clique.
- Time complexity of Brute Force Approach: O(2^V)
- Time complexity of Greedy Algorithm: O(V^2)
Problem 10
Given a number N, the problem is to count the maximum number of composite numbers that sum up to N. First few composite numbers are 4, 6, 8, 9, 10, 12, 14, 15...
- Time complexity of Brute Force Approach: O(2^N)
- Time complexity of Greedy Algorithm: O(1)
N = 15 => 6 + 9
15 can be split into 6 + 9, so the output of 15 will be 2.
Problem 11
The problem we will solve is that given a number N, we need to find the minimum number of fibonacci numbers required that sums up to a given number N. Note a fibonacci number can be repeated.
- Time complexity of Brute Force Approach: O(N)
- Time complexity of Greedy Algorithm: O(log N)
Suppose you are given :
N = 14
so, the number of terms required would be 2, as 1+13, 8+5+1, 3+5+5+1 and many others can sum up to 14, but minimum number of terms required are 2.
With this, you must have a good practice of Greedy Algorithms.