We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Squares of a Sorted Array

Number: 1019

Difficulty: Easy

Paid? No

Companies: Uber, Meta, Amazon, Google, Yandex, Bloomberg, Microsoft, Oracle, Agoda, Apple, Yahoo, Walmart Labs, Tinkoff

Problem Description

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

Key Insights

  • Squaring numbers can disrupt the original order since negative numbers become positive.
  • A two-pointer approach can efficiently retrieve the largest square from either end of the array.
  • By comparing the absolute values at the two pointers, the largest square is inserted from the back of the result array.
  • This method achieves an O(n) time complexity without needing to sort the squared values afterward.

Space and Time Complexity

Time Complexity: O(n) - We traverse the array only once.
Space Complexity: O(n) - We use an extra array to store the output.

Solution

We use a two-pointer technique to traverse the array from both ends. Initialize pointers (left and right) at the beginning and end of the array, respectively, and an index pointer starting at the end of a new results array. At each step, compare the absolute values of the elements at the left and right pointers. The larger absolute value, when squared, is placed in the result array at the current index, and the corresponding pointer is adjusted. This continues until the left pointer exceeds the right pointer. Filling the result array from the back ensures that the array remains sorted in non-decreasing order.

Code Solutions

# Function to return squares of a sorted array in non-decreasing order.
def sortedSquares(nums):
    # Initialize two pointers at the start and end of the array.
    left, right = 0, len(nums) - 1
    # Create a result array of the same length as nums.
    result = [0] * len(nums)
    # Index to insert the largest square at the current position.
    position = len(nums) - 1
    
    # Loop until the left and right pointers cross.
    while left <= right:
        # Compare absolute values at the left and right pointers.
        if abs(nums[left]) > abs(nums[right]):
            result[position] = nums[left] * nums[left]
            left += 1  # Move left pointer rightward.
        else:
            result[position] = nums[right] * nums[right]
            right -= 1  # Move right pointer leftward.
        position -= 1  # Move to the next insertion position.
    return result

# Example usage:
print(sortedSquares([-4, -1, 0, 3, 10]))  # Output: [0, 1, 9, 16, 100]
← Back to All Questions