• 2 days ago
Transcript
00:00The next question which we will talk about is Pairsum2
00:03Pairsum2 and Pairsum1 is a little updated and advanced version
00:07I have the array list sorted and rotated
00:12We have talked about sorted and rotated arrays
00:16We used to talk about pivot
00:19What was the pivot?
00:20It is the element where the rotation is
00:21If I talk about this array list
00:25What is happening here?
00:26The pivot point of rotation is 10
00:31The original array list was 6, 8, 9, 10, 11, 15
00:37The rotation is here
00:39What did these values come from here?
00:42What was it completely sorted?
00:44This part is completely sorted
00:46This part is completely sorted
00:48But this part has been sitting
00:50It is 11 and 15
00:52After that, it is 6, 8, 9 and 10
00:55So my array list sorted and rotated
00:59Now I have a target sum here
01:01And I have to find out what a pair exists in this sorted and rotated array list
01:05Which sum is equal to my target sum
01:08First of all, we will do the same thing
01:10First of all, we will do brute force approach
01:13What?
01:13Brute force approach will be the same code
01:15That we have written in the pair sum
01:33But here, we will talk about the optimized approach
01:51We will use the same thing
01:52In the optimized approach
01:52We will use the same thing
01:54Our two-pointer approach
01:56Just this time
01:58The two-pointer approach will be a small twist
01:59A small twist
02:01How will it happen?
02:02First of all, I will find out
02:05Find out my pivot point
02:08Pivot point is that point
02:10Where my array is rotated
02:15I don't talk about that point
02:17Where the array is rotated
02:18I don't talk about that point
02:19I don't talk about that point
02:19I don't talk about that point
02:20Here, pivot means
02:22Basically my breaking point
02:25Where my sorted array is broken
02:29Sorted array is broken
02:31What is the sorted array?
02:34If I assume that I have sorted array in ascending order
02:37So what can I say
02:38In an ascending order
02:39In an ascending order
02:39Sorted array
02:40Or sorted array
02:42List
02:42In that list
02:44If I remove the i-th index
02:46Position value
02:47It will always be reduced
02:49As compared to my i-th index
02:52I mean
02:53If I have sorted list
02:551, 2, 3, 4, 5, and 6
02:57What can I say
02:58Every i-th index
02:59Value
03:00From i-th index
03:02Value
03:04So this 3 will be less than 4
03:06This 5 will be less than 6
03:08So this way
03:08Values are running
03:09When will the breaking point
03:11When will the breaking point
03:12Or pivot point
03:13Will my array list
03:14Come on
03:15When this condition
03:15Satisfied
03:16If I talk about this array list
03:20Here
03:21I write the elements
03:2311, 15, 6, 8, 9, and 10
03:27What will the breaking point
03:28Will I say
03:2911 is less than 5
03:30So here it is satisfied
03:336 is less than 8
03:34Here it is satisfied
03:35For 6
03:36For 6
03:36For 8 is less than 9
03:38For 8 it is satisfied
03:39For 9 is less than 10
03:41For 9 it is satisfied
03:43What is the next one
03:44What is the next one
03:44What is the next one
03:45Because there is nothing more
03:46So there is no comparison
03:47Where does it not satisfy
03:49It is not satisfied
03:50Here it is not satisfied
03:51Meaning
03:52I can say
03:53It is not satisfied
03:55For 15
03:56Why does it not satisfy
03:56For 15 it is not satisfied
03:57Because if it is sorted
03:58As a ascending order
03:59If it is sorted
04:00To be sorted
04:01To be sorted
04:01To be sorted
04:02To be sorted
04:13To be sorted
04:17To be sorted
04:30To be sorted
04:33To be sorted
04:33To be sorted
04:35Like I gave
04:361, 2, 3, 4, 5, 6
04:39To be sorted
04:40To be sorted
04:40In sorted list
04:40In the sorted list
04:40My left pointer
04:42It is initialized
04:45My right pointer
04:46It is initialized
04:48My right pointer
04:48It is initialized
04:49It is initialized
04:50On this logic
04:50To be sorted
04:52I will run
04:53So I will do the same
04:54Here
04:55The left pointer
04:56I will take the smallest
04:57element
04:58Which will be
04:59This element
05:00Here my left pointer
05:01will start
05:02Here my right pointer
05:03I will take the largest
05:05Here my right pointer
05:08will start
05:08Here my right pointer
05:08will start
05:08And
05:09I was working
05:10To move the pointers
05:12This time
05:13What was the work
05:13Before
05:15Left pointer
05:15Plus
05:16And
05:16Right pointer
05:19But
05:20What will happen
05:20This time
05:22This time
05:22My left pointer
05:23increases
05:24Because
05:25There was also
05:25And
05:26The right pointer
05:28increases
05:29So it will start
05:29Up to the back
05:31If we think
05:32It has reached here
05:33So it will start
05:33Rotate
05:34And
05:36If I talk about
05:37The left pointer
05:37It will start
05:38In the direction
05:38And
05:39It will start
05:41Rotating
05:42This way
05:44We are going to implement
05:46The logic
05:46In the two pointer
05:46The logic is the same
05:47The left pointer
05:49The right pointer
05:49Will initialize
05:50The right pointer
05:50Will initialize
05:51The right pointer
05:51Will initialize
05:52Now
05:52Smallest
05:53And
05:53Largest
05:54To find out
05:56I have
05:56Breaking point
05:57Find out
05:58If I have
06:00Breaking point
06:01Which is
06:01This point
06:02This
06:03Is
06:04Index
06:04Is
06:05I
06:05So
06:06My
06:07I
06:08Is
06:09My
06:09Largest
06:09To
06:11I
06:11I
06:11Can
06:13I
06:13I
06:13I
06:14I
06:14I
06:16I hope
06:28To
06:29So
06:29To find out
06:29Where
06:30To find out
06:30My left pointer
06:31Will come to your right pointer
06:32To
06:32To find out
06:34The left pointer
06:34I initialized
06:35Smallest
06:35Smallest
06:36I
06:36I
06:37I
06:37the right pointer initialized with the largest means i
06:40here comes my first thing
06:43that my left pointer will be equal to
06:47if this pivot point is i
06:48left pointer is equal to i plus 1
06:51and my right pointer is equal to i
06:53what do I need to do another thing?
06:56I have to run a loop
06:56which will run the same loop
06:58which I had run in the previous question
07:00i mean how to run the two pointer approach
07:03how to run the loop while my left pointer is not equal to my right pointer
07:07i mean when both values are not the same
07:09then i have to run a loop
07:11within the loop i want
07:13what i want
07:14if my left pointer is here
07:19and here is the right pointer
07:21i want to increase it back
07:24and after that
07:25it will come here
07:27and my left pointer
07:28it will increase it back
07:31then it will increase it back
07:32then it will increase it back
07:34i expect both of these rotated
07:37i expect to do this
07:38i expect to do this
07:39that both will travel the distance
07:40that will be my total distance
07:41i mean in linear time
07:44but how do we travel in rotation?
07:47i used to do simple rp minus minus
07:50lp plus plus
07:51i used to do increment and decrease
07:53but this time i used to increase and decrease
07:56logic
07:57so here i will use a special thing
08:00which is known as
08:02modular arithmetic
08:06math
08:07this is an advanced branch
08:09my mod function
08:12which is basically this
08:13it has many properties
08:15and these properties
08:16have very special algorithms
08:18we have many logic
08:20which we are seeing with advanced data structures
08:23these are mod properties
08:25these are really good properties
08:27and if you want to do competitive programming
08:29then with the modulo properties
08:31or how these properties
08:33are used in terms of coding
08:34we need to study
08:36if we have time
08:37then
08:37other than here
08:39we will use the rotation
08:40i will also use modular arithmetic
08:44or some of the modulo properties
08:46i will use some of the modulo properties
08:48after using the modulo properties
08:49there is a rule
08:51what is the rule?
08:51the rule is that
08:52if i in the rotated fashion
08:55i mean
08:56i will increase
08:57the left pointer
08:57one more and the left pointer
09:00will increase
09:01and increase
09:02the right pointer
09:03one more and the left pointer
09:04is increase
09:04but the left pointer
09:05will increase
09:05the same way
09:06and the other way
09:07i will increase
09:08this logic
09:09if i have to implement
09:09So what was my updation first? Left pointer was simply plus plus but this time left pointer will become equal
09:18to left pointer plus 1 mod n
09:20This n is my list.size
09:26This time I have to use this formula for updation
09:29The other formula will be right pointer
09:31What happened first? Simply right pointer would be minus minus
09:34This time what will happen? n plus right pointer minus 1 mod n
09:39This time my updation will remain the same
09:42I will analyze the case 1 that the target is equal to the sum
09:47Then my case 2 will be changed and my case 3
09:50But this time the updation will change
09:53Before I wrote LP++
09:54This time I have to write this and in the right pointer case I have to write this
09:59The rest of the code will be the same
10:01So in the 2 pointer approach
10:03I have to write the special things
10:05The most special things that I have to take
10:07And always remember
10:09For a sorted and rotated array
10:11It is that we use the modular arithmetic
10:15And the modular arithmetic rules
10:17Tell me this thing
10:19Now let's see this thing
10:20A little dry run
10:23How do I do dry run?
10:25How do I do?
10:26Let's assume that I have the target
10:27That is equal to 16
10:29I am going to dry run on this
10:31The first step will be for me
10:33That I will find out my pivot
10:34The pivot is for me
10:36I is equal to 1
10:36I mean here my array list
10:38My sorted list is break
10:41So what can I say?
10:43My left pointer will become i plus 1
10:45Which is equal to 2
10:46And my right pointer will become 1
10:48Which is equal to i
10:49This is i plus 1
10:50And this is i
10:54So I will initialize them
10:55Here is my right pointer
10:59Here is my left pointer
11:01Here is my left pointer
11:01Now let's check the condition
11:03Is 15 plus 6 is equal to 16?
11:06No, 15 plus 6 is equal to 21
11:08So this value is clearly greater than my target
11:13What will be done?
11:14I want to run case 3
11:14I want to run case 3
11:16In this case 3
11:18What will be done?
11:19What will happen?
11:19The right pointer will be I will act
11:21There will be a value of n
11:21Which is equal if i need for n?
11:23Two, three, four, five, six
11:24This is equal to n
11:25This is equal to n
11:27Since this value is 6
11:27I will appear to be 6
11:27Plus the right pointer value of 1
11:29Minus 1
11:30I will take it with the morgue
11:32So this will be equal to 0
11:35So this will be equal to 0
11:361 with 1 cancels
11:386 with 6 remainder 0
11:40So what happened?
11:41Right pointer value is 0
11:43I have seen right pointer value 0
11:45Where is right pointer?
11:47So my right pointer is back
11:50I will delete this
11:54Right pointer value is 0
11:58Now I will compare again
12:0011 and 6
12:02This sum is equal to target
12:0411 plus 6 is equal to 17
12:06It is not equal to 16
12:08Now this is 17
12:09This is greater than my target
12:11So I have to run case 3 again
12:13When my value is growing
12:14So I will run in case 3
12:15I will update my right pointer
12:20How will the right pointer update?
12:226 plus my right pointer value which is 0
12:26Minus 1
12:28Modulo 6
12:29Now this will be 5 modulo 6
12:31I will say that 5 modulo 6 is equal to 5
12:34Because 5 is the small and 6
12:36Reminder 5 will come
12:37So this value is
12:39Index 5
12:40Where does it exist?
12:41Index 5 is this in my list
12:43So what will it do?
12:44It will be removed from here
12:47It will be rotated
12:48To my last index
12:51And here will be my right pointer
12:53Now we will compare again
12:56Now we will compare again
12:57What is the value of 6 plus 10
13:00The value of my target is equal to
13:026 plus 10 is equal to 16
13:0316 is equal to target
13:05And here will return
13:06And here will return
13:07True
13:07So this will be my case 1
13:09In which I have true return
13:10So this will be my case 1
13:12So these are the cases
13:13We have seen
13:13Modular arithmetic formula
13:16What will happen?
13:17My right pointer will rotate
13:19And my left pointer will rotate
13:22And my left pointer will rotate
13:23When we use the modulo
13:26When I have a fixed size
13:28When I have a fixed size
13:28And outside the boundary
13:29If you want to increase value
13:31If you want to increase value
13:33But I need rotation
13:34I will increase value
13:36But I will increase in rotation
13:38Then I will use the modulo
13:40So that every time
13:41The value of n
13:43Bring only of n
13:43So logically
13:44I will not extend
13:45how much of the number
13:47So I will remove the remainder
13:50And the remainder
13:52Then the remainder
13:52You will put the remainder
13:52From 0 to n
13:53– 1
13:54To the range
13:55This is the basic property of math
13:57The basic property of math
13:59The basic property of math
13:59it says that you can take
13:59Which much of the x
14:01If you will remove x
14:02The remainder
14:03From n
14:03Then it will remainder
14:04From 0 to n – 1
14:06To the range
14:07Why ?
14:08Because n
14:08If n is bigger
14:09It will divide
14:12So the remainder will always exist between 0 and n-1
14:15What do I want to do in rotation?
14:17That my index will always stay between 0 and n-1
14:21Because I want to do that the left pointer
14:24It always stays within my list
14:27I want to rotate it
14:29I don't want to go further because there is no element stored in the list
14:32So when I need rotation
14:34And I need rotation in a fixed range
14:36What will I do?
14:37Then I will apply modular arithmetic
14:40I will use mod's special properties
14:43So I hope this explanation is clear
14:46We have also seen how to work in these formulas
14:50These formulas are part of modular arithmetic
14:52So we can remember directly that it will always work
14:55And why it will work?
14:57I have given a small logic
14:58Because I always need 0 and n-1
15:01Because I want to iterate the list so much
15:04Now let's write code
15:06Let's see
15:07Let's see