00:00What did I do in my main function?
00:02There is already a list in my main function
00:03which is sorted and rotated.
00:07For sorted and rotated,
00:09I have added elements in it
00:10and defined my target
00:12which is 16.
00:13Now let's make a function
00:14public static boolean
00:18pair sum 2
00:19I will have an array list
00:21for integer values
00:23which I have given the list
00:25and with it I will have a target.
00:28Now this list
00:29I will find out the pivot
00:32I will find out the pivot
00:33I will find out the pivot
00:36I will find out
00:37or I will call it pivot
00:38or call it breaking point
00:40BP
00:41I will call it not a valid index
00:44Now I will run a loop
00:45for int i equals 0
00:48i less than
00:49list.size
00:52i++
00:54where I will find out the value
00:56in my list
00:56in the i-th index
00:58that becomes greater than
01:00or equal to
01:01I will find out that
01:02there is no value repeated
01:04unique values
01:05so in that case
01:07somewhere
01:07if my list.get
01:11i-th value becomes greater than
01:14list.get
01:15i plus 1th value
01:16meaning
01:17the current value is greater than
01:20what is coming?
01:21this is my breaking point
01:23breaking point
01:24so we update the value of BP
01:26which becomes equal to
01:28i
01:28i is breaking point
01:30and as i get a point
01:31i can break from this loop
01:32so breaking point
01:34i have also
01:35now i will initialize
01:37my left pointer
01:38where will start from
01:40i plus 1
01:41because there is
01:43the smallest value stored
01:44in fact
01:45this is not i
01:46i is my variable
01:48which is the scope
01:49only to this loop
01:50so what will I do?
01:51I will take this
01:52in BP
01:52I have stored my i value
01:53after that
01:55I will initialize
01:56right pointer
01:57which will be equal to BP
01:58and that is my
01:59largest element
02:01right pointer
02:02left pointer
02:03left pointer
02:04while
02:04my left pointer
02:06is not equal to
02:07my right pointer
02:08we will do
02:10first case 1
02:11case 1
02:12says that
02:12if
02:14my list.get
02:15left pointer
02:16plus
02:17list.get
02:19right pointer
02:20equals
02:21my target
02:22so what i have to do?
02:25i have to do
02:26the return
02:26true
02:30let's talk about case 2
02:31case 2
02:33says
02:34that
02:35if
02:36my left pointer
02:37and right pointer
02:37gets less
02:38from target
02:39then i have to update
02:40left pointer
02:41how will i update
02:42left pointer
02:43left pointer
02:44plus 1
02:45from n
02:47here
02:48i define
02:48here
02:50my int n
02:51will be equal to
02:52my list.size
02:55so this is updated
02:56the rest of my case 3
02:58how will the case 3
02:59how will the case 3
03:00how will the case 3
03:03n plus
03:04right pointer
03:05minus 1
03:06modulo
03:06n
03:08so i covered
03:09three cases
03:10completely similar
03:11i have written
03:12while loop
03:12last
03:13i will return
03:14false
03:15that means
03:16that my target
03:17doesn't exist
03:18in this list
03:20let's save
03:21now run
03:21on its list
03:22for target
03:23is equal to 16
03:24here
03:25i will call
03:25pair sum
03:272
03:28let's save
03:29and now run
03:33answer
03:33is true
03:34because
03:3416
03:35pairs
03:35exist
03:36what will exist
03:37i can take
03:39pairs
03:39here
03:40100
03:41then
03:41the target
03:43is not equal to
03:44100
03:46for that
03:47i have to return
03:48false
03:48and if you see
03:50this function
03:50will be linear
03:53time complexity
03:54which means
03:55big of n
03:56will be equal to
03:57here
03:58i will rotate
04:01them
04:01but this rotation
04:02will stop
04:03when my left
04:05pointer value is equal to
04:06right pointer
04:07so
04:07total distance
04:08will be equal to
04:13n elements
04:14so
04:14the time complexity
04:15turns out to be
04:16big of n