1 00:00:00,830 --> 00:00:01,550 Hi, everyone. 2 00:00:01,580 --> 00:00:05,000 So today we are going to solve this question to some part two. 3 00:00:05,710 --> 00:00:08,780 OK, now this is exactly the same as the previous question. 4 00:00:08,780 --> 00:00:11,950 So the only difference is basically the input that is sorted. 5 00:00:12,110 --> 00:00:12,530 OK. 6 00:00:14,340 --> 00:00:19,350 And potteries basically sorted, given our target value, what they have to do, you have to find two 7 00:00:19,350 --> 00:00:25,690 numbers inside the area such that if you add those two numbers, you can obtain the target value. 8 00:00:26,250 --> 00:00:31,590 OK, the only difference between this question and the previous question is basically the array will 9 00:00:31,590 --> 00:00:32,159 be sorted. 10 00:00:32,450 --> 00:00:34,380 OK, that is sorted. 11 00:00:34,620 --> 00:00:40,820 OK, so basically all the solution that we discussed in the previous problem are valid here, ok. 12 00:00:40,860 --> 00:00:47,400 For example, the brute force solution that we discussed pick one element and search for another element. 13 00:00:47,400 --> 00:00:48,760 That solution is valid here. 14 00:00:49,470 --> 00:00:52,260 The second approach, the second approach we used map. 15 00:00:52,260 --> 00:00:54,160 So that solution is also valid here. 16 00:00:54,340 --> 00:00:58,400 OK, so basically these solutions does not care about the array. 17 00:00:58,410 --> 00:01:00,840 Whether that is sorted or not, the solution will work. 18 00:01:01,990 --> 00:01:07,420 OK, so the solutions are definitely valid, but here we have to use the property of the area and what 19 00:01:07,420 --> 00:01:08,080 is the property? 20 00:01:08,080 --> 00:01:10,300 So the property is basically the given at is sorted. 21 00:01:11,250 --> 00:01:12,660 Now, how we can use. 22 00:01:13,730 --> 00:01:21,440 This property, to solve our question, OK, so how we can use this property, so basically the first 23 00:01:21,440 --> 00:01:25,730 way to solve this question is what are you going to do is you pick one element. 24 00:01:27,390 --> 00:01:29,550 OK, pick one element. 25 00:01:31,260 --> 00:01:34,120 And then we have to search for another element. 26 00:01:34,440 --> 00:01:37,400 OK, we have to search for that element. 27 00:01:37,650 --> 00:01:39,750 But since the arrays sorted. 28 00:01:41,320 --> 00:01:44,650 We can use the binary search for searching the other element. 29 00:01:45,530 --> 00:01:52,930 OK, so for example, if you are standing at one, the target value 16, you have to search for 15 and 30 00:01:52,930 --> 00:01:55,720 for searching 15, we can use binary search. 31 00:01:57,210 --> 00:02:02,850 OK, so whatever the time, complexity of using this approach to the time, complexity is basically 32 00:02:03,000 --> 00:02:04,440 in the worst case, what will happen? 33 00:02:04,440 --> 00:02:05,820 We have to pick every element. 34 00:02:06,180 --> 00:02:09,660 So a loop, basically a loop for picking every element. 35 00:02:09,669 --> 00:02:13,170 So and multiply, we have to search for other elements. 36 00:02:13,200 --> 00:02:18,600 So this is logoff in certain complexities and log-in and the space complexities. 37 00:02:18,780 --> 00:02:19,620 Big of one. 38 00:02:21,750 --> 00:02:24,450 OK, so this is the first approach. 39 00:02:25,420 --> 00:02:27,550 Now, let us discuss the second approach. 40 00:02:29,490 --> 00:02:32,910 The second approach, basically, this is called 2.0 approach. 41 00:02:33,330 --> 00:02:35,820 OK, so what is our 2.0 approach? 42 00:02:36,330 --> 00:02:40,980 So 2.0 approach says you take two pointers when at the start. 43 00:02:40,990 --> 00:02:41,870 When at the end. 44 00:02:42,420 --> 00:02:44,070 So I am taking two pointers. 45 00:02:44,670 --> 00:02:48,690 So this is we have to take two point one at the start. 46 00:02:48,690 --> 00:02:49,740 One at the end. 47 00:02:50,940 --> 00:02:56,730 OK, then you will add the two as you will start placing, so they will be three conditions. 48 00:02:57,450 --> 00:03:03,720 So first condition is when you will start plus and it will become close to the target value. 49 00:03:04,950 --> 00:03:09,730 This is the first scenario, if this is the case, we can simply return our answer. 50 00:03:10,290 --> 00:03:14,850 We can simply create a vector and we can return a start command simple. 51 00:03:15,890 --> 00:03:21,230 Now, the second condition can be, if you will add the two elements, Starplex, and it can be greater 52 00:03:21,230 --> 00:03:22,760 than the target value. 53 00:03:23,830 --> 00:03:30,280 OK, so if basically you start plus end is getting the target value, our current numbers are greater 54 00:03:30,280 --> 00:03:31,240 than the target value. 55 00:03:31,270 --> 00:03:34,180 That means I have to decrease this part, OK? 56 00:03:34,330 --> 00:03:36,000 This is bigger than the target value. 57 00:03:36,010 --> 00:03:37,180 I have to decrease this part. 58 00:03:37,510 --> 00:03:40,900 So for decreasing this part, I can do and minus minus. 59 00:03:41,590 --> 00:03:48,100 OK, because let's say this is and here, if you will move in the direction, what will happen that 60 00:03:48,100 --> 00:03:48,820 is sorted. 61 00:03:48,970 --> 00:03:52,950 So basically the value of and will decrease the value of and will decrease. 62 00:03:52,960 --> 00:03:55,630 And obviously this whole part will decrease. 63 00:03:56,290 --> 00:03:57,150 OK, so will do. 64 00:03:57,160 --> 00:03:58,090 And minus minus. 65 00:03:58,480 --> 00:04:03,710 Now that third condition can be when you are adding these two elements. 66 00:04:03,760 --> 00:04:05,910 This is less than the target element. 67 00:04:07,460 --> 00:04:12,470 So if this is the scenario, what you can do, so basically after adding these two elements. 68 00:04:13,870 --> 00:04:20,470 We are less than the target element, so in this case, I can write a start plus plus basically if I 69 00:04:20,470 --> 00:04:23,530 will move ahead then I will start. 70 00:04:23,530 --> 00:04:28,870 Value will increase and and overall, this value will increase and we will be able to reach condition 71 00:04:28,870 --> 00:04:29,410 number one. 72 00:04:30,040 --> 00:04:32,560 OK, so these are the very three simple cases. 73 00:04:33,540 --> 00:04:39,900 If I start and is bigger, then decrease by doing and minus minus if I start, placenta's smaller, 74 00:04:40,140 --> 00:04:43,020 then do start placeless to make this value bigger. 75 00:04:43,760 --> 00:04:47,940 OK, now let us implement these approaches on these examples. 76 00:04:48,570 --> 00:04:50,980 OK, so this is my start point. 77 00:04:51,900 --> 00:04:53,060 This is my end point. 78 00:04:53,940 --> 00:04:59,540 OK, so one plus forty five, this is 46 so I will do and minus minus. 79 00:05:00,120 --> 00:05:01,410 So this is my new end. 80 00:05:01,460 --> 00:05:02,760 OK, remove from here. 81 00:05:03,690 --> 00:05:05,490 So one plus 10. 82 00:05:05,490 --> 00:05:08,400 This is 11, so 11 is less than 16. 83 00:05:08,400 --> 00:05:10,280 So I will start placeless. 84 00:05:10,290 --> 00:05:14,690 So we will start from here but start here for blastin. 85 00:05:15,090 --> 00:05:17,790 So this is 14, so 14 is smaller. 86 00:05:18,240 --> 00:05:19,560 So I will move ahead. 87 00:05:19,680 --> 00:05:21,120 So this is my new start. 88 00:05:21,460 --> 00:05:23,480 OK, six plus 10. 89 00:05:23,820 --> 00:05:24,750 This is 16. 90 00:05:24,780 --> 00:05:27,210 OK, so six plus 10. 91 00:05:27,510 --> 00:05:28,350 This is 16. 92 00:05:28,560 --> 00:05:34,280 So I will return start comma and I will create a vector and I will start command. 93 00:05:34,350 --> 00:05:39,540 OK, now let us implement this Approach 2.0 approach. 94 00:05:39,850 --> 00:05:42,900 Let us implement 2.0 approach on this example. 95 00:05:44,260 --> 00:05:52,690 OK, so this is my start point, this is my end point, given that is sorted, basically. 96 00:05:53,090 --> 00:06:00,670 OK, so one plus six, this is seven, so I have to move ahead to seven is less than 10. 97 00:06:01,300 --> 00:06:03,910 So this is my start to play six, eight. 98 00:06:04,150 --> 00:06:05,740 So it is less than 10. 99 00:06:05,890 --> 00:06:07,390 So I have to move ahead. 100 00:06:09,820 --> 00:06:13,930 Three, six, nine, so nine is less than 10, so move ahead. 101 00:06:16,380 --> 00:06:22,910 Six plus four, so 10 equals then, so we have reached our answer and I will start. 102 00:06:23,250 --> 00:06:30,760 And very simple now let us implement this 2.0 approach on this example. 103 00:06:30,790 --> 00:06:34,020 OK, so this is a start and this is end. 104 00:06:34,750 --> 00:06:36,590 OK, so two plus 15. 105 00:06:36,630 --> 00:06:39,620 So this is 17 and 17 is greater than nine. 106 00:06:39,930 --> 00:06:40,650 So I will do. 107 00:06:40,660 --> 00:06:41,730 And minus minus. 108 00:06:42,800 --> 00:06:43,690 I have two degrees. 109 00:06:44,120 --> 00:06:48,030 OK, so two plus 11, so we learned last week, basically tardiness. 110 00:06:48,060 --> 00:06:51,080 So today is the deadline, so move backward. 111 00:06:51,470 --> 00:06:56,480 So I will remove and from here and I will put and here now seven plus two. 112 00:06:56,700 --> 00:06:58,910 So this is nine and nine equals nine. 113 00:06:58,920 --> 00:07:02,570 So we got our answer and I will then start command. 114 00:07:03,050 --> 00:07:04,540 OK, very simple. 115 00:07:04,970 --> 00:07:07,910 So why this 2.0 approach is working. 116 00:07:08,610 --> 00:07:11,060 OK, so why this is working. 117 00:07:11,060 --> 00:07:14,750 This is only working because the given that is sorted every. 118 00:07:16,180 --> 00:07:22,450 Since the governor is ordinary, then only this hour, these three conditions will work, then only 119 00:07:22,450 --> 00:07:26,440 this 2.0 approach will work only when the governor is assaulted every. 120 00:07:27,670 --> 00:07:31,120 OK, now what will be the time and space complexity? 121 00:07:31,900 --> 00:07:35,160 So basically what we are doing, we are simply iterating over the area. 122 00:07:35,470 --> 00:07:41,050 So the time, complexity of the two pointer approaches big off and and the space complexity, we are 123 00:07:41,050 --> 00:07:42,590 just creating few variables. 124 00:07:42,700 --> 00:07:46,710 So this is the time and the space complexity of the Bhupinder approach. 125 00:07:48,630 --> 00:07:56,230 So you can see yourself by just taking and longer time, but this 2.0 approach is taking big oftentime. 126 00:07:56,270 --> 00:07:59,040 OK, so this 2.0 approach is the best approach. 127 00:07:59,820 --> 00:08:01,890 OK, this is the best approach. 128 00:08:03,210 --> 00:08:09,870 Now, let us write the code, but before writing the code, see this example here, so two plus seven. 129 00:08:10,900 --> 00:08:16,480 It's basically 9:00, so our answer should be zero when we have to return the index, but we have to 130 00:08:16,480 --> 00:08:20,880 return one comma to OK, so we have to add plus one. 131 00:08:21,400 --> 00:08:28,300 We have to return one comma, too, because in the end it says you have to return one indexed based, 132 00:08:28,470 --> 00:08:28,900 OK. 133 00:08:30,380 --> 00:08:38,549 So generally, our area is basically zero indexed based on what it is indexed based, but the question 134 00:08:38,549 --> 00:08:40,340 now is to return the indexes. 135 00:08:41,419 --> 00:08:45,270 When indexed, based, basically, OK, so after calculating the answer. 136 00:08:45,290 --> 00:08:49,750 So our answer is basically zero common after calculating the answer, we will add plus one. 137 00:08:50,120 --> 00:08:54,770 So I will return one to basically the indexing is basically starting from one. 138 00:08:54,800 --> 00:08:59,430 OK, so if this is the question, so normally that is indexed based. 139 00:08:59,450 --> 00:09:01,180 So this is zero, one, two, three. 140 00:09:01,760 --> 00:09:04,760 But the problem is, is that there is one index to be. 141 00:09:04,790 --> 00:09:06,790 So this is one, two, three, four. 142 00:09:07,160 --> 00:09:11,000 So that's why I will return one Clamato instead of returning Zuckermann. 143 00:09:11,270 --> 00:09:11,630 OK. 144 00:09:12,630 --> 00:09:13,500 Now, that's right, the. 145 00:09:15,010 --> 00:09:16,460 So writing code is very simple. 146 00:09:17,560 --> 00:09:19,270 So first, let us create. 147 00:09:20,720 --> 00:09:27,640 I would answer now let us use to point that approach for two point, that approach you need to point 148 00:09:27,650 --> 00:09:27,810 out. 149 00:09:28,070 --> 00:09:33,850 So the first point I start and you have another point, but let's name this area. 150 00:09:35,210 --> 00:09:38,030 So this another point that is a nazis' minus one. 151 00:09:38,180 --> 00:09:38,600 OK. 152 00:09:40,880 --> 00:09:48,040 Annotates my one now to the dropping idea, so we'll start this list and this will be the strobing criteria 153 00:09:48,620 --> 00:09:53,510 now that three situations so basically start plus and. 154 00:09:54,530 --> 00:09:56,390 It goes to the target value. 155 00:09:57,430 --> 00:10:00,970 So if this is the scenario, what they can do, I Sadaat push back. 156 00:10:02,660 --> 00:10:12,080 Start plus one, and similarly, Sadaat, push back and plus one and then you can your answer. 157 00:10:14,390 --> 00:10:16,910 OK, the second situation can be. 158 00:10:18,890 --> 00:10:20,240 If the start plus end. 159 00:10:21,690 --> 00:10:26,930 It's basically less than their target value, so if it is less than the target value, you have to do 160 00:10:26,940 --> 00:10:30,360 start placeless so that this value can be increased. 161 00:10:30,540 --> 00:10:36,060 OK, so that this will look an increased Starplex because in the Right-Hand side, all the elements 162 00:10:36,060 --> 00:10:37,400 will be increasing elements. 163 00:10:37,450 --> 00:10:39,890 OK, all the elements will be bigger than the current element. 164 00:10:41,100 --> 00:10:44,340 And in the end, smart, who can write and minus minus. 165 00:10:44,580 --> 00:10:46,030 OK, very simple. 166 00:10:46,470 --> 00:10:48,780 And finally, for the purpose. 167 00:10:50,030 --> 00:10:55,370 I will return on set here also, OK, for the completion purposes, because I have to return that property 168 00:10:55,370 --> 00:10:57,170 just so I have to return. 169 00:10:58,630 --> 00:11:01,720 I said here I have to return this line for the completion purposes. 170 00:11:01,760 --> 00:11:05,950 OK, now let's bring our code and then we will try to submit our code. 171 00:11:08,500 --> 00:11:10,480 OK, so our court is looking now at some. 172 00:11:14,370 --> 00:11:22,830 OK, so our goal is 100 percent correct, so as discussed, the time complexity is big often and the 173 00:11:22,830 --> 00:11:24,650 space complexities big often. 174 00:11:25,340 --> 00:11:29,130 OK, so this approach is called 2.0 approach. 175 00:11:30,710 --> 00:11:34,790 To point out approach, and this approach is working because the given that is sorted out. 176 00:11:35,160 --> 00:11:39,710 OK, so if you have any doubt in the logic or in the court, you can ask me, OK, thank you.