Practice › Hashing & Two Pointers
Squares of a Sorted Array
Easy · Hashing & Two Pointers · Asked at Amazon, Google, Meta, TCS, Infosys
The array is sorted in non-decreasing order and may contain negative numbers. Print the squares of all elements, sorted in non-decreasing order.
Input
First line: n. Second line: n space-separated integers.
Output
The sorted squares, space-separated.
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
The largest square is at one of the two ends. Fill the answer from the back with two pointers — no sorting needed.
Example 1
Input
5 -4 -1 0 3 10
Output
0 1 9 16 100
Example 2
Input
5 -7 -3 2 3 11
Output
4 9 9 49 121
Hints
- After squaring, the biggest values sit at the two ends of the array (large negatives on the left, large positives on the right).
- Use two pointers at the ends and fill the result from the back with the larger square each time.
Approach
Squaring then sorting is O(n log n). Instead, compare a[l]² and a[r]²: the larger one is the largest remaining square, so write it at the current end of the result and move that pointer inward. Repeat until the pointers cross.
Complexity: O(n) time · O(n) space for the output
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n), res(n);
for (auto &x : a) cin >> x;
int l = 0, r = n - 1;
for (int k = n - 1; k >= 0; k--) {
if (a[l] * a[l] > a[r] * a[r]) res[k] = a[l] * a[l], l++;
else res[k] = a[r] * a[r], r--;
}
for (int i = 0; i < n; i++) cout << res[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
res = [0] * n
l, r = 0, n - 1
for k in range(n - 1, -1, -1):
if a[l] * a[l] > a[r] * a[r]:
res[k] = a[l] * a[l]
l += 1
else:
res[k] = a[r] * a[r]
r -= 1
print(*res)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n], res = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int l = 0, r = n - 1;
for (int k = n - 1; k >= 0; k--) {
if (a[l] * a[l] > a[r] * a[r]) res[k] = a[l] * a[l++];
else res[k] = a[r] * a[r--];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(res[i]).append(i + 1 < n ? " " : "");
System.out.println(sb);
}
}Solve Squares of a Sorted Array online · All practice problems