977. Squares of a Sorted Array

🟩 Easy

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

Example 1

Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].

Example 2

Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]

Constraints

• 1 <= nums.length <= 10^4

• -104 <= nums[i] <= 10^4

• nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Solution

My Solution

func sortedSquares(nums []int) []int {
    l, r := 0, len(nums)-1
    resp := make([]int, 0, len(nums))

    for l <= r {
        if nums[l]*nums[l] >= nums[r]*nums[r] {
            resp = append(resp, nums[l]*nums[l])
            l++
        } else {
            resp = append(resp, nums[r]*nums[r])
            r--
        }
    }

    for i, j := 0, len(resp)-1; i < j; i, j = i+1, j-1 {
        resp[i], resp[j] = resp[j], resp[i]
    }

    return resp
}

Optimal Solution (Two Pointers)

func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1
    
    // Fill array from end to start
    for i := n-1; i >= 0; i-- {
        if abs(nums[left]) > abs(nums[right]) {
            result[i] = nums[left] * nums[left]
            left++
        } else {
            result[i] = nums[right] * nums[right]
            right--
        }
    }
    
    return result
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Approach

This solution uses a two-pointer technique to build the sorted squared array:

1. Key Observation:

   • In a sorted array, largest squares will come from either:

     • Largest positive numbers (at the end)

     • Largest absolute negative numbers (at the start)

2. Two-Pointer Strategy:

   • Left pointer at start (for negative numbers)

   • Right pointer at end (for positive numbers)

   • Compare absolute values to decide which square is larger

3. Result Construction:

   • Build result array from end to start

   • Place larger squares first

   • Move pointers accordingly

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array

• Each element processed exactly once

• No sorting required

• All operations are O(1)

Space Complexity: O(n)

• Result array of size n

• Only constant extra space besides output:

  • Two pointers (left, right)

  • Loop counter

  • Temporary variables for calculations

Why it works

• Array Properties:

  • Input array is sorted

  • Squares of numbers follow a U-shaped pattern

  • Largest squares are at the extremes

• Two-Pointer Benefits:

  • No need to sort after squaring

  • Directly builds sorted result

  • Handles both positive and negative numbers efficiently

• Optimization Details:

  • Pre-allocating result array avoids resizing

  • Building from end eliminates need for reversal

  • Absolute value comparison ensures correct ordering

result

Leetcode: link