Count Subarrays With Fixed Bounds | Made Simple | Microsoft | Leetcode - 2444 | codestorywithMIK
HTML-код
- Опубликовано: 16 сен 2024
- This is the 7th Video of our Sliding Window Playlist.
In this video we will try to solve another very very good problem "Find the Index of the First Occurrence in a String". (Leetcode-2444)
Problem Name : Count Subarrays With Fixed Bounds
Company Tags : Microsoft
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
asked by meesho in today's OA
i have meesho OT today... what other questions they asked could you tell???
I would say THIS IS CRYSTAL CLEAR EXPLANATION !! 👌👌👌
LOVED the CULPRIT INDEX CONCEPT. Enjoyed AND learnt in one go. CREDIT : YOU
After understanding, I feel like I won't forget the solution .
Thank you so much for your contributionto the coding society.🙌🙌
Thank you so much 🙂
It was your day 2 of the streak,and now you are near at around 400 days on leetcode,great bro
just saw day2 and thought wtf, then saw the date od upload 😂 anyways great explanation man at first it looked like sliding window to me
Today I had seen many videos solution of this question but none of these are able to solve this problem in your way..
Your way of solving problem is totally different from others and I really love it and appreciate your work....❤
Indeed man.
yes
Thanks bhai, what a lovely explanation! Below is the Java code:
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long ans = 0;
int minKPosition = -1;
int maxKPosition = -1;
int culpritIndex = -1;
for(int i=0; i maxK) {
culpritIndex = i;
}
if(nums[i] == minK) {
minKPosition = i;
}
if(nums[i] == maxK) {
maxKPosition = i;
}
int smaller = Math.min(minKPosition, maxKPosition);
long temp = smaller - culpritIndex;
ans+= (temp
Thanks to you like always ❤️
@@codestorywithMIK ❤
this channel will boom in coming days out of nowhere
❤️🙌🙏
Very beautiful explanation. This channel going top
It means a lot ❤️❤️🙏🙏
Like Anurag also mentioned, I watched many videos on RUclips on this Qn.
But the explanation of this guy is way tooo good man. You are just too different bro. I don't know if you realise this , but you are really gifted. Keep it up.
sir itna hard question ko itna easy banadiya apne , god level explanaiton
Thank you so so much ❤️❤️❤️❤️
I come here daily after solving question to see how you solved and sometimes to grasp the idea. Good initiative, carry on.
bro just keep doing ur work.
i appreciate the hard work that u put in to give us a detailed solution. 😊😊
I saw multiple videos for this and referred discuss section of leetcode. This is by far the best explanation. Hats off
Feels illegal to get such quality content free of cost 😅❤️
😅
bhaiya your content is amazing keep it up
Awesome Explanation!!
Starting my day with your video great quality control brother ✨
great explaination, bhaiya!
You explained "what is the solution" really well. But you didn't explained, how to come up with this solution? What should be thought process behind this solution ?
yeah the intution is missing, these subarray problems are bi*ch
I agree with others that this is indeed a crystal clear explanation.
Excellent explanation. Thank you !
I am grateful for your help 🙌🙌
great explanation
You are so Good. Your Explanation is amazing man! MIK.. from today i will be your daily User!
I remember struggling with this question earlier. Such a nice explanation!
Thank you so much 🙏😇
Java Code for this solution is:
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long ans=0;
int min_k_pos=-1,max_k_pos=-1,culprit=-1;
for(int i=0;i
Thanks yaar
thank you for such a good explanation!!
you made my day
Thanks a lot bhaiya ❤❤ Got the Leetcode March badge all credit goes to you 😇😇❤❤
super duper explanation man. loved how you break things and make even Hard look simple.
Thank you 😊
Thanks man, What a consice approach and explanation.
Thanks a lot
please could you explain how you got the intuition for the smaller - culprit, which will give a valid subarray, and how you got to know that you have to take a smaller
great bhya , u made it look like it wasn't what it was.....
my entire hostel is preparing from your dp playlist...bcoz it is that amazing..
one request please add more variations to this playlist as well...
Wow. It means a lot.
Thank you so much.
Sure, more coming ❤️❤️❤️
This is what i understood:
class Solution {
public:
long long countSubarrays(vector& nums, int minK, int maxK) {
long long count = 0;
// Tracks the last index of an element equal to minK encountered so far
int lastMinIndex = -1;
// Tracks the last index of an element equal to maxK encountered so far
int lastMaxIndex = -1;
// This variable will be used to mark the beginning of a new subarray
// after encountering an element outside the range [minK, maxK]
int startAgain = -1;
for (int left = 0; left < nums.size(); ++left) {
// If the current element is outside the desired range
if (nums[left] < minK || nums[left] > maxK) {
// Reset the starting point for the next subarray
startAgain = left;
} else {
// Update lastMinIndex if the current element is equal to minK
if (nums[left] == minK) {
lastMinIndex = left;
}
// Update lastMaxIndex if the current element is equal to maxK
if (nums[left] == maxK) {
lastMaxIndex = left;
}
// Calculate the valid length of the current subarray
// considering both minK and maxK elements We use max(0, ...) to
// ensure we don't get a negative count (which wouldn't make
// sense) min(lastMinIndex, lastMaxIndex) - startAgain
// represents the number of valid elements in the subarray
count += max(0, min(lastMinIndex, lastMaxIndex) - startAgain);
}
}
return count;
}
};
Really good. Thanks!
Whenever i feel i get stuck in LC daily i always comes too your channel and boom magic happens everytime. Also need your help any medium through which i can talk to you as i tried topmate to get chance to talk with you but didn't find any meeting scheduling link. If possible provide any methods to talk to you personally.
Let me soon reopen my topmate. Currently i have been very occupied as I have been shifting to a different city.
Very very very nice explanation!👏😇
so helpful
Thank you so much 😇🙏
A great approach
Intuition:
1. As you move index i, Think how many valid subarrays are ending at this position.
2. Think what could be the shortest valid subarray (Subarray containing minK and maxK at the ends)
3. Also subarray till i (current index) and including the minK and maxK is also valid. So we only care subarray from leftmost valid index to current index i.
4. So to find leftmost we take min(minKPos,maxKPos).
5. So now we just need to think how far we can extend from leftmost valid index so that we count remaining subarrays that are still valid.
6. We can go left until we find an element that is out of bound (>maxk or
Bhaiya how one is supposed to think like that in an interview .....dimmag meh hi nhi aayega yeh toh :(
Very difficult if you haven't solved these types of problems.
same yrr
Hands down best explanation. And welcome back brother hopefully everything is good now.
You deserve more likes and subscribers.....
Means a lot ❤️
Amazing explanation
Feeling Happy that I got the approach.
But, feeling Sad for not getting this approach on my own.
Good Approach !!!
Bhaiya, here we are using culprit index to bring out our answer.
Say the array is 3,2,1,4,4,5,6 and minK = 1, maxK = 5
So, when i = 5, that is where we directly add 3 to our answer which is required of us
Now, what was the thought process behind using a culprit index, that too for evaluating the Ans?
Like, if we wanted to give INT_MIN to all values
Then, what would we do?
brilliant , Top G ! How did you come up with the approach?
Thanks a lot .
Just some dry run helped and also similar qns in past
Understood.
Below is the JavaScript solution:
var countSubarrays = function(nums, minK, maxK) {
let ans = 0;
let minKPosition = -1;
let maxKPosition = -1;
let culpritIndex = -1;
for(let i=0; i maxK) {
culpritIndex = i;
}
if(nums[i] == minK) {
minKPosition = i;
}
if(nums[i] == maxK) {
maxKPosition = i;
}
let smaller = Math.min(minKPosition, maxKPosition);
let temp = smaller - culpritIndex;
ans+= (temp
Tysm ❤️
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
minPos = -1
maxPos = -1
i = -1
res = 0
for j in range(len(nums)):
if nums[j]>maxK or nums[j]-1 and maxPos>-1:
res += min(minPos, maxPos)-i
return res
I used this to solve the question .. but anyway I think its same as the 'i' here is the culprit index.. but only thing we dnt need to care about getting a negative count here in case of a invalid subarray ..
i got this intuition after learning from you only .. thanks for all the awesome crystal clear explanations as always
please make a video on : Minimize Manhattan Distances , leetcode weekly contest 391 4th problem
This is lit 🔥
I think it is not possible to solve this problem without knowing this concept and you wont able to solve at first time if you won't solve such problem ever.
yeah, this approach is super clean but feels like you have to remember it, or else you can't solve this problem in the future.
Super hero
bhaiya kaise soch lete ho aise kaise story bana lete ho......... thank you!!!!!
Accha hain. Thanks bro
i got march badge bro because of your op explaination
i still don't understand the formula fully. But great explanation overall
Python code:
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
minIndex = maxIndex = culpritIndex = -1
ans = 0
for i in range(len(nums)):
if nums[i] == minK:
minIndex = i
if nums[i] == maxK:
maxIndex = i
if nums[i] < minK or nums[i] > maxK:
culpritIndex = i
ans += max(0,min(minIndex,maxIndex)-culpritIndex)
return ans
class Solution {
public:
long long countSubarrays(vector& nums, int mini, int maxi) {
int sz=nums.size();
long long ref=0 ;
long long cnt=-1;
auto k=[&](int h, int l){
queuemx;
queuemn;
for(int c=h;c
Explaination is good, but how to approach this type of question, what concept are you using, if you use new concept for every question, how will i tackle new question.
Yes, he explains it well, but he doesn't cover the intuition or the approach to solving this type of question. If the question changes a bit, someone who has only watched this video might not be able to solve it. Prefer Striver for DSA as he explains the intuition very well.
I could not understand the solution completely this is what I understood
//make subarrays with maxIndex and minIndex in it
//for example maxIndex = 2 and minIndex = 5
//now number of subarrays till index 5 cannot be calculated as j-i+1 ? as all the other possibilities my exclude maxIndex element which is on index 2
//simply we choose maxindex(smaller and on left of min Index) and find other subarrays on left of it till the culprit index is not found
Is it correct?
Outstanding explanation.
Sir, do you come to this approach of culprit index because in first attempt it might be difficult to get this.
Can you please explain why did you choose to take min of the maxKindex, minKindex? What is the idea behind this?
but why in both examples you considered the min element only at last index of array? It could have been in the middle or anywhere, and then we need to consider even the right part of array after that
How one can think for this approach?? This Approach is really amazing. But How can I develop my mind to think like this ??
this is the actual doubt I have anytime I have to watch his videos, how to build this approach?
@@atryshsharma773 this is a sliding window concept. Intution is nothing but pattern created by brain. The more you solve more easier it will become for your brain to come up with solutions like these.
bhai playlist looa trees recursion ke upr please
what if we had more than one culprit?
❤️
sri iska .... sliding window and queue ka use karke approach bata sakta hai ....
This solution cant be generated intuitively by me
Sir can u plz explain intuition behind the smallest index - culprit index
The number of subarrays possible will be the number of elements between the culprit and the first maxK/minK element including itself. SO the smallestIndex - culprit will give you that number only.
This is one of those problems where bhaiya ki approach samajne me dikkat aarhi hai. Anyone else?
not me. Ek do jagah rewind karke dekha, ek do dry run kara. ache se samajh agaya.
But tbh kaafi tough hai khud se aise approach soch paana. Unless the person has solved it before only then will be able to solve during interviews.
Then maybe it is me
bro can u solve one question of mine
Brute force would not work as it exceeds time limit
Please tell this one thing ki aapane story kaise banayiii i mean how u get this intuition?????
What is the intuition for this approach
Bhai yeh solution toh bohot zyaada acha hai, but yeh socha kaise? Intuition hi nahi aayi mujhe yeh sochne ki..
How can someone come with this solution, I am unable to get the institution.
Interview me ye approach mind me click bahut muskil hai 😥😥
bhiya code tak toh theek hai but there is no why i can come up with this :( and i would never learn the code
Hi there,
Actually it’s alright. In the beginning i could also not come up on my own. I practiced such qns.
So keep practising more and more. It will help a lot ❤️
did microsoft asked this for SDE 1 ?
Number of subarrays at index i ya at index j kitne honge ye kaise find karte hai sir ??? I mean formula and intuition ???
To calculate the number of subarrays from index i that “end at index j”, you can use the formula:
Number of subarrays = j - i + 1
This formula works because for any subarray starting at index i and ending at index j, there are (j - i + 1) elements in that subarray.
@@codestorywithMIK Thanks ❤❤
Attempt krke aata hu agar nhi hua to
Is this in English or not. If not why all the titles and comments are in English?
Because the question title on leeetcode is in english.
Bro aisa approach kasie aapke dimag mein aaya??