What's up guys, Mike, the coder here. Today we are going to go over two pointers. So this is a another coding interview pattern that is very, very common. And let's just start, let's get jump right into it. All right, so the first one type of the two pointer is we have we have a pointer pointing to the front of the list. So it's just like an index or something. It could be anything, right?  And then we have another pointer pointing to the end of the list. And what we're going to do is when, as we're moving one of the pointers to the right, the one at the end of the list is going to go down. Okay. And in the end, what's going to happen is we're going to meet in the middle, or we're going to stop at a certain condition that follows from this. So that's one of the pattern of two pointers. There's another pattern of the two pointers is when we have one pointer here, which is a let's say I starts from in the beginning, right? And then another one, Jay also starts at the same position as I, but I is going to go one space to the right and Jay is going to go twice as fast. So what ends up happening is that I was going to go to the right and Jay is going to twice as fast. And then as Jay reaches the end of the condition, I is going to reach either to the middle or something happens in the middle, and that's going to end the condition and stop it right there. So these are the two types of patterns, one pointing from the beginning into the end, going to the center. And the other one is one goes twice as fast than the other one. Okay, so yeah. So let's actually go over some, it sounds like really, really basic problems. So the first one is in a sorted array, find if a pair exists with the sum s. So one of the easiest ways here is we're just going to brute force it. So we're going to loop from zero to n minus two, and Jay is going to loop from i plus one to n minus one. So this is going to go from beginning to end, and this is going to go from beginning to the second to last place of the end. And if two values add up equal to s, we return true, otherwise return false. So that's like a brute force approach. And here is the more efficient approach, which is utilizing our two pointer ideas. So here, we have pair exists, right? And in here, what what we're doing is we're starting from the beginning of zero. And then we have Jay starting from the end. So this is pretty much exactly how I explained in the beginning of the video, of having two one pointing from the beginning and one pointing at end, and we're going to keep decreasing it. Okay, so what's going to happen here is that we're going to add the current sum of the first value and then the last value. Okay, and then what we're saying is that if they're both equals to there are the sum that we want to find s, then we're just going to return true. Otherwise, what we're going to do is if the current sum is less than some number x, right, some number x, or it's actually this should be s, it should be s. Yeah, this they wrote this wrong. But if our current sum is less than s, we're just going to move the lower pointer to the right. Otherwise, if the current sum is greater than s, then we're going to move the right pointed down by one. The reason why we're doing this is because if because this array is already sorted, right, if this array is already sorted, and we move one pointer to the right, that's going to increase the sum, right? So here, if the current sum is less than the value that we're trying to find, we're going to increase the current sum, right? And though that's what we want to do until our condition is met, where ends. And if it's greater than our the sum that we're trying to find, if the current sum is greater than the sum we're trying to find, we're going to decrease the right pointer. And that's going to actually decrease the sum of the first one and the last one that was adding up, right, because it's sorted, right? So therefore, this condition would be met and we will get closer and closer to the target value of s, as this loop continues on and then it ends. Okay. So yeah, that's that's this first approach of the problem of was it in a sort of a finite pair exists equals or some s. Okay. So yeah, that's this basic problem. All right, here's another one is find the middle of a link list. So here, we're going to utilize the same the second type of the two pointer, which is one is going to go twice as fast as the starting one. So j is going to go twice as fast. And as the starting value of I, which is just going to go normally. So in this example, we need to find the middle of a link list. So yeah, here's a brute force approach is just you loop to the end, and then calculate the length of link list, and then loop to the beginning again, and then divide by two, right?  But yeah, not efficient because you go twice. So the more efficient approach here is to have two pointers. So we have the slow is going to slow point is going to start from the front and the fast is going to start from the front. And then what we're going to do is while the fast is not null, and the fast next not null, so it's going to go next, and then fast is going to go twice as fast. So then in the end, as the last pointer goes to the end, the ith pointer, the first, the first pointer is going to reach the middle because it's going twice as slow as the second point, right? The second point is going twice as fast, then the first point is going to meet in the middle. And then we just return that value of slow, that's in the middle. Okay, so yeah, how does this pointer receive space because it decreases required space or we move all together. Alright, here's another one is a reversing an array. So what you could do if the naive solution is going to just loop through it and just copy all the values from the beginning to the end into like the original array. But with a two pointer approach, we could actually just swap the values. So here we're going to reverse an array, we're going to start from the beginning, pointer, start from the beginning, and then the J is going to point or start at the end. While the I is less than J, what we're going to do is we're just going to swap I and J. So it's going to reverse the two values at the beginning and the end. And then what we're going to do is we're just moving one to the front and move J to the end, move, J down by one. And then what's like, what that does is, these values are going to get swapped. These values are going to get swapped. These rides are going to get swapped, these rides are going to get swapped and then they get swapped in the end. And then yeah. The get reversed. So yeah. Okay. Another popular example of two point approach is using merge sort, which is not. Yeah, this is merged to resort arrays. Okay, so I'll just explain how the merge sort works. So here, this is a merge sort. We have one array called a and we have another ray called B, and N1 and N2 are just like the size of a and size of B. And then C is going to be our merged array, right? That's going to have twice the size of both A and B. So how does this work? The first pointer is going to loop through to all the values of A. And the second pointer at J is going to loop through all the values of B. Okay, so that's what this loop is doing. Okay, so if A is less than B, what's that going to do is that's just going to mean that hey, yeah, A is less than B. So A has to go first in our new array, right, because we're trying to merge two sorted arrays. So we want to make sure that our end array is sorted, right? So if A is less than B, the value that we are putting in our new array C must be the smaller value. So we're going to set equal to A. And then we're just going to move, move the lower pointer of I add by one. And in case it's going to be like our index of our new array, C. So in case it's going to get add by one. Otherwise, since now otherwise, this means that B is smaller than A. So we're going to set C is going to equal to the current value of B, and then k plus plus, and then J, we're going to increase that pointer plus for one. So then after this, this whole thing is completed and finished, we just have to add up the rest of the values, right? Put the rest of the values into the array. So if I is less than n, we just put the rest of the values, okay, k plus plus, okay. And then also, if J is less than n, we just put the rest of values, right? Because there are conditions if we if we stopped in the middle already, and we already merged them, and they're not the same size, right, we got to put the rest of the values in right. So here, that's this puts a and then this puts B's. Okay. So yeah, that's another way of using two pointers using in merge sort. And last and lot least is a quick sort. I believe, yeah, a partition function, a quick sort. Okay. So partitioning is like, if I put like, a value, like if let's say if I had an array, so let's say I had a quick sort partitioning, this is like, it's not that hard of an algorithm to understand. But basically, what it's doing is that if I pick one element, let's say three, all the values that are less than three is going to go on the left side and all the values are greater than three goes on the right side. So that's what this picture does. And how it works is, here's how it works, we have two pointers. We pick a pivot, which is like the values that we want to pick. Okay, that want to go from all the values to go to move all the values on the left side of that pivot. And then to move all the values, it's greater on the right side of the pivot, right? So this is like pivot is like, what's, what's the starting point value we need to put in there, right? Here is going to equal to L minus one. So that's like the lower, lower pointer. Right. And then J is going to loop from L to R minus one. So J is going to loop through. So if we go back to our picture here, let's say I picked three here, this is a pivot. It's going to loop from here to here, right, the values before three, right. And then what it's going to do is if it's smaller than the pivot, we're going to add one to our index, right, to add one to the index, and then we're going to swap those values. So that those values are going to get all the viruses that's smaller than it, we're going to go to the left. Okay. Then after this for loop is done, we're just going to swap the current value with the last value of the right side. And then we just return I plus one, so that in the end, as the pointers are moving forward. Yeah, what's going to happen is like, all the values that are smaller are going to be on the left side. Okay. So yeah, so I think that's what this pivot, this partition is doing. All the values that are smaller, the pivots can go on the left side. So that's where they have this. But yeah, both stars are moving forward in the same direction at the same place, J incrementing as well. Yeah. So yeah, that's basically the first gist of our introduction. And let's go move on some more problems. All right, guys, we're going to go over another problem or move duplicates from sorted array. So given an array, let's say it's 112. What's going to happen is we're just going to have one and two because the duplicates in this array, one one is gone. Okay. And we're assuming this is already sorted. Okay, an increasing order. So yeah, the duplicates one one are gone and it becomes one two. And then in the end, what they're going to they want us to do is return like the size of this array. So it just returned to so then we don't have to like, include the rest of the empty values here. So yeah, also in this example, let's say we have another example, zero zero one, one, two, two, three, three, four. We have zero one, two, three, four, because all the duplicates got removed. And then we're just going to return the size of the end of the array. So it'd be zero one, two, three, four, five will be five. Okay. So that's that. And here's what the code would look like. And we're going to use two pointers. So here we have, if the size is equal to zero, we just return zero because like, it wouldn't even matter, right, if it's already empty. Now, our first pointer is going to start from i equals zero, the second one is going to start from j equal to one. And we're going to loop from j to the equal to the end, less than n. And if j is not equal to i, nums at i, what we're going to do is we're going to increase i, right? So we're going to move the one on the bottom one up one. And then we're just going to set i equal to j. And then, in the end, we're going to increase j plus one. And at the end of this, we're going to return i plus one. So how this would work is that, let's say we have this one, one, two, two, three, three, I starts in the beginning as zero. So this is, this is i, right, starts here, j is going to start from one. Okay, so j is going to loop to the end of this array. So if j is, if nums at j is not equal to i, so here, it is equal to i. But so here, one is equal to one, right? So in this case, we do nothing. And then we're just going to increase j plus one. So j is going to go to here. Okay. Now, does nums at i not equal to j? Yes, they don't equal to each other. So what we're going to do is we're going to move the lower pointer up down by lower point up to here, right? And this is going to still be j is still going to be here, move the lower pointer up. And then we're just going to set the lower point is going to equal to the value of j. So this two one is going to become two, right? And then yeah, one is going to become two. And that's it. And then we move j plus plus. So then let's take this j, we're going to move it up here. And then yeah, once we move up here, we're just going to check is to yeah, is two equal to two is equal to each other. So yeah, we're just gonna move j up again, because it's value of that. And then yeah, then two is not equal to three. So then now what we're going to do is we're going to move I up. So I get to move up here. And then what we're going to do is since I is gets moved up, we're going to change this to be three. Right. So then this, yeah, we change this to be three, right? Because this is the value of j. So we change it to three, and we move j one. So then j gets up up here. Okay. Yeah, and then yeah, at that point, at that point, we just return I plus one. So then that we reach the end of the rate and then we just return 123. So we just return this. Okay. So yeah, that's basically the gist of how you would use two pointer to solve, move duplicates from sorted array. And let's go to the next problem. Our guys, the next problem is squares of a sorted array. So given a sorted array, we just want to square each of the number. And we have to make sure it's an increasing order in the end. So we have negative four, negative one, zero, three, 10. And then after squaring all the numbers, we're going to have zero, one, nine, 16, 100. So this problem is only difficult if you think about like, like if you if you think about like, because of the signs, right, the signs make it an issue of squaring it, right? But yeah, let's just go to the solution and show you guys how you use two pointers for this. So here's the solution. How you do it, we're going to create a new array called result. And then the lower point is going to start from the zero. And then the right point is going to start from the end. Right. So it's basically very similar to how we did how we explained in the previous video, or the previous beginning of the video, right? So let's say we have this negative four, minus one, zero, three, and then 10. Okay. So what we're going to do here is, okay, the starting value is zero. And the last value is going to start to the end. So here, here is a starting point of I, and here's going to start J is going to start the end. And then we're going to have another array, our resulting array, right? So this is like the final results of our array. So like, I have no idea. I was like, this, I don't know, just like these. Okay, yeah, that was that's fine. Okay. So like, yeah, this is like a final end result of our array. What we're going to do is we're going to loop through, we're going to loop through from the right side of I. So yeah, I call left and right, I and J, but here, they have a third pointer here, starting at the end of this. So this is going to be like the end result that we're going to start from. Okay, so if the left, if the right side, the absolute value of the right side. So if 10 absolute value of 10 is greater than the absolute value of left side, which it is, right? So 10 is greater than four. What we're going to do is we're going to square 10. So 10 is going to become 100. And we're going to put that in our end of the array. And then we're going to move array down by one. Okay, then we're going to move J down by one. So this is going to move down to here. Okay. And then what we're going to do is, yeah, we repeat this process. So then is three greater than four, right? Absolute value three is a greater than four. No, it's not. So then what we're going to do is we're going to have add force negative four square into here. So this is going to become 16. And then what we're going to do is we're going to move our ith pointer to the right. So it's going to be here. Okay. And then we do the same thing is negative one is three greater than negative one, three greater than one, right? Absolute value one. So yes, three is greater than one. So we're just going to put nine, right? We square three square, give nine. And then we move the three down to here. And then we're going to say is negative one greater than zero greater than one. No, it's not. So we're going to add one into our array, negative one square is going to be one into array. And then we move I up. Okay, and then zero, we're just going to put zero in there. And yet, so in the end, we're going to have zero one, nine, 16, 100, which is, I believe, zero one, nine, 1600, yeah, which is exactly what we want. And all the values here are the square values here. And yeah, we just return that. So yeah, that's the gist of this code. And he's still using two pointers. And that's squares of sorted array. Alright, guys, we're going to go over another problem called three sum, given an array of numbers, return all the triplets of values of i, j and k where they're not equal to each other, each not equal to each other, but their sums are equal to zero, right? So here we have negative one, zero, one, two, negative one, negative four. And negative one, negative one, two, right, these values are not the same, right? They're not in the same indexes, and they're not in. Yeah, they're just not the same. But yeah, they're not the same indexes, right? But their sums negative one plus negative one plus two is equal to zero. So that's why this is a inside one array. And then here, they have another value of negative one, zero, one, which are different indexes also, and their sums are equal to zero. And yeah, that's the return the array. So let's actually just go look at the solution because it uses it uses the two pointer rule. Okay, so here, let's just look at how it works. So we have sorted, we first, we should sort the array because in order to do two pointers, they have to be sorted to do our two pointer rule, they have to be sorted. Okay, so here, we're going to loop from the beginning to the end of our value numbers, right, we're going to loop from beginning to the end of the right. If it's greater than zero and it's equal to the previous value, generally, you just, we're just going to continue and not check it. Because what we're trying to do is we're trying to have at find three values that add up equal to add up and they're equal to zero, right? And if it's equal to the previous value, ideally, that doesn't mean that they're going to add up to zero, right? Normally, they're ideally they wouldn't add up to zero. So yeah, if I is greater than zero, and they're not they're equal to the previous value, the current number is equal to the previous value, we're just going to continue. Okay, so here's your here's when the two pointers starts. So it's actually clear this. Okay, so let's go back to the description of the problem. And I'll show you as an example how this would work. And then we'll be on our way. Okay, and then we'll do the next problem. It's interesting a while for me. Okay, so we have negative one zero one two negative one four. So we have negative one zero one two negative one four. Okay, and then we want to return negative one negative one two negative one zero one. Okay, so here, after sorting it, it's going to be like, we have negative one, negative one, zero, one, two and four. Okay, so after sorting it, our new array looks like this. So let's get rid of this. And get rid of this, rid of this. And this is going to be our array. Okay, so then now, if the current value I is equal to the previous value. So here we start from here, right? I is, we're going to skip the first part, because I is equal to zero, right? So this condition doesn't get run. All right, we're going to see here, we're going to L is going to equal to i plus one. So this is, this is i, this is L, this is the left side of our pointer. And right is going to equal to the end. So here, this is right. Okay, now what we're going to do is we're going to just sum them. So if L is less than r, what we're going to do is we're going to sum i plus L plus r. So here, we're going to add this plus this plus this. So it's going to equal to two, right? So negative one plus negative one plus four is two. Now, if it's greater than zero, we're going to move the right pointed down. So because two is greater than zero. And what we're trying to find is we're trying to find the three numbers add to zero. Since two is greater than zero, that means the sum is too large. So what we're going to do is we're going to move the right pointed down to decrease our sum. So we're going to move the right pointed down. Okay, and yeah, and this ends there. Then we go back to the top here, and then we're going to do i plus i plus L plus r. So i plus L plus r is equal to zero, right? So it's equal to zero. So since it's equal to zero now, we're going to push back. So we're going to add negative one, negative two, negative one, negative one, two into our new array. So this is going to be negative one, negative one, two. So this is going to be like the one of the answers there. And then now we're going to do while L is equal to L plus one. So while this is just going to equal to this is just going to keep moving the pointer down if they have the same values, right? Because we don't want to. Yeah, we don't want to like continue having the same values that we loop through. So yeah, because L is not equal to L plus one, this for loop does not run this while loop does not run is r equal to r minus one. Nope. And this doesn't run. Then what we're going to do is we're going to move L plus one and then r minus one. So here, we're going to L plus one, move to top and r is going to minus one down. Okay. And then this L statement ends there. And then we'll go back to the top. And we're going to do i plus L plus r. So here we're going to do negative one plus zero plus one. And that gives us zero. So then we're going to push this value negative one, zero one, it's going to get added again. And then while L is equal to L plus one, so it's not equal to it. And while r is equal to r minus one, it's not equal to it also. Yeah, then we're gonna do L plus L plus plus and r minus minus. So I was going to get incremented to here, and r is going to get minus r is going to move down here. And then because L is now not less than r, this loop ends. And then yeah, and then we go back to the top and yeah, then I goes to the front of this here, right? And then we do this pretty much the exact same thing. So yeah, then after I moves here, does I equal to the previous value does I does I equal negative one is equal to previous value it is. So we're going to continue. So we're just going to go to the next iteration of I so I is going to move to the right. And then we just do the exact same thing. So L is going to equal to I plus one, so L is here. And then r is going to equal to the end. So just this one. And then we do the exact same thing with some zero plus one plus four. But these are all greater than zero. So we could just like end it right here. Technically, we could just end this right here. Because we wanted to sum equal to zero. But yeah, he didn't have a break statement. But yeah, that's pretty, then at the end, we just return this. And yeah, that's pretty much the gist of the code. And that's how you do three sum is equal to zero. All right, guys, we're gonna go over another problem three sum closest. Bear with me guys, because my throat is hurting for some reason.  Anyway, so we're given this very similar to the previous problem, except now our target is now a different number. And we want to find the closest triple sum that gets you to the target. So we have negative one to one negative four. And our target is one. And the closest triple sum is two, because if you the closest sum that is the sum of three integers is negative one plus two plus one, and that's equal to two, and that's closest to one. Okay, here we have zero zero zero on the target is one closest triple sum of zero plus zero plus zero is zero. And that's close to one. So let's just go to the solution right now, because yeah, if you do two pointers, the solution, it's not that hard. Okay. So first, we have to sort it. Sort it because in order to do two pointers, generally, the the array has to be sorted, right? Because otherwise, you can't really do the sliding window, or not sliding window, the two pointer rule. So here, we sort the array, we're going to have a the size variable size, and then we have the first answer, which is just zero plus one plus two. Okay, then what we're going to do is we're going to loop from zero to the second to last second to last value. And we're going to start a two pointer from there. So if we were to do this again, right here, let's say we had like, I don't know what it was. I forgot what I don't even know what it was there, to be honest. Let's say we have like negative one, two, three, four, I don't know. And we want to find like, the closest which is some which would be three, right? Let's let's say we want to find the closest of three. And in this case, it would be like negative one to negative one plus two is one plus action, not three. Five, right, let's say let's say we want to find a closest sum to five. So we do this. Right, closest sum is five. So then we the closest sum would be negative one plus two, plus four, which would be five, right? That's would be that would be our answer. But so let's how how we would do this, we start from here. And then we're going to loop this up to the second to last value to three. And we're going to start our two pointers. So here we start left is going to point to start value of i plus one. So this is left. And then right would go to the end, which is this one. Right, this would be right. And then we do this exact same thing. So we're going to do like some of this i plus l, which is the plus four. And I'll actually give us five though. And then we what we're going to do is, here's the only difference is that we're going to take the answer and subtract by the target. So if like, and yeah, so what we're doing essentially is that like, answer is like the first three sums, right? So it's this plus this plus this, right? Right, one plus four, right? So if our answer is subtracted by target, so that's that's going to represent how far we are from the target. And if it's greater than the the sum that the sum that we just calculated. So if it's greater than this sum, this plus this plus this, right? minus the target value, which is the one we're finding five, then what we're going to do is that'll be our answer, right? Answer would equal to that. And then we just go continue. Yeah, our answer would be we have to shift the sum, right? So like the sum would now equal to a new sum that's close to some would now equal to negative one plus two plus four, right? Because that's as closer to it, right? Because this value is closer to it. Otherwise, what we're going to do is, if it's equal to a target, like exactly equal to five, we're just going to break. So in our case, we're doing negative one plus four, two plus four, and that's actually equal to five. So then we'll just break. Okay. And then if it's greater than target, what we're going to do is we're going to decrease the right pointer, because that means that that means that our target is this is too much, right? There's the value is too much. So when you decrease the right pointer size, actually lowers the sum value of your next sum, because since it's already sorted, the last one, four is like greater than three. So if we move the right pointer down, so if we move from four to three, it's actually decreases like the next sum. So that's why if we want to find our target sum, and it's our if the values are greater than it, like the three sums are actually greater than the target, we should decrease the right pointer. Okay. Otherwise, if it's less than the target, we're going to move the left pointer up. So we're going to move this up. So in our case, it's actually exactly equal to the target, right? Because negative one plus two plus four is like exactly equal to five. So in that case, this would actually just break. And that'll be our answer. But yeah, that's basically the two pointer rule, we're using this is technically three pointer rule, because we're using I and L and R goes through it. So it's like a n squared algorithm, or yeah, n squared algorithm in total. Yeah, this is better than n cube. So yeah. Yeah, and let's just go to the next problem. All right, guys, we're going to go over another problem called count triplets with some smaller than the target. So it's pretty much the exact same problem as the previous one, except instead of finding the closest one, we want to find the one that is just smaller than it. Okay. So yeah, if we had negative two zero one three, the out of the sum in our target is two, we want to find the count the number of triplets with a sum smaller than two, right? So here, there'd be two triplets negative two zero one and negative two zero three, they're just smaller than two. But yeah, um, yeah, so let's just go to directly to the solution. I'll show you guys what how to do it. Because pretty much very similar. Okay, so we first sort the array because you have to do it in order to do two pointer. That's the that's only downfall downside of it. Yeah, sort the array and initialize the result equal to zero. Okay, we're going to loop from zero to n minus two again, which is just going to be like the reason why it's n minus two because, like I said in the last video, not last video, last part is that if you if you had like an array of like, let's just go to this example. 52347, right? So five, two, five, one, five, one, three, four, seven. Our two pointer is going to like we have the first point here, right? And then we're going up to this part because like the second to last because our two pointers are actually going to start from here, plus one, and then j is going to be at the end, right? Our left, left and right. Or right. And then as we decrease this size window to try to calculate with this one, if we move right to the right. So that's why it's like I that's why it's I plus one, right? That's why it's n minus two, right? We're going to the second to last value for I. Anyway, yeah, we got second to last. Here they call it J and K. I'll just call left and right because that's just what I did in the previous ones. Yeah, I is going to loop from here to the end. Left is going to equal to I plus one and right is all the way on the right side again. Okay, so then we're just going to be in the middle. So we're going to decrease increase L and decrease r. So how this works is that the only difference is now is that so we're still going to sum I plus j plus k. So we're still going to sum this plus this plus this, right? The values that are three pointers. This time, if it's greater or equal to some. So if it's so if our target, let's say our target was like s, right? Target is s. So if it's greater than equal to s, we're going to move the right pointer down. So we're going to move this down. Okay, and then yeah, otherwise, what we're doing, what we want to do is we want to calculate the number of sub arrays that was a sub rays. No, the number of triplets that are just smaller than the given value, but the sum smaller than the given value. So if it's smaller than it, right, so let's say this plus this plus that is smaller than the given value of s. Then what we want to do is we're actually going to, since we want to calculate the number of it, number of number of triplets are like that. We're going to take the right pointer of this r and subtract it from L. Okay, and the reason why is because so let's say if our sum was like, I don't know, 14, like just greater than 13, right? So let's say let's say our sum was like, I don't know, 13 or something 14. Oh, I just realized it has to be sorted. Okay, so let me just move this real quick. Yeah, this has to be sorted. Move this real quick. Here. Okay, so yeah, so let's say our sum was like 14, right? So one plus three plus seven is 11, right? One plus three plus seven is 11, right? The i plus j plus k. Yeah, so since it's less than 14, we want to calculate the number of different triplets, right? Count the number of triplets are smaller. So because we know that because it's sorted, we know that this triplet, this, this and this are are like all smaller than the 14. So we know like one plus three plus four is 14, right? Then because this the right value and it's sorted is greater than all the previous values, right? So seven is greater than four plus five. We know immediately that the sum one plus three plus seven, right? And the sum, all the values between left and right, the sum of all the values between left and right are going to also be smaller than it, right? So here I'll explain why because like, the sum one plus three plus seven is this, right? Which is 11, right? And because seven is the largest value in our sorted array, we know that the values of four and five are also going to be smaller than seven. So one plus three plus four, yeah, plus four, we know immediately this is going to be smaller than 11, right? So this is like eight. And we know immediately that one plus three plus five, which is equal to nine, this is also smaller than 11. So because of that, we could, since we know because it's already sorted, we know these two situations, we could just if we want to count how many, how many triplets are smaller than it, we just take the index of the right minus index of left. Okay, so here, if we have 01234, the index of the right is this seven, yeah, no, four, and the index of the left is one. So four minus one, we give us three, and these values are going to be all smaller than it. Okay, so that'll be the counter that we add to our answer. And then we're going to move our left pointer up. So we're going to, we're going to move our left pointer up, and then do the exact same thing. Okay, then check this, this plus this plus this, see if it's smaller, then we subtract R minus L and do the exact same thing. Okay, and after this gets done, we end up with counting all the triplets that have a sum smaller than the given value. Okay, so yeah, that's just the code. Let's go to the next problem. All right, guys, so now we're going to go over sub array product less than k. So given an array of integers, and a value of k, we need to return the number of contiguous sub arrays whose product of all the values are less than k. So yeah, this is exactly the same thing. Only difference now is just multiplying. So I think it's like, return the number of contiguous sub arrays. Yeah. So if we just go to go to the solution, you'll exactly you'll see like exactly what it is. But yeah. Oh, wow, this guy used like, I don't know what he used here. This is actually unreadable. I don't want to I don't want to deal with like, super unreadability. This one, also unreadable. Oh my gosh. Okay, let's see if we find one that's actually readable. Okay, yeah, this is like the closest thing that's readable. Okay, so if k is less than or equal to one, return zero, because all the numbers are positive in the array, so you can't really do anything there. Alright, so here we're going to have our two pointers left, zero, and then right result is just like the answer product is like the current product. Okay, so we're going to move the right from zero to the end. And we're just going to keep multiplying by the values. If our product is greater than equal to k, we'll divide by the numbers on left pointer, and increase left point. So like if, yeah, and then yeah, so like what this is doing is like, okay, here, I'll show you. So let's say we had see, so let's say we have 10, five, two, six, right? So we have 10, five, two, six, 10, five, two, six. Okay, and our k is equal to 100. Did they sort it? I'm pretty sure they sorted it. I'll just how would they do this? They didn't sort it. Okay, that's even more crazy. Alright, so this answer did not use any sorting for some reason. So I don't think they're using like the same two pointer algorithm.  Okay, so they're going to loop from here to here. Okay, so this is like, this is the right pointer. They're gonna loop from here to there. And during the time, they're gonna just keep like a track multiplying how many elements they're currently multiplying at. So like, here, the prod would just be like, 10, right? And then they go to the next one, five, and so on, so forth. So 10, is this greater than 100? Oh, is it less than 100? So it's not right. So then they're just gonna keep going into the right. This condition never gets run. This never gets run. So what they're doing is, it's not greater than k, right? What they're going to do is they're just going to take r minus left, which left they said equal to zero.  So that'd be like, it just be one, right? So like, our answer would get incremented to one. So here would become one. Okay, and then yeah, and then we go to the next value. So then here, r is going to go to this part. Okay, and our product is going to be like 10 times five, which would be 50. And then is it greater than equal to k? No, it's not. So what we're going to do is our left is still pointing to left value. So this is our left, right? This is our left. So it will be r minus zero plus one should be two. So this is going to be added by two. So this becomes three. Okay, that becomes three. And then our gets moved to the right again. Okay, and then what's going to happen is we're going to multiply this by 100. So this becomes not by 150 times two become 50 times two would become 100. Right. So this is our product now. This is prod product 50 times two would be 100. And then now it's greater than equal to k. So then what they're going to do is they're going to divide by this left this value. And the reason why they're doing that is that's going to decrease like the window. And then when it gets decreased, they move out to the right. So then now, yeah, so now they're going to decrease divided by 10, which is going to get give us 10. So 100 becomes 10. So let's get rid of this hundred becomes 10. Okay. And then is 10 greater than equal to k? It's not so then we're done with that. And then we're going to take right minus left plus one. So here to be right, which would be two minus left be one plus one would be two minus one plus one is two plus two becomes five. So answer it will now be five. This and yeah, answer be five. Then we just continue again. are multiplied by go back to the top. Are going to go to the here, multiplied by six, which is going to become 60. Right? So this is going to be 10 times six to 60. Okay, and then is that it? I think that's it. Yeah. It's not greater than k. Let me take our minus left, which would be three minus one, which is two plus one, which is be three, three minus two, two plus one is three. Plus three, this become eight. Okay. And then it's done. And we just return that. So what what essentially what it's doing is like, it's doing the exact same thing, except as we're going to the right, this should actually personally, I think this should be sorted. But I don't know. But yeah, I don't know why it's like not. What it's basically basically is doing is like, as we're going to the right, we're maintaining a variable product. And then if it's like, if it's if our current product is like, greater than or equal to k, which is our answer, what we're going to do, because we want smaller than it, right? We're just going to divide by like the left pointer, right divide, divide, divide by the left value on the left pointer, and that's going to decrease it. And then we're going to move our left pointer upwards. So then that's going to give us the next window that is the next length of our window that we could that that are all the values are going to also be smaller than k. Okay, is when we plus equal to it, I'll give us all the values are smaller than it. Okay, so yeah, that's the gist of this. And I think, I think we're, I think that's all the problems we have.


Thank you for joining us at this session today. I'm Rhiann A Auckland. I've been at Goldman Sachs for 10 years and I currently manage our London Data Models Team Helping to build the data models for our global market business. Prior to that, I spent six years in the Middle Office supporting our credit derivatives Mr from everything operational. Hopefully, you are able to tune into Piers Keynote session earlier in this conference where he took us through the technology behind legend a'r ystafell fyddien o'i gwneud. Mae angen i'r cwestiynau, yn ystafell i'r gwell yn dda i'r un o'r gweithgareddau, yn cyhoedd yr un driforol, sy'n cydweud hynny, peir. Felly, mae'r ddweud i'r unrhyw ymddangos sy'n wneud i gael y cwestiynau. Mae hyn o'r cwestiynau'r gweithgareddau yn gweithgareddau yn cael ei gydag yma ychydig yn y ddydd yn ddigon i gydag ymddangos ymddangos. Felly, mae'n gwneud i gyda'r ddweud eich bod yn legend, ac yn ddatblygu ddweud i gydag cyfreu'r ystyried arall, oherwydd y cerddau a'r ddweud yn hynny. Byddwn ni'n ddweud, gan nhw'n ddelch yn ysgrifennu, Pia ac Ier oedd wedi'i gweithio ar y cerddau o'r ddweud o'r ddweud i ddweud i gweithio i gydag a'n ddweud i gydag ar y sgreun, ond yn y cerddau cyd-relygu, yna'n ddweud i gydag ar gweithio. Felly, yn gyntaf y dyw i'n fifio'r ddaeth i'r ddiweddau i'r ddiweddau i'r ddiweddau. Mae'r ddiweddau ar 4 yma, rydym ni'n cerdydd tdwynd i Isdor a'r ddylai'r ddiweddau ar y dyfodol y maen nhw yw'r cyffredin cyfathau yn ddim yn gyfath. A rydym ni i'n gwybod a'r hefyd yn gwybod yma yma, byddwn ni'n gwybod yma cael y ddydd ei wneud i ddim yn gwybwys iawn i'r cyfath, And on't just demonstrate it just as a tool and as a functionality. So, the CDM felt like a great place for us to position the pilot and, with the support of ISDA, WEGNOSYS and SRFINOS, we were able to set up two working groups. The first one looked at developing and enhancing the current code available for FX options, and the second looked to build a brand new payout in order to be able to define commodities products. Last month, we successfully committed code back to the CDM, and this was a big milestone for many of us in the project, showcasing how legend was able to help us to continue to build and develop together in collaboration with the industry and translate that code back into the Rosetta form in order to be able to submit that to the golden source. Some of the functions that we found really helpful during this collaboration were the diagrams, and I will showcase that a little bit later in a demonstration. One of the things that came out of the pilot that we felt would be even more beneficial for collaboration was the idea of a notes page, bit like a sticky note where you may just want to jot down some ideas to come back to as a group or even put it out there for someone else to try and solve a particular issue that you were working on. I'll also demonstrate that as we go into the next section. As a second part of the demonstration, I also want to show you some of the extended functionality within legend, mainly the validations, the model to model mappings or transformations of data, and then how we can test this to demonstrate the compilation of the code. Finally, we'll look at how we actually commit this code back and the SDLC functionality that is available through GitLab to ensure that we have governed commits and we avoid any conflicts. So let's get started with our demonstration. Hopefully you can all see my screen. So we are going to use the CDM that I just spoke about as part of the demonstration and this is available in the external version of legend. So if you choose the project, you can then create your own workspace. So for this, I will call it LFDemo and hit create. Once that's ready for you, you can hit next to open your workspace and now we're all set. So you can see on the left hand side here that we have the CDM available to us. If we open these drop downs, you can actually see the model and for those of you that are familiar with the CDM, some of these classes you will recognise. For those of you who aren't, these are just all the classes that have been built to define derivatives products. And within each class, there'll be multiple properties and we'll show you some of those a little bit later on. When I started out, I mentioned this idea of diagrams. So let's have a look at one of those. So this is a diagram of payouts. Payouts is how we define products in the CDM and the idea is that they are building blocks to defining a product overall. So in this version, you can see the entire class of payouts and you can see that we have other classes coming off of this. You can zoom in and out using the scroll button on the mouse and you can also move it around using the right hand click button. You'll notice when you zoom it, you're actually focused on the centre of the page. So if you move it around, you can then zoom in to other parts of the diagram as you wish. To collapse the diagram, very simple. You can click on the class and hit delete. So I can do this across all of them. And as I do, you'll notice that old back into the original class. I could also go into the model and start to pull those payouts back out again. So if we go and have a look for the interest rate payout. If I drag this back into the diagram, we will see it removed from within the class and connected by a line with all of the details within itself. Next I want to show you how to use the sticky note. So in here we can quickly and easily click the plus. We have a choice of things to create and we are going to use a few of these a little bit later. But the one I want to bring your attention to now is this new text. So if we call it to do within this, we can just type some things down that might help us in the future. So from those payouts, we may want to do a few extra things. We may want to change the name of a property. We may also want to combine the equity payout and the commodity payout into an asset payout. And this is actually what happened as part of one of the Finos pilots. You will see that our to-do does find its way into the left hand side here as well. So we have a to-do list. How about we give it a go to do the actual first one on our list? So if we go back to our diagram, you'll notice it's here in the left hand. But also since I've already picked it up, you will see it in this top panel for a quick and easy navigation. And if we double click on the payouts here, it will open up on the right hand side such that we can see the properties within that class and edit them directly. So the first item on our to-do list was to change equity payout to asset payout. Hopefully, as you can see from that, nice and easy to make that change. If I wanted to add a new property, I just hit the plus here and I can equally remove it using the X. What I wanted at this point is show you the compilation of the code. Now in this scenario, I am expecting it to provide us an error because the asset payout or as was previously called the equity payout is in other parts of the code. And so by trying to compile now, it is likely to fail, but we will go through it to show you. Right hand side, but it's also brought up the code in the background. So for those of you who are more comfortable with coding directly, this is all happening in the background and you could update directly in here. But if we hit F8, it will take us back. So now I want to take you through to some of the more extended functions available within Legend. And to do this, we're going to have a look at one of the classes called FX haircut currency. So this is a class that has two properties. One is termination currency and the other FX designated currency. Basically for this class, it is defining which currency we use for the haircut. If it's the termination currency, then this is termination currency attribute would be true. And if this was false, then we would be able to specify a currency that we would want to use. You can see that this is termination currency is Boolean and is mandatory. Whereas the FX designated currency is an optional field. And this class actually has a few constraints on it. For those of you who are familiar with code, you might already be able to see a discrepancy here. We have a validation of one of constraint, which is saying that you must have one of these. However, you can notice that the is termination currency is mandatory and therefore we're always going to have two. So this is actually obsolete, but I am going to leave it here so that when we come through to the tests, we'll be able to demonstrate that the tests do fail and we can resolve it at that point in time. So to run the tests, what we'll do is also generate a model to model mapping. Now this is something that would help you if you were looking to map perhaps between proprietary data models and industry standards, or even internally between your own data models, you could do this model to model mapping in legend. So for us to make a start, we are going to create a new package. And I'm going to call this one target haircut. And within target haircut, I'm also going to create a new class. So as you can see, I've been going through nice and easy to navigate adding new items. And now we have a new class, I can add the new properties. So on my internal model, I'm also going to have two properties. But I'm going to call the first one use termination currency and specified currency. I'm going to leave both of my attributes as string, but I will make the specified currency optional, given we won't always need it. So how do we map between these two? Again, to add an item just in our drop-down list, add a new mapping. I'm going to call this mapping haircut. Now we have the ability to add the target class and also the source class. So if we add the target class first, this is our target haircut. And here on the right-hand side, we can add our source, which is the one from our CDM model, which is FX haircut currency. So in the middle, you can see it's already pulled in our properties from our target class. And on the right-hand side, the two properties that are available to us from the source class are ready to go. So we can drag and drop these to demonstrate the mapping. Now you may remember that actually the is termination currency is actually a boolean. So we need to do a conversion of that into a string. Now you will have noticed as I was typing there that there was a red error box just below. This will be there until you have written a logical statement in the code. And that's very helpful for those who are perhaps not so technical in the coding languages. So we now have a logical transformation from our is termination currency to use termination currency. And our specified currency and FX designated currency should work as they are. So let's start building some tests. So we want to test our new target currency class. So here we can build some data. So is termination currency. I'm going to start with false such that we can specify a currency. Let's go for GBP for these purposes. And we can generate an expected result and I'm expecting this to fail. So it's actually failing because we haven't actually changed our equity payout back. So as I mentioned previously, when we did our compilation, this asset payout was in other places. So if we change this back and this demonstrates that the entire time that the code is compiling. And that helps us to avoid conflicts in data as we go along. So we now have another error. This is the one related to our constraint. So that one of constraint that we mentioned earlier. So nice and easy way for us to fix this one if we go back to our haircut currency class and into the constraints. We can just hit the X to remove it. Now if we try and generate an expected outcome. Excellent. So now we have an expected outcome. We can see the conversion of our code. So is termination currency of false has mapped to no. And we've now received our specified currency of GBP because of that. I also now want to create a test so that we can test true in this scenario. So to add a test, I just click the plus button. I'm going to leave this one as true. And let's go for USD this time around. Although when I try and generate this expected result, I'm again expecting to receive an error. And that is because when is termination currency is true, we should be using the termination currency and therefore should not be specifying another. So in this case, we actually need to remove the additional piece of data from our source. And now we have an expected result with our use termination currency of yes and our specified currency as null. So we have two tests available. As you can see, as we built those tests, the validations that we expected to fail were failing, and therefore we were able to demonstrate those. And now we can actually run our two tests here. So to run the tests, you can hit the play button. So we have one test passed. And we'll just do the second one as well. And our second test is passed too. So we've now been able to demonstrate a check of the validations. I've managed to also show you how the compilation runs in the background the entire time such that if anything is changed, even if not directly to the code you're working on, it will also throw an error where necessary. And we've managed to test our model to model mappings between two classes and show those to be able to pass. If this was where we were and we were complete with what we wanted to do today, we could then go and submit this back through the SDLC. Now there is SDLC that sits within GitLab. So each submission and commit goes through GitLab, but you are able to do that directly from legend. So the changes are tracked, everything that we've done today. And I could go through and submit these. Once I've submitted, people could go in and also approve them. And once approved, they could be merged back in. So all of that can be run directly from the UI. It can also be done by GitLab as well. So that's everything we wanted to show in the demo. Hopefully that's given you a taste of what you could achieve by using the tool and some of the benefits in terms of how we use it in the industry for collaboration as well. So the other two parts of this session we wanted to cover were what other opportunities are there beyond this CDM use case for us to collaborate in the industry and use legend as a tool to accelerate those industry standards. So there are a couple of projects already running. One of those is the Finos Securities Reference Data Project. And this is one that was set up actually on the back of the FX Options pilot, where we found that it would be really helpful to have an industry standard around FX currencies. And so there was one that had started up, was in relatively early stages, and they are now looking to use legend in their data modelling going forwards. Other places, so Finos also have a financial objects project where they would want to be trying to solve specific problems in the industry. Now this could be within the derivative space already continuing to develop the CDM as we have already demonstrated over this last year. It could also be looking at other areas and other problem statements that could be in new products. It could be different parts of a life cycle such as the quoting. Or it could be specific issues in the processing that we can identify today. Another option is to go beyond financial data specifically and actually look at other strands of data within the industry. There's obvious ones around reference data perhaps or market data. Another that we looked at also was actually ESG data. So as part of the pilot, we started to explore this. It was decided that it was probably going to be a bigger project than we could tackle within the timeframe that we wanted to. But during those discussions, it was definitely identified that it would be a helpful place for us to start to standardize industry data in this space. And so perhaps that's another place we could continue to develop. So new features that are coming into legend that should also help to bring extra benefits in this space. So the mapping to databases. So giving access to real data such that you could start to integrate that into your processes and into your systems. This way we'd really realize the benefits available in terms of industry standards and communicating in data. Supporting flat data sources. So the idea that we could output a CSV file for instance. And automated code generation. So I did mention at the beginning that we were able to translate the code from the legend language to Rosetta in order to submit that back as part of the pilots. That will be available coming soon. And it will also give us the opportunity to add other languages into that translation. So you could use it for proprietary language transformation or other languages that are available in the industry as well. And finally, let's explore how you can get involved and use legends as we go forward. The first one is contribution. So legend is now open source that happened last month. So you can contribute directly through the GitHub legend repositories. You could go in and raise issues or comments on current codes that people are working on raise issues just that you think should be resolved if you can go and resolve it yourself. Another space is the dock site. This is actually where new people who are looking to onboard onto legend can go and get demonstrations similar to today, but in different parts of the system as well. And you could go in and improve that document site as you start to use it and play around. Secondly, collaboration. We've touched on this, I guess, in the use case and also just recently, but you could get involved in collaboration that's ongoing in the industry. Perhaps there's some current efforts that are of interest to you and you could get involved in those groups and influence industry standards or suggest and push new industry standards. So where there's places that you think there would be benefit to actually build a working group, get some industry participants together and start working in legend to improve that. Finally, adopting legend on premise. So this is where people start to really gain those benefits of that model to model mapping that I demonstrated being able to generate your proprietary models in the system and map those to some of the industry standards that are already available. You could also, as I mentioned before, start to map between your own internal data models, perhaps, and that would help in translation and processing of data in other ways. So thank you for your attention through this session today. As I mentioned, Pierre and I are both available for questions right now, and we'd love to continue a discussion on any of the points that I have touched on, or also that Pierre mentioned in his keynote speech. Please do follow up with us and thank you for attending.