Problem Statement
Given an array of sorted numbers, Square each number and arrange their squares in sorted order.
Example:
Input1: arr: [-1, 0, 1, 2, 3] Output1: [0, 1, 1, 4, 9] Explanation: Square for each number is [1, 0, 1, 4, 9] and their sorted order is [0, 1, 1, 4, 9].
Code
Java
C++
Python
import java.util.*;
class Innoskrit {
public static int[] squareSortedArray(int[] arr) {
int n = arr.length;
int low = 0, high = n - 1, sortedIndex = n - 1;
int[] sorted = new int[n];
while(low <= high) {
int lowSquare = arr[low] * arr[low];
int highSquare = arr[high] * arr[high];
if(lowSquare <= highSquare) {
sorted[sortedIndex] = highSquare;
high--;
} else {
sorted[sortedIndex] = lowSquare;
low++;
}
sortedIndex--;
}
return sorted;
}
public static void main(String[] args) {
int arr[] = new int[] {-1, 0, 1, 2, 3};
int[] res = Innoskrit.squareSortedArray(arr);
for(int x : res) {
System.out.print(x + " ");
}
}
}
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static vector<int> squareSortedArray(vector<int> &arr) {
int n = arr.size();
int low = 0, high = n - 1, sortedIndex = n - 1;
vector<int> sorted(n);
while(low <= high) {
int lowSquare = arr[low] * arr[low];
int highSquare = arr[high] * arr[high];
if(lowSquare <= highSquare) {
sorted[sortedIndex] = highSquare;
high--;
} else {
sorted[sortedIndex] = lowSquare;
low++;
}
sortedIndex--;
}
return sorted;
}
};
int main() {
vector<int> arr = {-1, 0, 1, 2, 3};
vector<int> ans = Innoskrit::squareSortedArray(arr);
for(int x : ans) {
cout<< x << " ";
}
return 0;
}
class Innoskrit:
@staticmethod
def square_sorted_array(arr):
n = len(arr)
sorted = [0] * n
low, high, sorted_index = 0, n - 1, n - 1
while low <= high:
low_square = arr[low] * arr[low]
high_square = arr[high] * arr[high]
if low_square <= high_square:
sorted[sorted_index] = high_square
high -= 1
else :
sorted[sorted_index] = low_square
low += 1
sorted_index -= 1
return sorted
if __name__ == '__main__':
arr = [-1, 0, 1, 2, 3]
ans = Innoskrit.square_sorted_array(arr)
for x in ans:
print(x, end = " ")
Output:
0 1 1 4 9
Time and Space Complexity
Time Complexity: O(N)
Space Complexity: O(N) for sorted array.