Square of sorted Array

103.Squares of a Sorted Array

Array

Two Pointers

Problem Statement:

Given an integer array A sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Algorithm:

1. Use a two-pointer approach to traverse the array from both ends:
• Compare the absolute values of the numbers at the left and right pointers.
• Square the larger absolute value and place it in the current position of the result array, moving the pointer accordingly.
2. Repeat the process until the pointers meet.
3. The result array will be populated in reverse order (largest squares first).

Complexity:

Time: O(n), where n is the length of the array | Space: O(n).

Java Implementation:

// Classic Two-Pointer Solution
public int[] sortedSquares(int[] A) {
    int[] res = new int[A.length];
    int k = A.length - 1; // Position to fill in the result array
    int i = 0, j = A.length - 1;

    while (i <= j) {
        int num;
        if (Math.abs(A[i]) > Math.abs(A[j])) {
            num = A[i++];
        } else {
            num = A[j--];
        }
        res[k--] = num * num; // Square the larger number and fill from the end
    }

    return res;
}
                

Python Implementation:

def sortedSquares(A):
    res = [0] * len(A)
    k = len(A) - 1  # Position to fill in the result array
    i, j = 0, len(A) - 1

    while i <= j:
        if abs(A[i]) > abs(A[j]):
            res[k] = A[i] ** 2
            i += 1
        else:
            res[k] = A[j] ** 2
            j -= 1
        k -= 1  # Move to the next position

    return res
                

C++ Implementation:

#include 
#include 
using namespace std;

vector sortedSquares(vector& A) {
    vector res(A.size());
    int k = A.size() - 1; // Position to fill in the result array
    int i = 0, j = A.size() - 1;

    while (i <= j) {
        if (abs(A[i]) > abs(A[j])) {
            res[k--] = A[i] * A[i];
            i++;
        } else {
            res[k--] = A[j] * A[j];
            j--;
        }
    }

    return res;
}