Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.o... Entire playlist: • Two Pointer and Slidin... Follow us on our other social media handles: linktr.ee/take...
@@himanshu_047 NO bro .. Im not from CS background so, my CS fundamentasl are not strong.. especially OSI, System design.. I was able to solve the current problem but messed up in system design problem.
Bhaiya mai abhi class 12 pass kiya haii aur abhi btech cse krne ka decide kiya hu and in jee mains meri 73 percentile bani aur abhi mai drop lu ya na lu ke doubt mw hu , ek point ye kehta hai ki college se zada skills matter krti hai agar tumhare pass skills hai to tumhari placement off campus bhi ho jayegi but ek taraf man me ye bhi hai ki kya ek baar try krna chhaiye , is taking a drop is worth it?
Hey bro , At the end of the day your skills matter more than any college bro. Yes , the top tier colleges will give you that early career boost but its you who has to push yourself. Irrespective of college , if you keep yourself pushing you can do it from any college. yes you will have more difficulties , but they will definitely teach you a good lesson bro... ALL THE BEST (And if you are confident that you can do better by taking drop, go for it. You are still young, don't think much about outside noise. At the end of the day Its you who has to feed your family. )
Just by watching & understanding the previous 4 videos, I was able to solve it on my own. First with brute then the sliding window technique. That's the magic of Striver😃❤
@@jimit2795 Look I am a noob myslef, but consider this, wherever we have to maintain something in terms of numbers like k distinct, at most k, you should know it is gonna be map. Here also we have two baskets i.e. we can store maximum of two types and we have to maximize the numbers of those 2 types of fruits. So at most K type questions. Hence map/set. That's all there's to it. Don't worry keep grinding. You'll get it.
I'm visiting this problem after a week (I solved this by watching striver's solution). I was not able to solve a single problem on my own thinking. I saw few comments stating that they were able to solve this by themselves and I was like "Am I doing something wrong. Why am I not able to solve on my own?" To my surprise, I completed the entire sliding window playlist and when I revisited after like a week, I'm able to solve every single sliding window problem in like 20 minutes. You deserve a huge salute, Striver!
I used to have the Same problem manhh. Thats Normal. Complete the whole series or half of the problems. then take a problem and try to solve the problem on paper and pen. For some it takes only 50 leetcode problems But for some it takes More than 200 . " Consistency is the Key". keep improving...
Actually the space complexity of the most optimal approach will be almost O(n) Coz just imagine all the elements are different then, the code will not care what's the size of the map, it will just keep adding elements in the map, howeven the maxlen will not be affected. Amazing lecture!!!!
Right!!! but suppose the array has half no. of elements as of type 1 and the rest of the array has different types(2,3,4,.....) then while trimming down the left side we will be adding different elements to the map. So instead of O(n), it can said to be near about O(maxlen ) or O(n/2) as at max we will be storing half of the elements. What do you say?
i think i solved it in better way : class Solution { public: int totalFruit(vector& fruits) { pairp1={-1,-1}; pairp2={-1,-1}; int l=0; int ans=-1; for(int i=0;i
(best solution without using map) int totalFruits(int N, vector &fruits) { int f = -1; // first fruit type int s = -1; // second fruit type int l = 0; // left pointer int r = 0; // right pointer int ans = 0; while (r < N) { if (f == -1 || fruits[r] == fruits[f]) { f = r; } else if (s == -1 || fruits[r] == fruits[s]) { s = r; } else { // When a new fruit type is encountered if (f < s) { l = f + 1; f = r; } else { l = s + 1; s = r; } } ans = max(ans, r - l + 1); r++; } return ans; }
I was unable to solve a single question in Sliding Window and two pointers after watching the above concepts I can think of and able to solve this question. This is the solution that I have solved on my own. def totalFruit(self, fruits: List[int]) -> int: maxlen=0 map={} i=0 for j in range(len(fruits)): map[fruits[j]]=map.get(fruits[j],0)+1 while len(map)>2: map[fruits[i]]-=1 if map[fruits[i]]==0: del map[fruits[i]] i+=1 if len(map)
28:58 I have a question bhaiya .. Let's take this example {1,2,1,2,1,2,1,2,3,4,5,6,7,8,9,10,11} .. if you see in case of optimal solution then SC=O(n/2) for map ... so how it is O(1) . And if you make an example of 10^5 length array the same as the upper example then also SC=O(10^5/2)..
I solved this question in 5-8 mins without even starting the window. All the consecutive type questions are so intuitive using sliding window. Used pq and map to solve it. int totalFruits(vector &arr) { unordered_map mp; int maxlength=0; int left=0; for(int right=0; right
In last solution, how is the space complexity O(1). Suppose there is a array with 200 elements, first 100 are 1 and 2 alternating. Rest 100 are 3, 4, 5, ............ While iterating my map will have only 2 elements till the 100th element of array, then other elements will be added and when at 198th element, I will have 100 elements in my map. That is definitely not constant
for optimal approach space complexity cant be O(1) right, because map can have more than 2 elements as well for this example {1,1,1,1,1,3,3,2,4,5,6,7,8,9} for the above example map can have almost n/2 elements correct me if im wrong
hey striver you make things so simple , some time i got jealous that some others also can know this method from this videos ........thanku again striver
Can anyone tell me why this is 'nt working int findMaxFruits(vector &arr, int n) { int left = 0, right = 0, maxLength = 0; unordered_map map; while (right < arr.size()) { map[arr[right]]++; if (map.size() > n) { map[arr[left]]--; if (map[arr[left]] == 0) { map.erase(arr[left]); } left++; } if(map.size()
If this is geeksforgeesks question the varibale n is the size of array. if questio says 2 basket then you need to use 2 instead of n the following will produce correct result: int totalFruits(int n, vector &arr) { int left = 0, right = 0, maxLength = 0; unordered_map map; while (right < n) { map[arr[right]]++; if (map.size() > 2) { map[arr[left]]--; if (map[arr[left]] == 0) { map.erase(arr[left]); } left++; } maxLength = max(maxLength, right - left + 1); right++; } return maxLength; }
A better method could be storing {value, last picked position} , since only two values would be there in the map pick the minimum of last picked position of the two, O(N) solution
after solving the previous question on my own and reading this one, i thought i could not be able to solve this one on my own but gave it a try and solved it on my own and that also in just o(n). quite happy today.
