Definition
- Problem – given a sorted array with possible negatives, produce an array of squares also in sorted order.
- Two-pointer approach – place
leftat index 0 andrightat the last index, and fill a result array from the back. - Comparison – compare
Math.abs(arr[left])withMath.abs(arr[right]); square whichever is larger and place it at the current back position. - Fill direction – filling from the last index toward index zero builds the sorted output in one pass.
- Complexity – O(n) time, O(n) space for the output array.
Rajesh at the National Bank of India has a sorted list of daily profit-and-loss figures where losses are negative and profits are positive. He needs the squared magnitudes sorted for a volatility measure. The biggest squared values live at the two ends of the sorted list. Priya reads from both ends inward, each time squaring whichever has the bigger magnitude and dropping it into the back of a new tray.
Understanding the Concepts
What is the squaring a sorted array problem?
Given a sorted array that may contain negative numbers, return a new array of the squares of each number, also sorted. The complication is that a large negative squared can be bigger than a small positive squared, so naively squaring left to right does not preserve the sorted order.
package com.bank.core;
import java.util.Arrays;
public class SquareSortedArray {
public static int[] sortedSquares(int[] arr) {
int n = arr.length;
int[] result = new int[n];
int left = 0, right = n - 1;
int pos = n - 1;
while (left <= right) {
int leftAbs = Math.abs(arr[left]);
int rightAbs = Math.abs(arr[right]);
if (leftAbs > rightAbs) {
result[pos] = leftAbs * leftAbs;
left++;
} else {
result[pos] = rightAbs * rightAbs;
right--;
}
pos--;
}
return result;
}
public static void main(String[] args) {
int[] pnl = {-7, -3, 2, 5, 8};
System.out.println("Sorted squares: " + Arrays.toString(sortedSquares(pnl)));
}
}
Sorted squares: [4, 9, 25, 49, 64]
Why do the largest squares sit at the ends?
In a sorted array with negatives, the most negative value sits at the far left and the most positive sits at the far right. Their absolute values are the largest in the array, so their squares are the largest. The smallest absolute value, and thus the smallest square, sits somewhere in the middle near the transition from negative to positive.
package com.bank.core;
public class EndMagnitudes {
public static void main(String[] args) {
int[] arr = {-10, -5, -2, 1, 3, 8};
System.out.println("Left end magnitude: " + Math.abs(arr[0]));
System.out.println("Right end magnitude: " + Math.abs(arr[arr.length - 1]));
System.out.println("Smallest magnitude near middle: " + Math.abs(arr[3]));
}
}
Left end magnitude: 10
Right end magnitude: 8
Smallest magnitude near middle: 1
How is filling from the back different from filling from the front?
Filling from the back means placing the largest square first and working down. This naturally produces a sorted result because at each step the largest remaining square is always at one of the two ends. Filling from the front would require finding the smallest square first, which is somewhere in the middle and harder to locate efficiently.
package com.bank.core;
import java.util.Arrays;
public class FillDirection {
public static void main(String[] args) {
int[] arr = {-7, -3, 2, 5, 8};
int n = arr.length;
int[] result = new int[n];
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
System.out.println("left=" + left + "(" + arr[left] + ") right=" + right
+ "(" + arr[right] + ") → filling pos=" + pos);
int lAbs = Math.abs(arr[left]), rAbs = Math.abs(arr[right]);
if (lAbs > rAbs) { result[pos] = lAbs * lAbs; left++; }
else { result[pos] = rAbs * rAbs; right--; }
pos--;
}
System.out.println("Result: " + Arrays.toString(result));
}
}
left=0(-7) right=4(8) → filling pos=4 left=0(-7) right=3(5) → filling pos=3 left=1(-3) right=3(5) → filling pos=2 left=1(-3) right=2(2) → filling pos=1 left=2(2) right=2(2) → filling pos=0 Result: [4, 9, 25, 49, 64]
Why is the two-pointer approach better than sort-after-square?
Squaring every element then sorting costs O(n log n). The two-pointer approach is O(n) because it exploits the existing sorted order. For large arrays this difference matters.
| Approach | Time | Space | Preserves order? |
|---|---|---|---|
| Square then sort | O(n log n) | O(1) in-place sort | No, needs re-sort |
| Two-pointer fill-from-back | O(n) | O(n) for result | Yes |
package com.bank.core;
import java.util.Arrays;
public class NaiveVsTwoPointer {
public static int[] naiveApproach(int[] arr) {
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
result[i] = arr[i] * arr[i];
}
Arrays.sort(result); // O(n log n)
return result;
}
public static void main(String[] args) {
int[] arr = {-7, -3, 2, 5, 8};
System.out.println("Naive: " + Arrays.toString(naiveApproach(arr)));
}
}
Naive: [4, 9, 25, 49, 64]
What about integer overflow?
Squaring large values can overflow a 32-bit integer. For example, squaring 50,000 gives 2,500,000,000 which exceeds Integer.MAX_VALUE. Use long for the square or cast before multiplying.
package com.bank.core;
import java.util.Arrays;
public class SquareOverflow {
public static long[] sortedSquaresLong(int[] arr) {
int n = arr.length;
long[] result = new long[n];
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
long lAbs = Math.abs((long) arr[left]);
long rAbs = Math.abs((long) arr[right]);
if (lAbs > rAbs) { result[pos] = lAbs * lAbs; left++; }
else { result[pos] = rAbs * rAbs; right--; }
pos--;
}
return result;
}
public static void main(String[] args) {
int[] large = {-50000, -30000, 20000, 40000};
System.out.println("Long squares: " + Arrays.toString(sortedSquaresLong(large)));
}
}
Long squares: [400000000, 900000000, 1600000000, 2500000000]
What if all elements are non-negative?
If the array has no negatives, squaring preserves the sorted order and a simple left-to-right pass is sufficient. The two-pointer approach still works correctly in this case, but the left pointer never moves because the right end always has the larger magnitude.
package com.bank.core;
import java.util.Arrays;
public class AllPositive {
public static int[] simpleSquare(int[] arr) {
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
result[i] = arr[i] * arr[i];
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println("Simple: " + Arrays.toString(simpleSquare(arr)));
}
}
Simple: [1, 4, 9, 16, 25]
What are the edge cases?
Edge cases include a single-element array, all negatives, all zeros, and an array with one negative and one positive.
package com.bank.core;
import java.util.Arrays;
public class SquareEdgeCases {
public static int[] sortedSquares(int[] arr) {
int n = arr.length;
int[] result = new int[n];
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
int lAbs = Math.abs(arr[left]), rAbs = Math.abs(arr[right]);
if (lAbs > rAbs) { result[pos] = lAbs * lAbs; left++; }
else { result[pos] = rAbs * rAbs; right--; }
pos--;
}
return result;
}
public static void main(String[] args) {
System.out.println("Single: " + Arrays.toString(sortedSquares(new int[]{-3})));
System.out.println("All neg: " + Arrays.toString(sortedSquares(new int[]{-5, -3, -1})));
System.out.println("All zero: " + Arrays.toString(sortedSquares(new int[]{0, 0, 0})));
System.out.println("Mixed: " + Arrays.toString(sortedSquares(new int[]{-2, 3})));
}
}
Single: [9]
All neg: [1, 9, 25]
All zero: [0, 0, 0]
Mixed: [4, 9]
What should a senior engineer know?
A senior engineer should explain why the largest squares sit at the ends rather than just stating the algorithm. They should also mention the overflow risk and the O(n) versus O(n log n) distinction. In production financial code at the National Bank of India, squared magnitudes of P&L figures are used for variance and volatility calculations, and using BigDecimal for precision is the standard practice.
Visual Overview
Input: [-7, -3, 2, 5, 8]
↑ ↑
left right
Step 1: |-7|=7 vs |8|=8 → 8 wins → result[4] = 64 right--
Step 2: |-7|=7 vs |5|=5 → 7 wins → result[3] = 49 left++
Step 3: |-3|=3 vs |5|=5 → 5 wins → result[2] = 25 right--
Step 4: |-3|=3 vs |2|=2 → 3 wins → result[1] = 9 left++
Step 5: |2|=2 vs |2|=2 → 2 wins → result[0] = 4 right--
Result: [4, 9, 25, 49, 64] ← sorted!
┌────────────────────────────────────────┐
│ Fill direction: ←──── back to front │
│ result: [_, _, _, _, 64] │
│ result: [_, _, _, 49, 64] │
│ result: [_, _, 25, 49, 64] │
│ result: [_, 9, 25, 49, 64] │
│ result: [4, 9, 25, 49, 64] │
└────────────────────────────────────────┘
Key Takeaway
Squaring a sorted array that may contain negative numbers is trickier than it first looks, because a large negative value squared can be bigger than a small positive value squared. That means the largest squared values live at the two ends of the sorted array, and the smallest square is somewhere in the middle near the transition from negative to positive.
The efficient solution uses two pointers, one at each end of the input, and builds the result array from the back toward the front. At each step you compare the magnitudes of the two end values, square whichever is larger, place that square in the next slot from the back, and move that end's pointer inward. Because the largest remaining square is always at one of the two ends, filling the result from the last slot backward produces a fully sorted array in a single linear pass.
In Rajesh's work at the National Bank of India, the risk desk keeps daily profit-and-loss figures in a sorted array where losses are negative and profits are positive. The desk needs squared magnitudes sorted for a volatility measure, and with millions of figures across many books, squaring and re-sorting each time is too slow. The two-pointer linear method keeps the computation within the latency budget.
The senior-level details are about correctness and overflow. You compare magnitudes rather than raw values because the sign does not matter for the square, and you cast to a wider type before multiplying so that squaring large figures does not overflow. If the array has no negatives, squaring preserves order and a plain left-to-right pass works, but the moment negatives appear, the two-ended fill-from-the-back technique is the right tool.
Remember one sentence: compare magnitudes at both ends, square the bigger, and fill the result from back to front for O(n) sorted squares.
---