Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What is a greedy algorithm?

Hafiza Farwa Mahmood

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

A greedy algorithm is an approach used to solve a problem by building an optimal solution. It chooses the optimal local solution hoping to make globally optimal results. The selection of locally available options may not lead to an optimal global solution. It uses a top-down approach to make decisions, which means earlier decisions can't be reconsidered.

Note: An algorithm is a set of finite instructions to perform any task. Want to know more about algorithms? Click here

Create a greedy algorithm

  • Find the subproblem of a given problem.
  • Determine the required solution—the shortest path.
  • Create an iterative base case that leads to the goal.

Working

Here's the animation of how the greedy approach works and makes decisions based on currently available resources.

1 of 7

When to use a greedy algorithm

Following are some cases where we can use a greedy algorithm:

  • The locally selected optimal solutions can build a global solution without changing earlier decisions.
  • The problem can be divided easily into sub-problems.

Applications

  • Prim's minimum spanning tree
  • Huffman coding
  • Knapsack problem
  • Job scheduling problem
  • Map coloring- graph
  • Traveling salesman problem and many others!

Limitations

  • Sometimes it may get stuck in the loop because it doesn't know about the next greedy choice.
  • It is unable to solve graphs with negative edges.
  • It's hard to prove why it is correct, so accuracy is unknown.
  • The locally optimal solutions may build a non-optimal global solution.

RELATED TAGS

CONTRIBUTOR

Hafiza Farwa Mahmood
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring