Greedy Algorithms

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).

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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".

Algorithms

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.

Algorithms

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).

Algorithms

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

Algorithms

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.

Algorithms

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)

Algorithms

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

Algorithms

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

Algorithms

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

Algorithms

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

Algorithms

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

Algorithms

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.

Algorithms

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)

Algorithms

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)

Algorithms

Greedy approach to find a single maximal clique in O(V^2) time complexity

There can be more than one single maximal clique in a non-complete graph (since complete graph is a maximal clique itself). To find a single maximal clique in a graph we use a straightforward greedy algorithm in O(V^2) time complexity

Algorithms

Divide numbers from 1 to n into two groups with minimum sum difference from O(2^N) to O(N)

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 Brute force which will take O(2^N) time complexity and Greedy algorithm which will take O(N) time complexity

Algorithms

Activity Selection Problem using Greedy algorithm

For activity selection, Dynamic Programming Approach takes O(n^3) time while Greedy Approach takes O(N) time when unsorted and O(n log n) when sorted. It follows Greedy approach as at every step, we make a choice that looks best at the moment to get the optimal solution of the complete problem

Algorithms

Graph Coloring Greedy Algorithm [O(V^2 + E) time complexity]

In this article, we have explored the greedy algorithm for graph colouring. graph coloring is a special case of graph labeling ; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

Graph Algorithms

Kruskal Minimum Spanning Tree Algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step