Greedy Algorithms in Array

Greedy Algorithms in Array:

There is no. of problems related to the greedy algorithm in an Array. Let’s try to understand with a standard problem named

Activity Selection Problem:

Problem Statement: You are given starting time and ending time of ‘n’ number of activities and you have to perform maximum activities in that time of span. Considering that you can only do one activity at a time.

e.g. starting_time = [10, 15, 20]
Ending_time = [20, 25,20]

You can perform a maximum two activities. The set of activities can be done is [0, 2] (indexes in starting_time and Ending_time). Here, the greedy choice will be if to do that activity whose finishing time is least then the remaining activities and starting time is more than or equal to ending time of the last activity.

• The first step is to sort the array according to their ending time
• Select the first element of sorted array and display it
• Perform following step for rest of the elements present in the sorted array
• If the starting time of this element is greater or equal to the last the selected element then select this element and print it.

C++ Solution:

The complexity of this solution would be O(n) if the elements in an array are in sorted order and O (nlogn) if the array is unsorted.

Minimum absolute difference in array-

Problem statement: You are given an array of ‘n’ elements in it and you have to find the minimum absolute difference between any two elements in the array.

E.g. Suppose size of an array is 5 and arr [ ] = [ 2, 9, 0, 4, 5]

The output is 1 as 4 and 5 give the absolute difference of 1. Here, the important thing to note is you can also solve it by checking the difference of the first element with rest of elements then the Second element with rest of elements and so on which will bring this solution to the complexity of O(n²) which will not be a greedy approach. The greedy approach here will be if we sort the array and then see the difference.

Let’s see how:

After sorting the array it becomes arr [ ] = [0, 2, 4, 5, 9] and here as you can see that after sorting the array the difference between the first element and second element will be less than the rest of the elements and so on that’s why we don’t need to check one element with every other element which is the key here and it will bring the complexity of this solution to O(nlogn).

C++ Solution:

Weighted job scheduling-

Problem statement: You are given n jobs where every job is represented as:

• Start time
• Finish time
• Profit Associated

Find the maximum profit subset of jobs such that no two jobs in subset overlap. e.g.  Let no. of job n=4

Job details {Starting_time, finishing_time, Profit}
Job 1: {3, 10, 20}
Job 2: {1, 2, 50}
Job 3: {6, 19, 100}
Job 4: {2, 100, 200}

Then we will get maximum profit of 250 with choosing job 2 and job 4

The first thing to do here is to see if jobs are conflicting but first sort the array on the basis of finishing time and can see which latest non-conflicting job you could have done before in the array. Now there could be two more cases including the current job or excluding so what does it mean? It means you don’t include the current job then the answer could be last latest job you could have done and If you’re doing the current job then you must do this. Suppose you have an array sorted on the basis of finishing time.

Here you will have to iterate through a loop from j=i-1 to j>=0 and see if(arr [j].finish <= arr[i].start) then include in profit.

One thing to note here is it is a combined problem of DP (Dynamic Programming) and Greedy algorithm. Then after storing in another array maximum from both including the current job and excluding it.

C++ Solution:

Although there is no. of problems for Greedy algorithm in Array few of them are:-

• Maximum and minimum product subset of an array
• Maximise and minimise array sum after k-negotiations
• Minimum increment/decrement to make array non-increasing
• Sorting array with reverse around the middle
• The minimum sum of the product of two arrays
• Sun of Areas of Rectangles possible for an array
• Find if k bookings possible with given arrival and departures time
• Minimum sum by choosing a minimum of pairs from an array
• Minimise the sum of the product of two arrays with permutation allowed
• Maximise height pyramid from the given array of objects
• Partition into two subarrays of lengths k and (N – k) such that the difference of sums is maximum
• Minimum operations to make GCD of array a multiple of k

Must do Greedy problems for placement/Interview Purpose:-

• Activity Selection Problem
• Kruskal’s Minimum Spanning Tree Algorithm
• Dail’s Algorithm
• Fractional Knapsack Problem
• Graph colouring
• Connect n ropes with minimum cost
• Boruvka’s Algorithm
• Dijkstra’s Shortest Path Algorithm
• Prim’s MST for Adjacency List Representation
• Minimise Cash Flow among a given set of friends who have borrowed money from each other
• Find maximum sum possible equal to the sum of three stacks
• Find minimum time to finish all jobs with given constraints
• Greedy Algorithm to find the Minimum number of Coins
• K Centers Problem
• Dijkstra’s Algorithm for Adjacency List Representation
• Efficient Huffman Coding for Sorted Input
• Prim’s Minimum Spanning Tree Algorithm
• Job Sequencing Problem
• Minimum Number of Platforms Required for a Railway/Bus Station
• Huffman Coding

Want to read more about algorithms? Click here.

• Prims and Kruskal Algorithm

Frequently Asked Questions

What is the idea behind the name greedy algorithms?

The name greedy indicates that the algorithm chooses the best answer available at the time without taking repercussions into account. It is regarded as greedy since it chooses the best immediate output while ignoring the big picture.

Name some of the important greedy algorithms.

Dijkstra's Algorithm is a very famous greedy algorithm that builds the shortest distance between two nodes using a priority queue. Other than this, Fractional Knapsack problem, Minimum Spanning tree problems are also solved using greedy algorithms.

Is knapsack greedy?

One of the well-known and significant issues that falls under the greedy method is the knapsack problem. Especially, fractional knapsack problem can be solved using a simple greedy technique: Just pick the item with maximum fractional value.

Conclusion

In this blog we discussed the concept of Greedy algorithms and how to apply greedy algorithms in an array. We also gained an intuition of how to decide a greedy approach would be the solution. Futhermore, we discussed the activity selection problem, minimum absolute difference in an array, and weighted job scheduling problem statements.

To learn more, follow these links on our Coding Ninjas Studio platform:

• Design and Analysis of Algorithms
• Huffman Encoding
• Boruvka's Algorithm
• Data Structure
• Kadane's Algorithm
• C Programming

Recommended problems -

• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming and many more! If you wish to test your competency in coding, check out the mock test series and take part in the contests hosted on Coding Ninjas Studio! 

If you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problems such as Minimum Subset Sum Difference etc, interview experiences, and interview bundles.

Nevertheless, consider our paid courses to give your career an edge over others!

Happy Learning!