977. Squares of a Sorted Array

Squares of a Sorted Array (LeetCode 977) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

How to solve Squares of a Sorted Array

Squares of a Sorted Array is a Converging Two Pointers problem, part of Two Pointers. Learn converging two pointers for sorted arrays. Solve two sum, three sum, and container problems efficiently.

Work towards the solution in these steps:

  1. Consider how the properties of the sorted input array can help you avoid sorting after squaring each element.
  2. Think about using two pointers starting at opposite ends of the array to compare absolute values.
  3. Reflect on how the largest square will come from the largest absolute value at either end of the array.

The reference solution runs in O(n) time and O(1) space.

The Squares of a Sorted Array solution and editorial walks through the full approach with reference code.

Problem statement

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

- -10^4 <= 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?

Topics and companies

Topics: Array, Two Pointers, Sorting.

Reported in interviews at Facebook, Uber, Google, Amazon, Apple, Bloomberg, Yandex, Microsoft, ByteDance, Flipkart, Cisco.

How to practise Squares of a Sorted Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Squares of a Sorted Array in the code editor, or read the Squares of a Sorted Array editorial for a worked solution with its approach and complexity analysis.

Where Squares of a Sorted Array sits in the DSA pattern sheet

Problems related to Squares of a Sorted Array

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

Squares of a Sorted Array FAQ

What is the LeetCode number of Squares of a Sorted Array?

Squares of a Sorted Array is LeetCode problem 977, rated Easy.

What pattern is used to solve Squares of a Sorted Array?

Squares of a Sorted Array is a Converging Two Pointers problem. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

What is the time complexity of Squares of a Sorted Array?

The reference solution runs in O(n) time and O(1) space.

Which companies ask Squares of a Sorted Array?

Squares of a Sorted Array has been reported in interviews at Facebook, Uber, Google, Amazon, Apple, Bloomberg, Yandex, Microsoft, ByteDance, Flipkart, Cisco.

Preparing this workspace.