In this chapter, we will learn how to solve Squaring a Sorted Array problem by using two pointers technique.
Table Of Contents
Problem Statement:
Given an integer array arr sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: arr: [1, 2, 3, 4, 5]
Output: [1, 4, 9, 16, 25]Example 2:
Input: arr: [-5, -3, 0, 1, 4]
Output: [0, 1, 9, 16, 25]Solution:
One simple solution can be to create an answer array of input array size. Then we can start filling it from the left side to the right side until we reach the end of the input array. Each time, we will calculate the square of the given number and store it in the answer array.
After covering all the elements, we would be having our answer array but it may or may not be sorted. To make sure that it is sorted, we can perform sort() operation on our answer array. Hence, this algorithm will take O(N * logN) time. Can we perform better?
Since the input array is sorted, the numbers at both ends can give us the largest square, therefore we can use two pointers starting at both ends of the input array. At any step, whichever pointer gives us the bigger square, we add it to the result array and move our respective pointer to the left or right accordingly.
Here is the visual representation of this algorithm:
Our algorithm will look like this:
Code:
Java
Python
C++
import java.io.*;
class Innoskrit {
public static int[] sortedSquares(int arr[]) {
int squares[] = new int[arr.length];
int start = 0;
int end = arr.length - 1;
int index = arr.length - 1;
while(start <= end) {
int leftSquare = arr[start] * arr[start];
int rightSquare = arr[end] * arr[end];
if(leftSquare < rightSquare) {
squares[index] = rightSquare;
end -= 1;
}
else {
squares[index] = leftSquare;
start += 1;
}
index -= 1;
}
return squares;
}
public static void main(String[] args) {
int ans[] = Innoskrit.sortedSquares(new int[] {1, 2, 3, 4, 5});
for(int a : ans) {
System.out.print(a + " ");
}
System.out.println();
ans = Innoskrit.sortedSquares(new int[] {-5, -3, 0, 1, 4});
for(int a : ans) {
System.out.print(a + " ");
}
System.out.println();
}
}class Innoskrit:
def sorted_squares(arr):
squares = [0] * len(arr)
start = 0
end = len(arr) - 1
index = len(arr) - 1
while(start <= end):
left_square = arr[start] ** 2
right_square = arr[end] ** 2
if left_square < right_square:
squares[index] = right_square
end -= 1
else:
squares[index] = left_square
start += 1
index -= 1
return squares
if __name__ == '__main__':
ans = Innoskrit.sorted_squares([1, 2, 3, 4, 5])
for a in ans:
print(a, end = " ")
print()
ans = Innoskrit.sorted_squares([-5, -3, 0, 1, 4])
for a in ans:
print(a, end = " ")
print()#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static vector<int> sortedSquares(const vector<int>& arr) {
vector<int> squares(arr.size());
int start = 0;
int end = arr.size() - 1;
int index = arr.size() - 1;
while(start <= end) {
int leftSquare = arr[start] * arr[start];
int rightSquare = arr[end] * arr[end];
if(leftSquare < rightSquare) {
squares[index] = rightSquare;
end -= 1;
} else {
squares[index] = leftSquare;
start += 1;
}
index -= 1;
}
return squares;
}
};
int main(int argc, char *argv[]) {
auto ans = Innoskrit::sortedSquares(vector<int>{1, 2, 3, 4, 5});
for(auto a : ans) {
cout << a << " ";
}
cout << endl;
ans = Innoskrit::sortedSquares(vector<int>{-5, -3, 0, 1, 4});
for(auto a : ans) {
cout << a << " ";
}
cout << endl;
}Output:
1 4 9 16 25
0 1 9 16 25 Time Complexity:
The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.
Space Complexity:
The above algorithm’s space complexity will also be O(N) this space will be used for the output array.
Innoskrit
We're building a next-level EdTech Startup.
