Day 6 of 30 days of Data Structures and Algorithms and System Design Simplified — Greedy Technique
Welcome back peeps. Hope all’s well. In this post we will cover Greedy technique as follows —
What and Why Greedy technique(in 2–3 sentences)?
How does Greedy technique work?
Important Patterns and Techniques in Greedy technique Questions
Most Important Questions with Solutions
Tips and Techniques to solve Greedy technique Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Greedy Technique
Importance : High
Note : New Greedy technique questions with solutions will be added every day. So keep checking this post day.
Let’s dive in!
What is Greedy Technique?
Greedy algorithm is a technique or strategy which is used to find an optimal solution by making the sequence of choices that are best for the given moment.
It may or may not produce an optimal solution.
Greedy algorithm makes locally optimal choice at the given moment with the strategy that the selected choice will eventually lead to an overall optimal solution.
It consists of two elements —
Selection function — A function that tells which candidate element looks most promising.
Solution Function — A function that checks whether chosen set of elements provide the targeted solution or not.
To put it straight, greedy technique is all about always making the choice that looks to be the best at that moment.
Examples of Greedy Algorithm -
Dijkstra Shortest Path
Minimum Spanning Tree
Bellman Ford
Knapsack etc.
How does Greedy Technique work?
Greedy Strategy works in two steps —
1.Chose by being Greedy
Make locally optimal ( greedy) choice that leads to an optimal solution in the top down manner
2.Optimal Substructure
The optimal solution to the subproblem combined with the greedy choice made in step 1 will yield an optimal solution to the original problem.
Important Patterns and Techniques in Greedy Technique Questions
Greedy technique is applied to —
- Problems where you want to maximize/minimize something ( say profit/no of things/sum etc) in the given amount of time T.
- Problems where there’s some sort of priority/rank/score given to set of elements
Greedy solution may or may not be the most optimal solution.
Patterns → Questions like below belong to Greedy ( not limited to):
Largest Sum
Smallest Sum
Calculate Max/Min Profit
Min/Max Cost
Array Partition
Longest Palindrome/Sequence etc
Most Important Questions with Solutions
Note : New Greedy technique questions with solutions will be added every day. So keep checking this post day.
Golden rule is — Learn by doing/implementing
In this we will see most important Greedy technique questions.
Split Array Largest Sum
Question —
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
Return the minimized largest sum of the split.
A subarray is a contiguous part of the array.
Example:
Input: nums = [7,2,5,10,8], k = 2
Output: 18Solution :
Main Logic/Idea —
The main logic is to take the max sum of the array, divide the array ( using binary search) and keep shifting left and right pointers if the current Sum found is greater than max sum. Return the answer once the sum is minimized. Main thing one needs to do is to find the maximum no ( by being greedy) in the array and start from there.
Implementation —
def splitArray(self, nums: List[int], m: int) -> int:
def testSplit(maxm):
temp,currSum = 0,0
for no in nums:
currSum += no
if currSum > maxm:
temp += 1
currSum = no
return temp +1 <= m
left,right= max(nums),sum(nums)
ans = right
while left<=right:
mid = left + ((right - left)//2)
if testSplit(mid):
ans = mid
right = mid-1
else:
left = mid +1
return ansQuestion Link
Similar Pattern —
Subsequence of Size K With the Largest Even Sum
Maximum Total Beauty of the Gardens
Capacity To Ship Packages Within D Days
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Jump Game
Question —
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example :
Input: nums = [2,3,1,1,4]
Output: trueSolution :
Main Logic/Idea —
The main idea is to start the problem backwards ( i.e from the last element in the array) and keep shifting one element backwards while simultaneously calculating if you can reach the next element or not. Return true if you can else False.
Implementation —
def canJump(self, nums: List[int]) -> bool:
g = len(nums) -1
for i in range(len(nums)-1,-1,-1):
if i+nums[i] >=g:
g=i
return True if g ==0 else FalseQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Two City Scheduling
Question —
A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.
Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.
Example 1:
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110Solution :
Main Logic/Idea —
The main logic is to choose min cost in each set of the cost to fly a person from city A to city B.
Implementation —
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
diff, ans =[],0
for t1, t2 in costs:
diff.append([t2-t1,t1,t2])
diff.sort()
for i in range(len(diff)):
if i < len(diff) //2 :
ans += diff[i][2]
else:
ans += diff[i][1]
return ansQuestion Link
Similar Pattern —
Minimum Moves to Make Array Complementary
Count Number of Maximum Bitwise-OR Subsets
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Greedy technique questions with solutions will be added every day. So keep checking this post day.
Complexity Analysis
The time complexity of greedy algorithm/technique is O(m+n) and the space complexity being O(1).
Remember, the solution obtained after applying the greedy technique may or may not be the most optimal solution.
Tips and Techniques to solve Greedy Questions Fast.
Remember, in Greedy algorithm we make the choice top down — the choice that seems best at that moment , reduce the problem into subproblems and then solve the sub problems arising after the choice is made.
Follow these four steps —
- Start with optimal substructure of the problem
- Develop a recursive solution
- Pick optimal local choices ( greedy choices)
- Develop a recursive algorithm and later convert it into an iterative algorithm
Solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached.
That’s it for now. Day 7 : 1 D Dynamic Programming Technique coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
