977. Squares of a Sorted Array LeetCode Solution

In this guide, you will get 977. Squares of a Sorted Array LeetCode Solution with the best time and space complexity. The solution to Squares of a Sorted Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Squares of a Sorted Array solution in C++
Squares of a Sorted Array solution in Java
Squares of a Sorted Array solution in Python
Additional Resources

977. Squares of a Sorted Array LeetCode Solution image

Problem Statement of Squares of a Sorted Array

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 <= 104
-104 <= nums[i] <= 104
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?

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

977. Squares of a Sorted Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> sortedSquares(vector<int>& nums) {
    const int n = nums.size();
    vector<int> ans(n);
    int i = n - 1;

    for (int l = 0, r = n - 1; l <= r;)
      if (abs(nums[l]) > abs(nums[r]))
        ans[i--] = nums[l] * nums[l++];
      else
        ans[i--] = nums[r] * nums[r--];

    return ans;
  }
};
/* code provided by PROGIEZ */

977. Squares of a Sorted Array LeetCode Solution in Java

class Solution {
  public int[] sortedSquares(int[] nums) {
    final int n = nums.length;
    int[] ans = new int[n];
    int i = n - 1;

    for (int l = 0, r = n - 1; l <= r;)
      if (Math.abs(nums[l]) > Math.abs(nums[r]))
        ans[i--] = nums[l] * nums[l++];
      else
        ans[i--] = nums[r] * nums[r--];

    return ans;
  }
}
// code provided by PROGIEZ

977. Squares of a Sorted Array LeetCode Solution in Python

class Solution:
  def sortedSquares(self, nums: list[int]) -> list[int]:
    n = len(nums)
    l = 0
    r = n - 1
    ans = [0] * n

    while n:
      n -= 1
      if abs(nums[l]) > abs(nums[r]):
        ans[n] = nums[l] * nums[l]
        l += 1
      else:
        ans[n] = nums[r] * nums[r]
        r -= 1

    return ans
 # code by PROGIEZ