This code adds the largest element to the smallest element and goes inwards into the code.
Very often we'll want 2, 3, 4 pointers in our array. These pointers do not always have to move at the same speed. Having 2 pointers is often an evolution of using 2 for loops. Look at this problem:
Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.
Given the array is sorted, our first thought might be 2 nested for loops. This is O(n^2). We want O(n).
We can achieve this with pointers.
Place 1 pointer at the start, and and another pointer at the end.
We know the value is larger, so we move one to the right.
x = [1, 2, 3, 4, 5]
pointer1 = 2 # value 1
pointer2 = 4 # value 5
sum = 7
sum == target
This algorithm is O(n).
The pointers pattern is an essential pattern for array manipulation, and we will see it come up a lot. Especially with 2 pointers moving at different speeds.
Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
There are multiple solutions to this!
Solution 1 - Python with in-built Sort
def sortedSquares(self, A: List[int]) -> List[int]:
for i in range(len(A)):
A[i] *= A[i]
A.sort()
return A
Space complexity is O(1) as it is entirely in-place. .sort() is in place. Ask your interviewer what to do here.
Solution 2 - Java with Pointers
We can do this in Java using 2 pointers, which is the way the solution was supposed to be written (it just happens our code is just as fast):
class Solution {
public int[] sortedSquares(int[] A) {
int n = A.length;
int[] result = new int[n];
int i = 0, j = n - 1;
for (int p = n - 1; p >= 0; p--) {
if (Math.abs(A[i]) > Math.abs(A[j])) {
result[p] = A[i] * A[i];
i++;
} else {
result[p] = A[j] * A[j];
j--;
}
}
return result;
}
}
Solution 3 - Python with Pointers
def sortedSquares(self, A):
answer = collections.deque()
l, r = 0, len(A) - 1
while l <= r:
left, right = abs(A[l]), abs(A[r])
if left > right:
answer.appendleft(left * left)
l += 1
else:
answer.appendleft(right * right)
r -= 1
return list(answer)
Author explains:
The question boils down to understanding that if we look at the magnitude of the elements in the array, A, both ends "slide down" and converge towards the center of the array. With that understanding, we can use two pointers, one at each end, to iteratively collect the larger square to a list. However, collecting the larger square in a list with list's append, results in elements sorted in descending order. To circumvent this, we need to append to the left of the list. Using a collections.deque() allows us to append elements to the left of answer in O(1) time, maintaining the required increasing order.
This uses built in sort. It should be O(n log n) but due to how Python's sorting algorithm works, it's O(n) amortised. You can learn about why it's O(n) .