1
00:00:00,690 --> 00:00:02,940
Hi everyone, let's do this question.

2
00:00:02,940 --> 00:00:07,950
You are given an array of integers sorted in non-decreasing order.

3
00:00:07,950 --> 00:00:13,440
Now non-decreasing means it can be increasing or equal when you go from left to right.

4
00:00:13,440 --> 00:00:14,040
All right.

5
00:00:14,070 --> 00:00:18,450
Now it says find the starting and ending position of a given target value.

6
00:00:18,450 --> 00:00:23,340
If the target value is not found in the array, return minus one comma minus one.

7
00:00:23,340 --> 00:00:27,690
You must write an algorithm with O of log n runtime complexity.

8
00:00:27,690 --> 00:00:28,890
So this is the question.

9
00:00:28,890 --> 00:00:31,470
Now let's say this is the array which is given to you.

10
00:00:31,470 --> 00:00:33,480
And the target is equal to two.

11
00:00:33,510 --> 00:00:35,820
So you can see that we have two in this part right.

12
00:00:35,820 --> 00:00:38,160
So the first two is occurring at index one.

13
00:00:38,160 --> 00:00:40,710
So that's why the left extreme over here is one.

14
00:00:40,710 --> 00:00:42,960
And the last two is occurring at three.

15
00:00:42,960 --> 00:00:44,430
So we are returning three over here.

16
00:00:44,430 --> 00:00:46,380
So the output should be one comma three.

17
00:00:46,380 --> 00:00:47,460
So this is the question.

18
00:00:47,460 --> 00:00:53,610
And then the caveat is it's mentioned that we have to write an algorithm with O of log n runtime complexity.

19
00:00:53,610 --> 00:00:54,540
So that's the question.

20
00:00:54,540 --> 00:00:57,630
Now again let's go ahead and write a few test cases.

21
00:00:57,630 --> 00:01:03,240
And remember over here you have log n and there are a few indications that this is actually a variation

22
00:01:03,240 --> 00:01:04,290
of binary search.

23
00:01:04,290 --> 00:01:08,310
So that's one indication over here the time complexity has to be O of log n.

24
00:01:08,310 --> 00:01:12,930
And we know that the time complexity for binary search is O of log n.

25
00:01:12,930 --> 00:01:18,270
And then it's given that the array is non-decreasing it's sorted and it's non-decreasing.

26
00:01:18,270 --> 00:01:22,470
So when something is sorted always remember try to use binary search.

27
00:01:22,470 --> 00:01:23,280
In that case.

28
00:01:23,280 --> 00:01:25,050
Now we have understood the question.

29
00:01:25,050 --> 00:01:27,360
Let's go ahead and write a few test cases.

30
00:01:27,360 --> 00:01:32,610
And remember when you're doing this in the interview you can always ask the interviewer if it's okay

31
00:01:32,610 --> 00:01:37,140
whether you and he or she can come up with a few test cases together.

32
00:01:37,140 --> 00:01:42,540
So this will help you ensure that you have understood the question properly, and are well aware of

33
00:01:42,540 --> 00:01:45,300
the expectation to go ahead and solve the question.

34
00:01:45,300 --> 00:01:47,670
So over here, let's go ahead and write a few test cases.

35
00:01:47,670 --> 00:01:51,630
Now let's say the array is 12345 and the target is three.

36
00:01:51,630 --> 00:01:53,550
So you can see that it's only occurring once.

37
00:01:53,550 --> 00:01:56,670
So we just have to return this index over here which is two right.

38
00:01:56,670 --> 00:01:59,220
This is 0123 and four.

39
00:01:59,220 --> 00:02:03,330
So the first index and the last index where three is occurring is two itself.

40
00:02:03,330 --> 00:02:05,490
So the output has to be two comma two.

41
00:02:05,490 --> 00:02:08,670
Now what if the array is empty and the target is one.

42
00:02:08,670 --> 00:02:11,490
So in this case one is not there in this array.

43
00:02:11,490 --> 00:02:14,340
So the output has to be minus one comma minus one.

44
00:02:14,340 --> 00:02:19,950
Now similarly let's say we have another array 57789 and the target is seven.

45
00:02:19,950 --> 00:02:22,470
So in this case this index over here is one.

46
00:02:22,470 --> 00:02:23,820
And this index is two.

47
00:02:23,820 --> 00:02:24,000
Right.

48
00:02:24,000 --> 00:02:26,040
So this is 0123 and four.

49
00:02:26,040 --> 00:02:28,560
So that's why the output has to be one comma two.

50
00:02:28,560 --> 00:02:34,050
Now if over here the target was let's say ten then we would have to return minus one comma minus one

51
00:02:34,050 --> 00:02:36,120
because ten is not there in this array.

52
00:02:36,120 --> 00:02:37,290
So this is the question.

53
00:02:37,290 --> 00:02:37,620
All right.

54
00:02:37,620 --> 00:02:39,090
So we have understood the question.

55
00:02:39,090 --> 00:02:41,370
And we have formulated a few test cases.

56
00:02:41,370 --> 00:02:45,180
Now we are ready to go ahead and think about solving this question.

57
00:02:45,180 --> 00:02:46,740
So let's do that in the next video.