Sorted Squares
In this article, we will discuss the following problem:
Given a sorted list of integers, our task is to compute the sorted list of squares of these given integers.
Before delving into the approach for the problem, let’s identify the available information and what is required from the problem. In a real interview scenario, this step would correspond to clarifying and understanding the requirements thoroughly.
Analysis
Given :
Sorted data, which is sorted integers in this case.
Does the input contain only positive values ? Let’s consider that input contains both the positive and negative values.
The integers are present in a list, preferrably an array for versatility. This could be flexible depending on what the individual is comfortable with. In an interview, this can be explicitly stated to the interviewer.
Required:
Sorted list (array) of squares. Each element in the output is the square of one of the elements in the input.
Additional constraints: Preferrable if the problem can be solved in O(n) time complexity with no additional space.
Approach
Approach-1 (Brute Force):
Compute the square of all the elements in the input array
Sort the modified array
Implementation in Java
public int[] computeSortedSquares(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0];
}
// Step 1: modify elements to their squares
for (int index = 0; index < arr.length; index++) {
int squareValue = arr[index] * arr[index];
arr[index] = squareValue;
}
// Step 2: sort the modified array
Arrays.sort(arr);
return arr;
}Time Complexity : O(n logn)
Step-1 in the implementation would take O(n) time, given n is the length of the array.
Step-2: sorting, would take O(n logn) time.
Approach-2: Optimized
It's crucial to note that the sorted input includes both positive and negative values. Interestingly, when we square these values, the square of a negative number can exceed that of a positive number. For instance, in an input like [-5, 1, 3], the square of -5 (which is 25) is higher than the square of 3 (which is 9). If the input array only had positive elements, obtaining the output would simply involve squaring all the numbers.
Now, to compute the output without sorting, given the presence of both positive and negative values, we can leverage a two-pointer approach. Two extreme ends can potentially give us the next largest square value. Let us try to understand this with e.g.
input: [-9, -5, 1, 2, 6, 8]
Let’s denote the two pointers as left and right. left would initially be 0 and right would be arr.length - 1 (5 in this case). All the negative values to the right of left (-5), their square would be lesser than the left element. Like wise, all the positive elements left of right (1, 2, 6), their square values would be lesser than the right element. Applying this, the maximum square value at each step would be either from the value at left or the value at right. We can place the maximum square value towards the end of the output array at each step and move towards the left in output array to place the next element.
Let’s apply the analogy to the above example.
left = 0, right = 5
arr[0] = -9, arr[5] = 8
\({(-9)}^2 > {(8)}^2\)
increment left
output: […………….,81]
left = 1, right = 5
arr[1] = -5, arr[5] = 8
\({(-5)}^2 < {(8)}^2\)decrement right
output: […………64, 81]
left = 1, right = 4
arr[1] = -5, arr[4] = 6
\({(-5)}^2 < {(6)}^2\)decrement right
output: […………36, 64, 81]
left = 1, right = 3
arr[1] = -5, arr[3] = 2
\({(-5)}^2 > {(2)}^2\)increment left
output: [……25, 36, 64, 81]
left = 2, right = 3
arr[2] = 1, arr[3] = 2
\({(1)}^2 < {(2)}^2\)decrement right
output: [……4, 25, 36, 64, 81]
left = 2, right = 2
arr[2] = 1, arr[2] = 1
we can increment left or decrement right, both are correct. Let’s increment left. This will mark the end of iteration for adding elements to the output as left > right now.
output: [1, 4, 25, 36, 64, 81]
Implementation in Java
public int[] computeSortedSquares(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0];
}
int[] output = new int[arr.length];
int outputIndex = arr.length - 1;
int left = 0;
int right = arr.length - 1;
while (left < right) {
if (Math.abs(arr[left] > Math.abs(arr[right]) {
output[outputIndex] = arr[left] * arr[left];
left++;
} else {
output[outputIndex] = arr[right] * arr[right];
right--;
}
outputIndex--;
}
return output;
}Time Complexity: O(n), iterate through the input array.
Space Complexity: O(1) Ignoring the additional space required to hold the output.
Application:
One application of this could be in geometry where you have distance from a center to different points. All the elements to the left of the point would have relative negative distance and all on the right would have relative positive distance. Consider that we are interested in knowing the relative order of absolute distance, where we need the square of the original values. Feel free to suggest other practical use-cases where this problem would be relevant.