1
00:00:00,720 --> 00:00:03,090
Hi everyone, let's do this question.

2
00:00:03,090 --> 00:00:09,690
You are given an integer array Numb's sorted in ascending order with distinct values prior to being

3
00:00:09,690 --> 00:00:10,830
passed to your function.

4
00:00:10,830 --> 00:00:18,090
Numb's is possibly rotated at an unknown pivot index k, where k is between one and numb's dot length

5
00:00:18,090 --> 00:00:23,160
such that the resulting array is this what is given over here where it's zero indexed.

6
00:00:23,160 --> 00:00:23,520
All right.

7
00:00:23,550 --> 00:00:26,370
Now for example, this is the array which is given to you.

8
00:00:26,370 --> 00:00:28,830
And let's say it's rotated at pivot index three.

9
00:00:28,830 --> 00:00:30,570
So 0123.

10
00:00:30,570 --> 00:00:32,340
So this is pivot index all right.

11
00:00:32,340 --> 00:00:36,210
And it becomes 456701 and two.

12
00:00:36,240 --> 00:00:40,890
So this is similar to a previous question we have seen where we have seen that the array is rotated

13
00:00:40,890 --> 00:00:42,000
n number of times right.

14
00:00:42,000 --> 00:00:43,170
Or k number of times.

15
00:00:43,170 --> 00:00:48,630
So if this is the array which is given to you after it is rotated at pivot index three, you get four

16
00:00:48,630 --> 00:00:48,960
over here.

17
00:00:48,960 --> 00:00:51,840
So 456701 comma two.

18
00:00:51,840 --> 00:00:54,330
So this is pretty similar to the previous question.

19
00:00:54,330 --> 00:00:54,660
All right.

20
00:00:54,660 --> 00:01:00,210
So after this array over here is rotated one time this seven over here will come to the first part.

21
00:01:00,210 --> 00:01:00,390
Right.

22
00:01:00,390 --> 00:01:03,870
You will get 701245 and six.

23
00:01:03,870 --> 00:01:05,490
So this is after one rotation.

24
00:01:05,490 --> 00:01:10,170
Similarly after the second rotation you will get six also coming over here.

25
00:01:10,170 --> 00:01:12,330
So that's the same thing that we have seen previously.

26
00:01:12,330 --> 00:01:16,890
So again if you do three rotations you will get this thing over here which is mentioned over here.

27
00:01:16,890 --> 00:01:20,430
And that's the same thing as rotating at pivot index equal to three.

28
00:01:20,460 --> 00:01:22,590
Now given an integer target.

29
00:01:22,590 --> 00:01:24,240
So you are given a target integer.

30
00:01:24,240 --> 00:01:28,740
Return the index of target if it is in the array, else return minus one.

31
00:01:28,740 --> 00:01:33,180
You must write an algorithm with O of log n runtime complexity.

32
00:01:33,180 --> 00:01:37,230
So if this is the array which is given to you, notice that this is a sort.

33
00:01:37,260 --> 00:01:41,370
This is the array 0124567 which is a sorted array.

34
00:01:41,370 --> 00:01:43,110
And then it's rotated one time.

35
00:01:43,110 --> 00:01:45,660
So you get 7012456.

36
00:01:45,660 --> 00:01:49,560
And then let's say for example the target which is given to you is equal to seven.

37
00:01:49,560 --> 00:01:55,290
Now in this case you have to return the index zero because seven over here is at index zero.

38
00:01:55,290 --> 00:02:01,470
Now if the target was ten then you have to return minus one because ten is not present in this array

39
00:02:01,470 --> 00:02:02,400
which is given to you.

40
00:02:02,400 --> 00:02:08,460
And then the catch is that you have to write an algorithm with O of log n runtime complexity.

41
00:02:08,940 --> 00:02:15,120
Now, the naive way of searching for it would be you could just say index off and then you can just

42
00:02:15,120 --> 00:02:15,930
pass this target.

43
00:02:15,930 --> 00:02:16,230
Right.

44
00:02:16,230 --> 00:02:17,280
So index of seven.

45
00:02:17,280 --> 00:02:18,390
So it will give you zero.

46
00:02:18,390 --> 00:02:21,300
So that would be a o of n operation.

47
00:02:21,300 --> 00:02:21,480
Right.

48
00:02:21,480 --> 00:02:25,920
Because in the worst case you will have to go through each of these elements which is a linear search.

49
00:02:25,920 --> 00:02:31,680
But over here it's mentioned that our algorithm has to run in O of log n runtime complexity.

50
00:02:31,680 --> 00:02:37,200
Now again remember the interesting thing to notice over here is first you know that binary search runs

51
00:02:37,200 --> 00:02:38,820
in O of log n runtime.

52
00:02:38,820 --> 00:02:42,030
And then over here also this has something to do with sorting right.

53
00:02:42,030 --> 00:02:46,260
So the array was sorted initially and then it's just that it's rotated a few times.

54
00:02:46,260 --> 00:02:52,140
So again we have to make use of some variation of the binary search algorithm which we discussed to

55
00:02:52,140 --> 00:02:57,750
be able to search for the target value which is given to us in the array, which is possibly rotated

56
00:02:57,750 --> 00:03:00,840
in lo log n complexity time complexity.

57
00:03:00,840 --> 00:03:02,130
So that's the question.

58
00:03:02,130 --> 00:03:03,570
So we have understood the question.

59
00:03:03,570 --> 00:03:06,210
Now let's go ahead and write a few test cases.

60
00:03:06,210 --> 00:03:11,160
And remember in the interview feel free to ask any clarifying questions you have.

61
00:03:11,160 --> 00:03:12,210
So that's very important.

62
00:03:12,210 --> 00:03:16,890
And then once you're done and if you understood the question properly, you can come up with test cases

63
00:03:16,890 --> 00:03:18,120
along with your interviewer.

64
00:03:18,120 --> 00:03:23,280
So you can ask him or her whether it's okay if both of you could come up with test cases together.

65
00:03:23,280 --> 00:03:29,040
So this will cement and ensure that you and the interviewer are on the same page, and that you have

66
00:03:29,040 --> 00:03:31,500
a good understanding of what the expectation is.

67
00:03:31,500 --> 00:03:33,660
So let's go ahead and write a few test cases.

68
00:03:33,660 --> 00:03:37,740
Let's say the array is empty and target for example is ten.

69
00:03:37,740 --> 00:03:40,350
So in this case we cannot find ten in the array.

70
00:03:40,350 --> 00:03:42,540
So we would have to return minus one.

71
00:03:42,540 --> 00:03:42,840
All right.

72
00:03:42,840 --> 00:03:44,160
So that's straightforward.

73
00:03:44,160 --> 00:03:46,680
Now what if the array is 12345.

74
00:03:46,680 --> 00:03:50,280
And you can see it's sorted and no rotations have been made on it.

75
00:03:50,280 --> 00:03:52,380
Now let's say target is equal to three.

76
00:03:52,380 --> 00:03:56,040
In this case we have to return the index over here which is equal to two.

77
00:03:56,040 --> 00:03:56,280
Right.

78
00:03:56,280 --> 00:03:58,620
Because that's the index of this value over here.

79
00:03:58,620 --> 00:04:02,730
Now let's say we have rotated it and we get 3451 and two.

80
00:04:02,760 --> 00:04:06,540
So you can say that this is the equivalent of doing three rotations to the right.

81
00:04:06,540 --> 00:04:11,040
Or it's the equivalent of rotating where the pivot index is this over here right which is two.

82
00:04:11,070 --> 00:04:13,290
So you get 3451 and two.

83
00:04:13,290 --> 00:04:15,090
And let's say the target again is three.

84
00:04:15,090 --> 00:04:17,910
So in this case you have to return zero right.

85
00:04:17,910 --> 00:04:20,640
So over here the target was at index two.

86
00:04:20,640 --> 00:04:23,280
But over here the target is at index zero.

87
00:04:23,280 --> 00:04:24,390
So this is the question.

88
00:04:24,390 --> 00:04:26,550
So we have understood the question properly.

89
00:04:26,550 --> 00:04:32,520
In the next video let's see how we can solve this question with the variation of the binary search.