Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. After squaring, the biggest values sit at the two ends of the array (large negatives on the left, large positives on the right).
  2. 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