Shadowing Practice: Kth Smallest element in a matrix | Leetcode #378 - Learn English Speaking with Video

בחר מצב תרגול

כל מצב פותח חדר תרגול במסך מלא.

234 משפטים

אם המשפטים קצרים או ארוכים מדי, לחץ על ערוך כדי להתאים אותם.

Hello guys welcome back to TechDose

and in this video we will see the kth smallest element in a sorted matrix

which is from lead code number 378

and it is based on a searching algorithm let us now

look at the problem statement in this problem given an n by n matrix where each of the rows

and columns are sorted in ascending order return the kth smallest element in the matrix note

that they are asking about the kth smallest element in the sorted order

and not about the kth distinct element so you must find a solution

which has a memory complexity of better than order of n square

so let's take an example for better understanding in our case we are given a row wise

and column wise sorted matrix with non -decreasing order

and the matrix size is n by n our goal is

to find the k smallest element let's consider a one dimensional matrix it is not an n by n matrix

but i'm just giving you an example that

if you have a single dimensional array then in this case

if they are asking about the third smallest element then it will be two

and not three because they are not talking about the distinct element they are talking about even

if you have duplicates you can count them okay now

if you have an n by n matrix like we have

on the right hand side you see we have taken four

by four matrix every row is sorted in ascending order

and every column is also sorted in ascending order you see therefore in this case

if you have to find the kth smallest element

and let's find out the fourth smallest element what you can

do is you can convert these two dimensional matrix into one dimensional array

and simply get all the elements sorted

and you can find out the fourth smallest element

and in this case

if you enumerate everything in a non -decreasing order then the fourth element will be whatever fits at index 3

so that will be 2 in our case okay.

Now one technique can be to just flatten this entire matrix into a single dimensional array

and apply the sorting algorithm which will be n square log of n square

but a better technique could be to just push all the first elements into a heap

and then pop out the element which is the minimum out of this

and then push the next element of

that row this technique was already explained in the sliding window

maximum problem you can follow this the video link will be in the i button

or you can check out the description as well this can be solved using heap

and the time complexity will be n square log n

and the space complexity will be n square

but this is not the best approach in this case this

is just one of the approaches now in this case we can observe

that since we already know

that all the rows are sorted in non -decreasing order all

the columns are also sorted in non -decreasing order therefore whatever

will be our answer will be in the range of the smallest

and the largest one in this case the smallest one is 1

and the largest number is 11 so our answer cannot lie below 1

or beyond 11 right therefore the kth smallest element must be within the range of 1 to 11

and it must definitely be present in the matrix therefore what

we can do is we can search in our answer range okay we know the range of answer

so the minimum possible answer you can say this is lowest possible answer is 1 and the highest possible answer is 11. so

if we want to search in this answer range then one approach we can take is to take n pointers

and simply we can apply each of the pointer to the

first element just like we did in the heap previously it is a similar approach

but this is kind of a more simpler one in this

case you just compare all the n pointers like you can take p q r s

and you compare all these pointers p q r s

and see which one is smaller whichever is smaller you just have a counter

so you can have a count value c equals to zero now

when you skip this you move it to the right and the count will increase by 1.

Again, compare 2, 2, 5, 7.

Whichever is smaller, you just skip there.

You could have skipped the second 2 as well.

When two values are same, you can skip any one.

Now, the count of elements you have skipped is 2.

Now, let's say I was talking about the third smallest element.

Now, since you have skipped two elements, so out of these, whatever we are pointing, one of these will be the third smallest element

because two elements have already been skipped so

which one do you think will be the third smallest the

smallest of all these pqrs pointers right the smallest one will be the next one

which is skipped and if you find out the smallest it will be two okay

so the answer in this case will be equals to two this approach is also valid

and you see that for finding out each element like for skipping

which element do I need to skip you have to compare all the PQRS pointers.

so it is an n by n matrix

so there are n rows here right

so for each element skip you have to make n comparisons find out the minimum out of n elements

and you know that the highest k value can be the last one

which is n square itself therefore the time complexity in this case will be n square

which is the highest k value multiplied by for skipping each

element you need to do n comparisons therefore order of n cube will be the time complexity

but the space complexity will just be order of 1 okay

because we are not taking any extra space

so this is a simple approach not as good as the heap approach

but the heap approach used extra space in this case you

are optimizing space by taking more time to solve the same problem

so heap approach can be considered better since we already know

that all the rows and columns are already sorted therefore we also know

that our answer will be in the range of 1 to 11 on a sorted array

or on a sorted matrix we can always apply binary search.

So let's see how we can apply binary search in order to find the kth smallest element.

Let's say that our kth smallest element k value is equal to 3.

So we want to find the third smallest element.

So we already know the range of answer.

What is the lowest answer possible?

The lowest answer possible is one which is given by the top left corner.

The highest value which can be possible in the answer is the bottom right corner

which is 11 okay and we can say this since it is row wise column wise sorted

100

so we have to take a candidate so let's take the candidate as mid

101

which will be low plus high minus low by 2 this

102

is the technique i already told you in the binary partition how to do this

103

and why we do this

104

so the answer will be 1 plus 11 minus 1 by 2 which comes out to be 6.

105

So, let's try this out like this becomes the candidate

106

that what if I take 6 is this 6 the kth smallest element that is what I am trying to find.

107

So, in order to find

108

if 6 is the kth smallest element thus in the simple

109

approach what we could do is in every list we could

110

count how many elements are less than 6 less than equals to 6 you can say.

111

So, in the first row there are four such elements

112

which are less than equals to six in the second row three elements in the third row two elements

113

and in the fourth row there are no elements

114

which are less than equals to six

115

so total elements less than equals to six are four plus three plus two

116

which is nine six is kind of the ninth smallest element

117

but we are talking about the third smallest element right so

118

if it is the third smallest element

119

and six is actually the ninth smallest element then I should

120

decrease the number like I will definitely get a number lower

121

than 6 right therefore in order to decrease it my low value will remain the same

122

but my high value will be equals to the mid value

123

you will understand at the end like why I did not

124

make high equals to mid minus 1 there are multiple variations of binary search

125

and you have to adjust accordingly sometimes high will become equals

126

to mid minus 1 sometimes it will not be in this

127

case we should not take i equals to mid minus one by the end you will definitely understand

128

so let's just take it and let's see what will be the new mid value

129

that will be one plus six minus one by two

130

so this comes out to be three let's see how many elements are less than equals to three

131

now in the previous case we had applied i mean the simple linear search

132

which was again very time consuming

133

so what we should do is instead of applying like how

134

many elements are less than equals to three on a given row, we should do that by using binary search

135

and how many elements are less than equals to three can be counted

136

or the first index which is having a value greater than three can be given by upper bound.

137

So if you apply let's say upper bound of two on the first row, then it will stop at index three

138

because index three is the first index where the elements are

139

greater than two okay this is the first occurrence in this

140

row therefore for 6 as well we should have applied binary search so

141

if we apply binary search on 6 again then the upper

142

bound will stop at index 4 here the upper bound will

143

stop at index 3 here it will stop at index 2

144

and here it will stop at index 0

145

so you can add up all the indices 4 3 7 7 plus 2 9

146

so again the answer is same

147

but for applying binary search upper bound it takes order of log of the length of the single row right

148

so that is log of n now again we are applying the same for three

149

so for three the upper bound on the first row will

150

stop at index three the upper bound on the on the in on the second row

151

which is index one row will stop at one for this two it will stop at zero

152

and for three it will stop at zero so how many elements did we see we saw three plus one, which is four elements, right.

153

So, this is saying that this is the fourth smallest.

154

Okay, three is the fourth smallest probably.

155

Therefore, what we should do, we should search for a lower number.

156

Therefore, your L will be equals to one and your H will be equals to three.

157

In this case, let's take the mid value and this will be one plus three minus one by two, which will be equals to two.

158

Now let's find out the same for two.

159

So for two in the first row, we will stop at index three in the second row will stop at index one.

160

And here we will stop at index zero.

161

And here as well we will stop at index zero.

162

So for this as well, we got the count equals to four.

163

So definitely I will keep on searching.

164

Low will be one and high will be equals to two now.

165

So mid will be equals to low plus high by two or you can say low plus high minus low by two, which will be equals to 1.

166

Now for one, my search will stop here.

167

And for all the other rows, it will stop at index zero.

168

So here the count will be equals to one, which is less than the third smallest element, right.

169

So we should go on the right hand side.

170

So low will be mid plus one and low will be two, high will be two.

171

And as soon as low and high are same, we will stop there.

172

And whatever is the high value, we will return it as an answer, high value or low value whatever so in this case we can say

173

that 2 is the answer 2 is the third smallest element you can see

174

that if I had made high equals to mid minus 1 then in this step where

175

the high value was 3 and we had taken the mid as 2

176

and the 2's count had come out to be 4 in

177

this update for the next value the high value could have been made equals to 1

178

which is mid minus 1 right so that would not preserve the result

179

so i think

180

if you just do some dry runs you will yourself understand about should i update it to mid minus one

181

or should i update it to equals to mid

182

and the same can happen for multiple questions

183

when you update low sometimes it can be just low equals to mid

184

or sometimes it can become mid plus one

185

so it can vary depending on the type of question you are solving

186

so let's discuss about the time complexity how many times do

187

we need to do this binary search here like binary search on the range of answer right

188

so what can be the range of answer it will be

189

the maximum minus minimum you can take the mod of this this will be the given range of answer

190

and since we are doing binary search on the range

191

so it will be log of this

192

which we can write as log of r

193

which is the binary search on the range of numbers the

194

range will be equals to max minus mid okay now having

195

seen this for each of this binary search on the range

196

of answer we are applying binary search on all the rows how many rows are there n rows

197

and what is the size of each row the size of

198

each row is n therefore log of n operation is required to find upper bound on each row

199

and there are n rows therefore n log n time is

200

spent for each verification of I mean whenever you find a mid value you need to count how many

201

elements are less than equals to the given mid value right

202

so it will take n log n time on the entire matrix

203

and we are repeating it log r times therefore the time complexity will be n log n log r

204

which is very very less as compared to order of n square

205

and the space complexity is order of one

206

so this is one of the best approach for this problem

207

let's look at the code i would like to announce about our live training programs data structures

208

and algorithms which is interview dose and system design

209

which is design dose if you are looking for making a switch from service to product based

210

or even make a product base to product base top tier switch

211

and aiming for your dream company this is the best curriculum

212

you can ever join i'll be your mentor throughout the cohort

213

and i will help you clear all your doubts in the

214

one -on -one sessions you can know more about this by querying us on the whatsapp number

215

or you can also visit our website techdose .co .in in this code you are given a matrix and a value k.

216

So, you can simply find out how many rows are there.

217

And since it is an n by n matrix, you know how many rows and columns will be there at the end, find out the lowest possible value, which is the first top left corner and the highest possible value,

218

which is the bottom right corner.

219

And then we have taken a mid variable.

220

So, this is binary search on the range of answer and you can see how I have updated the high value,

221

right so if the count is less than k then I will update the low to mid plus one

222

and if it is higher than k then high will be equals to mid higher

223

or equal okay and this is the function for upper bound right

224

and you can like easily solve this you can read about

225

upper bound how it is done now what can be a

226

follow -up question here a follow -up question can be can

227

you implement the upper bound another follow -up question is why have you updated this high equals to mid

228

so you can give an example and

229

uh try to make him understand like whatever example i have given the same example you can give

230

and if you do high equals to mid minus one then my input will not give correct answer okay

231

so you can take this input

232

and try it out i hope you understood this approach please also practice the heap approach

233

which was explained in the sliding window maximum problem link will be in the description below like

234

and share our video and subscribe to our channel in order to watch Watch more of this programming video, see you guys in the next video, thank you.

הורד אפליקציה

כל מה שאתה צריך כדי לדבר בשטף

הגיית AIציון לכל משפט

תרגול IPAשלוט בכל צליל

אוצר מיליםבנה את מאגר המילים שלך

משחק אוצר מיליםלמד תוך כדי משחק

סרוק QR

Download on theApp Store Get it onGoogle Play

FOR YOU

המלץ על סרטון

13 משפטים

Merge sort in 3 minutes

Daily ConversationUniversity Students

575 משפטים

Lec-6 Simplex Method | Maximization Problem | Mathematical Example Solution | Operations Research

Daily ConversationUniversity Students

68 משפטים

Vanishing & Exploding Gradient explained | A problem resulting from backpropagation

Daily ConversationUniversity Students

108 משפטים

Cắt bánh - bài toán gây đau đầu nhiều thế kỷ

Daily ConversationUniversity StudentsWorking Adults

34 משפטים

How to Work SMARTER Not HARDER in 2 Minutes

Daily ConversationUniversity Students

799 משפטים

Cell Biology | Cell Structure & Function

Daily ConversationUniversity Students

419 משפטים

Minimum Window Substring - Airbnb Interview Question - Leetcode 76

Daily ConversationUniversity Students

אוצר מילים והערות הגייה לשיעור הזה

שיעור הדיבור הזה ברמה C1 מבוסס על הסרטון “Kth Smallest element in a matrix”. המילים שחוזרות הכי הרבה: element, equal, row, smallest, mid. בסרטון הזה יש 234 משפטים ו-2984 מילים לתרגול Shadowing. הדיבור נמשך 15:30. הדובר מדבר מהר, כ-192 מילים בדקה, אז צפו לצלילים מחוברים ומקוצרים. 85% מהמילים נמצאות בין 3,000 המילים הנפוצות ביותר באנגלית; כדאי ללמוד את השאר לפני שמתחילים.

אוצר מילים מרכזי בסרטון הזה

12 המילים המתקדמות ביותר בסרטון, עם ההגייה והמשמעות שלהן:

מילה	הגייה	משמעות
minus	/ˈmaɪ.nəs/	פחות, מינוס
complexity שם עצם	/kəmˈplɛk.sɪ.ti/	מורכבות
ascend פועל	/əˈsɛnd/	עלה
algorithm שם עצם	/ˈælɡəɹɪðm̩/	אַלגוֹרִיתְם
ninth שם תואר	/naɪnθ/	תשיעי
verification שם עצם	/ˌvɛ.ɹə.fɪˈkeɪ.ʃən/	וידוא
occurrence שם עצם	/əˈkɜɹ.əns/	מקרה
cube שם עצם	/kjub/	קובייה, קֻבִּיָּה
consume פועל	/kənˈsum/	צרך
mentor שם עצם	/ˈmɛn.tɔː/	מַנְחֶה, חוֹנֵךְ
subscribe פועל	/səbˈskɹaɪb/	נִמְנָה
adjust פועל	/əˈd͡ʒʌst/	כוונן, התאים

Phrasal verbs שתשמעו

מילה	משמעות
check out פועל	בדק

דקדוק בסרטון הזה

המבנים שהדובר משתמש בהם הכי הרבה, עם המילים המדויקות מהסרטון:

מבנה	בסרטון
סביל (Passive voice) be + past participle — הדגש הוא על מה שקורה, לא על מי שעושה את הפעולה	is based · are sorted · are given
משפטי זיקה (Relative clauses) who / which + clause — מידע נוסף על אדם או דבר	algorithm which will · element which is · one which is
הווה מושלם (Present perfect) have/has + past participle — פעולה שקרתה בעבר ועדיין יש לה חשיבות או השפעה עכשיו	have taken · have skipped · have already been skipped

הגייה ששווה לשים לב אליה

הצלילים של “th”: algorithm /ˈælɡəɹɪðm̩/, ninth /naɪnθ/
הצלילים של “sh” ו-“zh”: dimensional /daɪˈmɛn.ʃə.nəl/, partition /pɑɹˈtɪ.ʃən/, verification /ˌvɛ.ɹə.fɪˈkeɪ.ʃən/, variation /ˌvɛəɹiˈeɪʃn̩/
מילים ארוכות — שימו לב להטעמה: complexity /kəmˈplɛk.sɪ.ti/, dimensional /daɪˈmɛn.ʃə.nəl/, enumerate /ɪˈn(j)u.məˌɹeɪt/, verification /ˌvɛ.ɹə.fɪˈkeɪ.ʃən/, accordingly /əˈkɔɹ.dɪŋ.li/

צלילים שדוברי עברית מתקשים בהם:

/w/ — שפתיים מעוגלות, לא /v/: whichever /wɪt͡ʃˈɛvɚ/, query /ˈkwɪɹ.i/
/æ/ — פתוח יותר מה-“אֶ” העברית, לא כמו “a” ב-“cup”: algorithm /ˈælɡəɹɪðm̩/, flatten /ˈflæ.tən/
/r/ — הלשון לא נוגעת בשום מקום, לא ה-“ר” הגרונית: matrix /ˈmeɪ.tɹɪks/, binary /ˈbaɪ.nə.ɹi/, pointer /ˈpɔɪn.təɹ/, algorithm /ˈælɡəɹɪðm̩/, cohort /ˈkoʊ̯ˌhɔɹt/

איך לתרגל עם הסרטון הזה

הקשיבו לכל הסרטון פעם אחת בלי לדבר, ורשמו את המילים שאתם לא מכירים.
התחילו במהירות 0.75×, תרגלו Shadowing משפט אחר משפט, וחזרו למהירות רגילה כשזה מרגיש קל.
הקליטו את עצמכם והשוו למקור, תוך תשומת לב למילים כמו minus, complexity, ascend.

מהי טכניקת השאדואינג?

שאדואינג היא טכניקת למידת שפה מבוססת מדע שפותחה במקור להכשרת מתורגמנים מקצועיים ופופולרית על ידי הפוליגלוט ד"ר אלכסנדר ארגואלס. השיטה פשוטה אך עוצמתית: אתה מקשיב לאודיו באנגלית ילידית וחוזר עליו בקול רם מיד — כמו צל העוקב אחרי הדובר עם עיכוב של 1–2 שניות בלבד. בניגוד להאזנה פסיבית או תרגילי דקדוק, שאדואינג מכריח את המוח והשרירים בפה לעבד ולשחזר דפוסי דיבור אמיתיים בו זמנית. מחקרים מראים שזה משפר משמעותית את דיוק ההגייה, האינטונציה, הקצב, הדיבור המחובר, הבנת השמיעה ושטף הדיבור — מה שהופך אותו לאחת השיטות היעילות ביותר להכנה לIELTS Speaking ולתקשורת באנגלית בעולם האמיתי.

טכניקת Shadowing: קרא את המדריך המלא שלב אחר שלב →

Shadowing Practice: Kth Smallest element in a matrix | Leetcode #378 - Learn English Speaking with Video

בחר מצב תרגול

הורד אפליקציה

Merge sort in 3 minutes

Lec-6 Simplex Method | Maximization Problem | Mathematical Example Solution | Operations Research

what is a database index?

Two Sum - Leetcode 1 - HashMap - Python

Sequential, Multiple Assignment, Randomized Trial Designs With Dr Kidwell

Stack Data Structure In STL | C++ Tutorial

Making a 360° Controller Smaller than a Penny!

Vanishing & Exploding Gradient explained | A problem resulting from backpropagation

Cắt bánh - bài toán gây đau đầu nhiều thế kỷ

How to Work SMARTER Not HARDER in 2 Minutes

Cell Biology | Cell Structure & Function

Minimum Window Substring - Airbnb Interview Question - Leetcode 76

אוצר מילים והערות הגייה לשיעור הזה

אוצר מילים מרכזי בסרטון הזה

Phrasal verbs שתשמעו

דקדוק בסרטון הזה

הגייה ששווה לשים לב אליה

איך לתרגל עם הסרטון הזה

מהי טכניקת השאדואינג?