×

Home Discussions Write at Opengenus IQ

×

Greedy Algorithms

Greedy algorithms are algorithms that follow the idea that the best possible path/ answer at all intermediate steps eventually results in the answer of the overall problem. This idea does not work for all problems but when it is applicable, it improves the time complexity greatly.

Greedy Algorithm vs Dynamic programming

In this article, we will discuss greedy methods vs dynamic programming. Both of them are used for optimization of a given problem. Optimization of a problem is finding the best solution from a set of solutions.

Greedy Algorithms

Fitting Shelves Problem [Greedy Algorithm]

In this article, we will understand what fitting shelves problem is and will see a greedy approach algorithm of solving this problem.

List of Mathematical Algorithms

Egyptian Fraction Problem [Greedy Algorithm]

In this article, we will explore the fascinating concept of Egyptian Fractions and will learn what they are and will also see an example of how they can be solved using greedy algorithm techniques.

Fractional Knapsack problem

In this article, we have explored fractional knapsack problem with examples. We have covered multiple approaches to solve this.

Jump Game II: Minimum number of jumps to last index

In this post, we will explore various ways to solve the minimum number of jumps to last index (Jump Game II) problem. In this, we will use ideas of Dynamic Programming and Greedy Algorithm.

Remove K digits to make smallest number

We will be solving the problem of removing K digits from a given number to form the smallest number possible without changing the order of the original number. We will use the idea of Monotonic Stack

Scheduling tasks to Minimize Lateness

In this article, we have explored techniques to schedule tasks (with a deadline and time required to complete it) in a way to decrease the time lag in finish time and deadline of the chosen request (i.e., lateness).

Smallest Missing Positive Integer

The problem is to find out the smallest missing positive integer given an unsorted integer array. We can solve this problem in linear time O(N) and in constant time O(1) using a greedy approach with hash map.

Find Maximum Perimeter of a Triangle

Given an array of integers, find which three elements form a non-degenerate triangle such that the triangle has maximum perimeter. This can be done using a Greedy algorithm by sorting the array of integers.

Make N numbers equal by incrementing N-1 numbers

Given an array, find the minimum number of operations to make all the array elements equal. The operation includes incrementing all but one element of the array by 1.

Split a number into K unique parts such that their GCD is maximum

The problem is to split a number N into K unique parts such that the sum of the parts is equal to N and the greatest common divisor of the K parts is maximum. This can be solved in O(N^1/2) time complexity using a greedy approach.

Largest Palindromic Number by Rearranging Digits

Given N (very large), we need to find the largest palindromic number by rearranging digits. If it is not possible to print the largest palindromic number from N then, print "Palindrome not found".

Smallest Palindrome greater than N using the same set of digits

We are given an number and we have to find the smallest pallindrome number greater than N which can be formed by using the same set of digits as in N. We have solved this using a Greedy approach in linear time.

Closest string such that no two consecutive characters are same

We are given a string and we have to find the closest string such that no two characters in the string are same. This problem can be solved using a simple greedy approach which will take linear time O(N) and constant space O(1).

Minimum number of Fibonacci terms with sum equal to a given number N

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

Find the largest number with given number of digits and sum of digits

In this problem, we need to find the largest number with a given number of digits N and given sum of digits say M. We will use a greedy algorithm to solve this is O(N) time complexity.

Find the smallest number with given number of digits and sum of digits

We are given two positive integers M and N. The task is to find the smallest number that has length M (number of digits) and sum of digits as N. We will solve this using a greedy approach in O(M)

Split N into maximum composite numbers

Given a number N, the problem is to count the maximum number of composite numbers that sum up to N. We solve this using a greedy algorithm in constant time

Maximize the sum of array[i]*i

Given an array of N integer, we have to maximize the sum of arr[i] * i. Brute force approach will take O(N*N!) time while greedy algorithm will take O(N log N) time

The smallest subset with sum greater than sum of all other elements

In this article, we explored a greedy algorithm to find the smallest subset with sum greater than sum of all other elements in O(N log N) time complexity

Find Minimum sum of product of two arrays

In this article, we explored a greedy algorithm to find the minimum sum of product of two arrays in O(N log N) time whereas the brute force approach takes O(N!^2) time

Find the Largest Cube formed by deleting minimum number of digits from a number

In this article, we find the Largest Cube formed by deleting minimum number of digits from a number using a greedy algorithm which takes O(N^(1/3)log(N)log(N)) time

Find the Largest lexicographic array with at most K consecutive swaps

For a given array, find the largest lexicographic array which can be obtained from it after performing at most K consecutive swaps.

Minimum Product Subset of an array

For a given array of elements, we have to find the non-empty subset having the minimum product. We will explore two techniques brute force O(2^N) and Greedy algorithm O(N)

Maximum Product Subset of an array

For a given array of elements, we have to find the non-empty subset having the maximum product. We will explore two techniques brute force O(2^N) and Greedy algorithm O(N)