Two PointersEasyO(n) time · O(n) space

Squaring a Sorted Array

Mahabharata — The Archery Contest — Measuring Arrow Distances

दूरं निकटं च समं स्थितं यद् वर्गीकृतं तत् प्रबलं भवेत्। सीमाभ्यां मध्यं प्रति गच्छतां क्रमः प्रकाशो भवति स्वयम्॥

*Far and near, when squared, become comparable in magnitude. Let the boundaries approach the center, and order reveals itself.*

The Story

The tournament grounds of Hastinapura were arranged with mathematical precision. Dronacharya had designed a contest unlike any before: arrows would be shot from a central platform, and each arrow's distance from the center would determine its score.

But there was a twist. The final score was not the distance—it was the square of the distance. An arrow landing 3 units away scored 9. An arrow landing 5 units away scored 25. An arrow landing 4 units to the left scored 16, the same as one landing 4 units to the right.

"Why squares, Guru?" asked Duryodhana.

"Because squares reveal true magnitude," Drona replied. "A negative distance becomes positive when squared. All arrows count, whether they fall left or right of center."

The contest had just concluded. Arjuna had shot a magnificent sequence, and his arrows landed at these distances from center: [-4, -1, 0, 3, 10]. Negative meant left of center, positive meant right.

"Now compute the squared distances in sorted order," Drona commanded. "The judges need them ranked from least to greatest."

Duryodhana's archer calculated naively: "I'll square each distance first, getting [16, 1, 0, 9, 100], then sort them..."

"That requires a full sort!" Karna interjected. "O(n log n) operations. Surely there's a faster way?"

Arjuna smiled. He had noticed something crucial about the original array. "Gurudev, observe: the original distances are already sorted from most negative to most positive. When we square them, the largest squares will be at the extremes—either far left or far right. The smallest squares cluster near zero in the middle."

"So?" Duryodhana demanded.

"So I don't need to sort after squaring. I can build the sorted result directly by comparing extremes."

Arjuna picked up two flags—one red, one blue. He planted the red flag at the leftmost arrow (-4) and the blue at the rightmost arrow (10).

"I ask: which extreme has the larger square? |-4| = 4, |10| = 10. So 10² = 100 is larger. That goes at the end of my result."

He moved the blue flag one position left, now pointing to arrow at distance 3.

"Next comparison: |-4| = 4 versus |3| = 3. The left extreme wins. 4² = 16 goes next from the end."

He moved the red flag one position right, now pointing to arrow at distance -1.

"Continue: |-1| = 1 versus |3| = 3. Right extreme wins. 3² = 9."

The pattern continued: - Blue at 3, red at -1: 3 > 1, so 9 recorded, blue moves to 0 - Blue at 0, red at -1: 1 > 0, so 1 recorded, red moves to 0 - Both flags meet at 0: 0² = 0 recorded

The result array filled from right to left: [0, 1, 9, 16, 100]

"You see?" Arjuna explained. "The original array is sorted by actual value, but squares care only about magnitude. The largest magnitudes are at the edges. By comparing absolute values at both ends and placing the larger square at the back of the result, I fill the answer from largest to smallest—which means smallest to largest when read normally."

Drona nodded approvingly. "O(n) time. No sorting needed. The sorted property was hidden in plain sight—you simply had to recognize that extremes produce the largest squares."

Karna objected: "But this uses extra space for the result array!"

"True," Arjuna acknowledged. "But the problem requires a new sorted array of squares. The input is sorted by signed value; the output must be sorted by squared value. They're different orderings. Some extra space is inherent to the problem."

The judges recorded the technique, and it became standard in Hastinapura's mathematical archives: when squaring a sorted array that includes negative numbers, compare extremes, place the larger square at the result's end, and converge toward the center.

This is the Two Pointer technique for squaring a sorted array.

Duryodhana's First Instinct

Square each element, then sort the resulting array. This works but wastes the fact that the original array is sorted.

java

public int[] sortedSquaresBruteForce(int[] nums) {
    // Square each element
    int[] result = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        result[i] = nums[i] * nums[i];
    }
    
    // Sort the squared values
    Arrays.sort(result);  // O(n log n) wasted effort!
    
    return result;
}

Arjuna's Wisdom

Arjuna's insight: in a sorted array with negatives, the largest squared values are at the extremes (most negative or most positive). By using two pointers at both ends and comparing absolute values, we can fill the result array from the largest squared value (at the end) to the smallest (at the beginning). `left` tracks the most negative candidate, `right` tracks the most positive. We compare `|nums[left]|` with `|nums[right]|` and place the larger square at the current fill position (starting from the end).

java

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    
    // Arjuna's two flags
    int left = 0;           // Most negative extreme
    int right = n - 1;      // Most positive extreme
    int fillPos = n - 1;    // Fill result from the end
    
    while (left <= right) {
        int leftAbs = Math.abs(nums[left]);
        int rightAbs = Math.abs(nums[right]);
        
        if (leftAbs > rightAbs) {
            // Left extreme has larger magnitude
            result[fillPos] = leftAbs * leftAbs;
            left++;  // Move red flag right
        } else {
            // Right extreme has larger (or equal) magnitude
            result[fillPos] = rightAbs * rightAbs;
            right--;  // Move blue flag left
        }
        fillPos--;  // Next position to fill
    }
    
    return result;
}

// Test with Arjuna's arrow distances
public static void main(String[] args) {
    int[] distances = {-4, -1, 0, 3, 10};
    int[] squared = new Solution().sortedSquares(distances);
    System.out.println(Arrays.toString(squared));
    // Output: [0, 1, 9, 16, 100]
}

Step-by-Step Walkthrough

Array: [-4, -1, 0, 3, 10]
Result: [_, _, _, _, _]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: left=0 (-4), right=4 (10), fillPos=4
        |-4|=4 vs |10|=10
        10 > 4 → result[4] = 100, right--
        [-4, -1, 0, 3, 10]     Result: [_, _, _, _, 100]
          L           R→

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 2: left=0 (-4), right=3 (3), fillPos=3
        |-4|=4 vs |3|=3
        4 > 3 → result[3] = 16, left++
        [-4, -1, 0, 3, 10]     Result: [_, _, _, 16, 100]
         L→        R

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 3: left=1 (-1), right=3 (3), fillPos=2
        |-1|=1 vs |3|=3
        3 > 1 → result[2] = 9, right--
        [-4, -1, 0, 3, 10]     Result: [_, _, 9, 16, 100]
              L     R→

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 4: left=1 (-1), right=2 (0), fillPos=1
        |-1|=1 vs |0|=0
        1 > 0 → result[1] = 1, left++
        [-4, -1, 0, 3, 10]     Result: [_, 1, 9, 16, 100]
             L→  R

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 5: left=2 (0), right=2 (0), fillPos=0
        left == right, only one element left
        |0|=0 → result[0] = 0
        [-4, -1, 0, 3, 10]     Result: [0, 1, 9, 16, 100]
                LR

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: [0, 1, 9, 16, 100]

Deep Insight

**Why does this work?**

The key insight: for a sorted array with negatives, squaring creates a "valley" shape: - Large positive squares on the right (large positive numbers) - Large positive squares on the left (large negative numbers) - Small squares in the middle (numbers close to zero)

By taking from the extremes first, we always grab the next largest square.

**The invariant:** At any point, `nums[left..right]` contains the elements whose squares haven't been placed yet, and `result[fillPos+1..n-1]` contains the placed squares in sorted order (largest to smallest from left to right means smallest to largest from right to left).

**Edge cases:** - All positives: Left pointer barely moves, right does all the work - All negatives: Right pointer barely moves, left does all the work - Single element: Both pointers start equal, one comparison needed - All zeros: Works fine, just places zeros

**Why fill from the end?** We're selecting largest first. Filling from the end means largest goes to position n-1, second largest to n-2, etc.—which is exactly sorted order.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n log n)	O(n)	Sorting dominates; wastes sorted input property
Optimal	O(n)	O(n)	Result array needed; one pass through input

Pattern Recognition

✅ Sorted array containing negatives
✅ Output requires a different ordering (squared values)
✅ Largest outputs come from the extremes of input
✅ "Sorted squares" or "non-decreasing order of squares"

**LeetCode Trigger Phrases:**
→ "sorted array of integers" + "squares in sorted order"
→ "non-decreasing order" + "square of each number"
→ "array sorted in increasing order" + "squares sorted"

Bhagavad Gita 14.24

समदुःखसुखः स्वस्थः समलोष्टाश्मकाञ्चनः। तुल्यप्रियाप्रियो धीरस्तुल्यनिन्दात्मसंस्तुतिः॥

Equal in pain and pleasure, self-contained, regarding a clod, a stone, and gold as equal; the same to the pleasant and unpleasant, firm—equal to criticism and praise of oneself.

Connection: The squaring operation treats -4 and +4 as equals—both become 16. Just as the enlightened person sees gold and clay with equanimity, the algorithm sees positive and negative distances as equivalent in magnitude. The two pointers don't favor left or right; they simply ask which has greater absolute value, treating all numbers with the same fair measure.