Maximum Sum Circular Subarray (Microsoft, Amazon) : Explanation ➕ Live Coding
Vložit
- čas přidán 28. 07. 2024
- This is our 33rd Video on our Array Playlist.
In this video we will try to solve a very very popular and good Qn "Maximum Sum Circular Subarray" (Leetcode-918)
This is a Hard Version of Kadane's Algorithm, but I will make it easy for you. Trust me, watch this video.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Maximum Sum Circular Subarray
Company Tags : Microsoft, Amazon
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/maximum...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
0:00 - Intro and Understanding Qn
2:10 - What is Kadane's Algorithm
3:21 - Brute Force
7:35 - Optimal Approach
18:30 - steps
20:05 - Revisiting Kadane's Algorithm
22:36 - Final Story
26:56 - Live Coding from Story
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
Small correction at 3:40
Answer for {5, -3, 5} will be 7
Got it
Why bhaiya it should be 10 only correct ? because if we rotate (5, 5, -3) maximum will be 10 right ?
sorry got it, I mistaked it with normal subarray sum
Respect++
Support++
Your videos are addictive
college walo nai ghanta kuch nhi padhaya kaden's
humne khud pdha hai aap jaise youtubers ki help se
❤️❤️❤️
Thanks for this awesome solution ..😇
Unbelievable explanation
I have gone to other videos but didn't understand this concept but your video is awesome and now I have no doubt about this, thank you so much bhayia.
Glad to hear that ❤️❤️😇😇
Really!! man at 8:00 time stamp my search for actual reason gets over. You are always truly amazing to highlight such important details.👍👍
Means a lot to me. Thank you so much 🙏😇
This is Art 🔥🔥🔥
As always awesome sir😍
Wow! Great explanation sir👏
Your explanation is awesome as always,
Thank you 😊
Thanks a lot Komal
Whoooaaa!!!!
Solid Explanation Brother 🔥
Thank you ❤️😇
nice explanation...thanks
Zabardastttt story building!!!!
Superb, very well explained 🔥
Thanks a lot
great video
awesome
Nyc explanation 💯
Thank you 🙏😇
Ohhhhh bhai ....great explanation 😮
Thanks a lot ❤️🙏😇
Bro make a video on time complexities and how to properly read the constraints mentioned in the question
Sure. Thanks for the suggestion
Added to my list
@@codestorywithMIK Bhaiyia Please make video on how to read constraints and understand that which tc solution will work
Excellent Sir!! just a small suggestion i would be beneficial to many students if you make videos on contests of leetcode,codechef and codeforces. Its true that your type of content is hard to make but it will influence more students towards better platforms. thank you so much for the videos
Thanks Yash.
I understand your point. A little difficult with so less time but yeah; i will soon be planning to include those you mentioned.
Slowly slowly will add more contents
You are love
So so good bhai..mujhe bhulna ni sb millions subscribers honge apke
Thanks 😊
Sure 💕
muje aapke charan chune ....aap itnaa achaa kese padhaaa sakteeeeeeee.
respect
Tried the same logic for almost 2 hours...everytime wrong answer on some cases...Then Finally video dekha and got the error ..Thanks for breaking it to easier subproblems.
❤️❤️❤️
I am so glad Sanjeeb that you tried on your own and gave it time. That’s how we learn. Keep it up
We can also do if (circular sum==0)return maxsum;
Else return max(maxsum,circularsum);
code of brute force
on submitting giving a tle
code :
class Solution {
public:
void rotate(vector&a,int n)
{int temp=a[0];
for(int i=0;i
Glad you tried brute force. It’s always a good practice to go for brute force
Hi! were you able to come up with this approach. As even I tried for so long but what did like running kadens algorithm only but having two pointer approach from front and back but it didn't work. As this was a bit biased problem,not so intuitive.? How to like start this approach, infact that rotate array then find maximum makes more sense!!!!
Hi there,
Actually i remember when I had solved this problem first time, I couldn’t come up with the exact same approach.
I think it’s fine to not being able to come up with such an amazing approach in one go. But once you get this, you can definitely think similar approaches in other similar problems.
@@codestorywithMIK 🙃 Btw explanation is top notch no doubt 👉👈
In [5,-3,5] this case 5+(-3)+5+5 can also be a subarray
Actually we can’t take any element twice. The 5 of index 0 is taken twice in “5+(-3)+5+5” which is not valid
Bhaiya topic tags mein Dynamic Programming aur Monotonic Queue q diya h? Usse bhi koi approach ho skta h kya?
haa sir, same question
Yes.
However i will cover them in separate play lists
@@codestorywithMIK ok bhaiya... Pressed the bell bell icon already ♥️
Tysm ❤️❤️❤️
@@codestorywithMIK ohk got it
Guruji
❤️🙏
support++
bhai aj ka leetcode ni ayega?
Being uploaded. Taking some time.
Stay tuned 😃
kadanes max
int sum = 0;
int maxi = INT_MIN;
for(int i=0; i
I guess
mini = min(mini, sum)
If (sum>0)
sum = 0
@@tauquirahmed1879 bro sum>0 fir to always negative me ayega
@@niteshk0487 yes you have to find the minimum know... Do it in two loops or take two sums, one to find minimum and one to find maximum. I am not sure it will work or not
@@niteshk0487
my solution works.
// code
class Solution {
public:
int maxSubarraySumCircular(vector& nums) {
int max_sum=INT_MIN, min_sum=INT_MAX, total_sum=0, circular_sum;
int n = nums.size();
int curr_max_sum = 0, curr_min_sum = 0;
for(int i = 0; i
Kadan's algo nhi karaye bhai
Bro Kadane's Algo se [5,-3,5] ka maxSum subarray 7 hoga na, 5 kaise??
Yeah 7 but his mistake
My bad. That’s a silly.
Thanks for pointing
@@codestorywithMIK Bro Highlight karne ke point se nhi bola bura math maan na. Mujhe5 minute tak smj nhi aaya tha ki hua kaise. That's it par ab smj gya.
No worries.
Thanks for your feedback 😇
Bhaya m algorithm kaha s or kaise pdu
I think for Algorithm, you can go through GfG . That’s good
But then make sure to solve Qns and apply algorithmic knowledge in them.
If you get stuck in problems, feel free to visit my channel for clear explanations
Kon kon s algorithm pdu?
I would suggest first start basic topics like
Array (it will have sorting algorithms, binary search etc)
Then further advancing, sliding window algo etc.
Basically, you need to choose a data structure to start with and then it will have certain different algorithms.
Bhaya I can solve graph,tree problem , this kadanes algorithm that you mentioned without knowing about it I solved finding maximum subarray in result making my own sadanes algorithm,I did some greedy problem also,some divide and conquer..
I wanted to ask that ki is there a structured method of learning just like the dsa or its random just learning algorithms when encountering those questions
Yes there is a structured way.
First you should have cleared all algorithms based on Arrays
Such as
Binary Search
Sliding Window
Kadanes Algo is also based on Arrays and so on
Why cant we just return directly "return max(circularMaxSum, maxSum);" instead of ??
if(maxSum > 0)
return max(circularMaxSum, maxSum);
return maxSum;
If you notice, I shared an example in my explanation : {-1,-1,-1}
In cases like these, you will return
wrong answer if you only do max(curcular, maxSum)
Try to dry run this small case
@@codestorywithMIK yes got it. So for handling all negative elements we are doing it right?
Indeed correct
@@codestorywithMIK thank you 💜
/**
* Sir Brute force se TLE araha h but able to 102 testcases out of 111
*/
class Solution {
private int kadane(int[] arr) {
int currSum = 0;
int n = arr.length;
int maxSum = Integer.MIN_VALUE;
for(int i = 0; i < n; i++) {
currSum += arr[i];
if (currSum > maxSum)
maxSum = currSum;
if (currSum < 0)
currSum = 0;
}
return maxSum;
}
private void rotate(int arr[], int n) {
int i, temp;
temp = arr[0];
for (i = 0; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[i] = temp;
}
public int maxSubarraySumCircular(int[] nums) {
int res = Integer.MIN_VALUE;
int n = nums.length;
for(int i = 0; i < n; i++) {
rotate(nums, n);
res = Math.max(res, kadane(nums));
}
return res;
}
}
Yes that’s expected because of the constraints.
But i am glad you tried brute force also, it’s a good thing to practice because it helps in interviews
//Brute force, got tle after passing 102/111 test cases😅😅
int kadane(vector &arr,int n){
int maxi = INT_MIN;
int sum = 0;
for(int i = 0;i
Good that you tried Brute force.
Great job
And i liked your rotation part 👍🏻
@@codestorywithMIK Thank you sir. Learning a lot from your channel❤
I think the interviewer may stress optimizing it in a single pass...
Yep you can simply write all in a single pass.
Click my code link in the description
Both codes are available
awesome
Thanks a lot ❤️❤️❤️