29/08/2024, 17:53 Askify | View Notes
Binary Search
Notes by:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
int arr[8] = {1, 2, 4, 5, 7, 8, 10, 12};
int value = 6;
// Define the range: index 2 to index 6
auto start = arr + 2;
auto end = arr + 6;
// Find the lower_bound in the specified range
auto it = std::lower_bound(start, end, value); ye yr lower and upper
bound mai confusion hoti hai lower bound matlab pehla aisa element
jo us number ke barabar ya bada ha and upper bound matlab upper
bound voh return karta hai jo strickly greater ho .
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 1/31
29/08/2024, 17:53 Askify | View Notes
searching in rotated sorted array isme mainly hme ye samjhna hai ki
aap values ka digram bana lo
toh samaj a jayga ki kisi bhi point pai ek part completely sorted hoga
and ek nahi
jo hoga uske based pai decision le paynge
15:23
ye uper wali approch ta work kar rahi hai jab apne without duplicate
elements hoga
idhar comarison mai dikat aygi agar duplicates present hue
05:10
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 2/31
29/08/2024, 17:53 Askify | View Notes
dekho fel sai samjho apna main kaam hai search space ko reduce
karn atoh iske liye ham ye kar rahe hai ki
jab a[l] == a[mid] == a[h] then we will move left pointer l++ right
toh h-- bcoz usse pehle ham compare kar chuke hoinge na ki mid ke
barabar nahi hai
09:52
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 3/31
29/08/2024, 17:53 Askify | View Notes
iska matlab jab duplicate element [present ho ya aise samaj lo ki
generral koi bhi question mai ye approch lagana
11:16
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
11:35
ye worst case time complexity hogi
min element in a rotated sorted array nikalna hai agar toh ye yaad
rakhn ki bhai
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
Minimum in Rotated Sorted Array
hmesha voh unsorted part mai hoga toh agar left sorted hai
l = m +1 ;
isme ans mai mini = min(mini,arr[l])
or agar right sorted hai toh
h = m -1 ;
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 4/31
29/08/2024, 17:53 Askify | View Notes
isme ans mai mini = min(mini,arr[m])
bs ek baad bahut imp hai iusme ki
[2,1] case pai dry run karlo samaj a jayga
Single Element in Sorted Array
mainly hme ye sochna tha isme ki kya aise prperty hai jiske based
mai elementaion karenge array mai
07:17
if i am standing at an index
and left and right same nahi matlab vohi ans hai
imagine
1122344
agar mera index even hai :
or left wala same nikalta hai toh right half mai hun
or right wala same nikalta hai left half mai hun
agar index odd hai :
left wala same toh left half
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 5/31
29/08/2024, 17:53 Askify | View Notes
right wala same toh right half
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
11:21
isko code karte yehi dikat a rahi thi coditions kafi sari thi toh ye sahi
way hai ki serch space ko left ++ right -- kar ke utn kar do baki edge
cases alag sai handle kar lo
https://leetcode.com/problems/single-element-in-a-sorted-array/
ye dekh lena code ek baar
Find Peak Element
isme voh V curve emgine karna agar single peak elemnet hai aise
assume kar ke
it will help in writing the code of elemenating the right or left half
and edge cases jaise uper handle kare waise karna
Ab main part ata hai ki multiple peak sainkaise deal karen
28:09
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 6/31
29/08/2024, 17:53 Askify | View Notes
agar mid decreasing slope pai ata hai toh kahin sai toh decrease kar
raha hoga matlab
ye sahi hai right wali peak ko ham nahi consider kar rahe but kisis
ko toh kar rahe hai
same for ham keh sakte hai ki agar ham right slope pai hai
30:37
ye case hai jika hme dhayan rakhna hai bs jab local minima mai a
jay
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 7/31
29/08/2024, 17:53 Askify | View Notes
toh bs ye add karna hai ki either go to the left or either to right no
matter
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
1) mid he peak a gya nahi
2) mid downward slope pai aya elemente right
3) mid upward mai aya elmeneate left
4) mid ab jahan aya voh hai local minima
kahi bhi chale jao
BS on ans we would know the range of our ans
so we would required to find min. or max ans from the given range
F F F T T T ye bhi yaad rakhna
Find the Nth root of an Integer
isme power exponentiation method use karenge
15:24
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 8/31
29/08/2024, 17:53 Askify | View Notes
usse time complexity log base 2 m aygi m is the power
isme problem ye thi ki number bahut bade ho sakte the isliye bhmne
jab bhi ans ko multiply karte gye or agar voh m sai bada a gaya toh
return kr diya ki not possible
20:01
dekho ek threshold de rakha hai
min max batana hai
feel aygi linear ki socho binary kaise improve kar sakti hai usi ko
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 9/31
29/08/2024, 17:53 Askify | View Notes
Kth Missing Positive Number
10:29
isme hona i +1 chahiye tha hai arr[i] toh missing kitne hue vahan tak
arr[i] - i -1
we are finidng the 5Th missing so we can say easily that it lies
between 7 and 11
ab jo missing number wala array hai uspe we can use binary serach
aise samjho ki tum ye ray pre compute nahi sath sath karoge
14:26
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 10/31
29/08/2024, 17:53 Askify | View Notes
ab isme 7 pai point karega phir uske baad vahan tak 3 missing the
toh total - 3 + jahan point kar raha hai
toh ans aya 9
13:20
pehle l wahan tha jisme kam tha and h wahan jisme jada
ab opposite polarity a gayi hai
17:30
Notes By:
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 11/31
29/08/2024, 17:53 Askify | View Notes
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
20:19
class Solution {
public:
int findKthPositive(vector<int>& arr, int k) {
int l = 0;
int h = arr.size() - 1;
while(l <= h)
{
int mid = l + (h-l)/2;
int missing = arr[mid] - (mid +1);
if( missing < k)
{
l = mid +1;
}
else{
h = mid -1;
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 12/31
29/08/2024, 17:53 Askify | View Notes
}
}
return l + k;
}
};
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
Aggressive Cow
Ab ek or pattern hai jisme hota hai min of max or max of min
toh yehi sochna ki isme binary search sai related hai
sort karna imp hai it helps in cleaning the input
02:11
jaise isme jo min distance between any two cows hai
usko maximise karna hai
arr[i] bata raha hai stall s ki postion
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 13/31
29/08/2024, 17:53 Askify | View Notes
03:13
ye sare possible distances hai
ab isme min hai 1 isko max karna hai hme
ab tuhme binary search lagani hai mi distance pai
voh hmesha consequtive cows mai he hoga
l=1
h = stalls[n-1]-stalls[0];
ab bs lagao mid dekho kya ye possible hai
ab jaise mid aya toh bs ek pointer statrting usko age badao or agar
kisi stall pai stall[i] - p >= mid
c++ p = stall[i]
ab bs c>=k
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
Allocate Books or Book Allocation
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 14/31
29/08/2024, 17:53 Askify | View Notes
yr isme main baat ye samjhni hai ki
likha loga MAX OF MIN ki max pages jo allocate kar sakte hai usko
min batana hai ki m person ko de payn
natural intution aygi ki agar mid ko limit man ke nikal lun kitno ko
de pa rahe hai let say voh ata hai c
if c >= m toh true bata do or isse kam karo mid or
ye galat hai bcoz idhar likha hai exactly m hone chahiye or agar aise
he hai uper wala toh usme phir kuch calculate na karna padhta sidha
ans hota jo max element hai but ye nahi
toh ham isme mid nikal ke dekhenege kitno ko allocate kar pa rahe
hai
return c <= m;
// m ko allocate karne hai agar m sai kam ko kar pa raha hun
// matalb mid bada hai capacity toh m ko kar paunga
// c > m a gya phir capacity uske hisab sai aygi kma ko more the
// m ko hoga yahab exact kaha tha
ab jo mid aya usko min karege matlab h = mid - 1
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
Minimize Max Distance to Gas Station
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 15/31
29/08/2024, 17:53 Askify | View Notes
09:06
jab bhi ans return hona hoga long double , ya double mai toh hme
hmesha ye line miilegi iska matlab hai we just need to compare till 6
decimal places
https://www.youtube.com/watch?v=kMSBvlZ-
_HA&list=PLgUwDviBIf0pMFMWuuvDNMAkoQFi-
h0ZF&index=21
ye dubara dekh lena
Median of two Sorted Arrays of Different Sizes
13:11
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 16/31
29/08/2024, 17:53 Askify | View Notes
ye optimised version hai memory optimisation
15:30
yr dekho isme ki jitne bhi ways hai to partition the array
voh ek he tarika hoga ki _ from array 1
and _ from array 2
11:39
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 17/31
29/08/2024, 17:53 Askify | View Notes
array cross mai sorted hai to make sure that
12:34
ye isliye valid hai bcoz 3 < 7 and 4 <6 hai
hence we can say all the elements on the left are smaller than all the
elements on the right
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 18/31
29/08/2024, 17:53 Askify | View Notes
16:26
18:10
21:36
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 19/31
29/08/2024, 17:53 Askify | View Notes
yehi hai 2 cases
24:03
26:09
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 20/31
29/08/2024, 17:53 Askify | View Notes
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
agar left wale do not exist ata hai then we take INTMIN and agar
right wala not exit ata hai then we take INTMAX
yr aise samaj ki left mai jitne element honge or right mai jitne honge
voh fixed hai
ab agar tu chite wale mai laga raha hai binary search or l1 > r2 a jata
hai matlab h = mod -1 karega kyunki chote pai jana hai
agar l2 > r1 ayga l2 karna decrease toh l1 increase
kyunki left mai element ka number same hona chhiye
26:41
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 21/31
29/08/2024, 17:53 Askify | View Notes
even
28:15
for odd case
K-th element of two sorted arrays
yr k ki value agar n1 sai jada hue toh ab uthe nahi le sakte na ek raay
sai isliye i am saying
min(k,n1)
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 22/31
29/08/2024, 17:53 Askify | View Notes
low = max(k-n2,0) ki agar n2 ke sare bhi include kar liye toh bhi k-
n2 toh lene he padhenge n1sai
ye uper wali problem ke tarah he hai just baat hai usme median ke
liye laga rahe the isme kth element ke liye laga rahe hai
10:55
Search in a 2D Matrix - I
05:22
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 23/31
29/08/2024, 17:53 Askify | View Notes
isme basically ham ye kar rahe hai ki rahe hai ki sare rows ko
traverse kar rahe hai but laga usme bs ek bar rahe hai
kyunki we would compare it with the two ends to know ki voh
element us row mai present hai ki nahi
ye time complexity hai O(n) + O(log m)
ab isko improve karne ke liye what we can do is
10:24
15:00
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 24/31
29/08/2024, 17:53 Askify | View Notes
09:49
11:21
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
O(N+M)
Find Peak Element-II
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 25/31
29/08/2024, 17:53 Askify | View Notes
dekho search space ko elemenate karne ki intutionna rahi hai we can
say it is bs
09:09
17:55
Time complexity
19:22
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 26/31
29/08/2024, 17:53 Askify | View Notes
Median in a Row Wise Sorted Matrix
ye row wise sorted array hai
06:03
agar brabar hota toh 7 sai. less than equal to 7 he hote but ab agar
repeat honge
09:57
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 27/31
29/08/2024, 17:53 Askify | View Notes
isme soch lo feel a jaygi main baat vohi hai jo just cgreater hoga
7 sai isme jaise 9 hai vohi hoga
(m*n)/2 sai
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
precomputation nahi karte ham bs ke saval mai kyunki bhai
agar precomputation he kar liya toh reh kya gaya O(n) ho jayga
16:42
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 28/31
29/08/2024, 17:53 Askify | View Notes
16:56
20:44
isme na concept of search spca elaga hai ki min value 1 and max is
1e9 ab jo median hoga voh in mai sal ksisi mai sai ek pai hoga
TC
21:37
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 29/31
29/08/2024, 17:53 Askify | View Notes
Notes By:
https://www.linkedin.com/in/ramanjot-singh-5b574422b/
Remove Ads from pdf and websites
Pricing
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 30/31
29/08/2024, 17:53 Askify | View Notes
Now you can use Askify in any websites
See How
https://askify.video/view/youtube?_source=youtube_extension&_action=download_pdf&_id=688c9c44-9a6d-45b0-bfd3-3238c0601412 31/31
