977. Squares of a Sorted Array
Problem Description
The problem provides us with an array of integers nums
that is sorted in non-decreasing order. Our task is to return an array containing the squares of each element from the nums
array, and this resulting array of squares should also be sorted in non-decreasing order. For example, if the input is [-4, -1, 0, 3, 10]
, after squaring each number, we get [16, 1, 0, 9, 100]
and then we need to sort this array to get the final result [0, 1, 9, 16, 100]
.
Intuition
Given that the input array is sorted in non-decreasing order, we realize that the smallest squares might come from the absolute values of negative numbers at the beginning of the array as well as the positive numbers at the end. The key insight is that the squares of the numbers will be largest either at the beginning or at the end of the array since squaring emphasizes larger magnitudes whether they are positive or negative. Therefore, we can use a two-pointer approach:
- We create two pointers,
i
at the start of the array andj
at the end. - We also create an array
res
of the same length asnums
to store our results. - We iterate from the end of the
res
array backward, deciding whether the square ofnums[i]
ornums[j]
should occupy the current position based on which one is larger. This ensures that the largest square is placed at the end ofres
array first. - We move pointer
i
to the right ifnums[i]
squared is greater thannums[j]
squared since we have already placed the square ofnums[i]
in the result array. - Similarly, we move pointer
j
to the left if the square ofnums[j]
is greater to ensure we are always placing the next largest square. - We continue this process until all positions in
res
are filled with the squares ofnums
in non-decreasing order. - Finally, the
res
array is returned.
Learn more about Two Pointers and Sorting patterns.
Solution Approach
The solution makes use of a two-pointer approach, an efficient algorithm when dealing with sorted arrays or sequences. The steps of the algorithm are implemented in the following way:
-
Initialize pointers and an array: A pointer
i
is initialized to the start of the array (0
), a pointerj
is initialized to the end of the array (n - 1
wheren
is the length of the array), and an arrayres
of the same length asnums
is created to store the results. -
Iterate to fill result array: A loop is used, where the index
k
starts from the end of theres
array (n - 1
) and decrements with each iteration. Thewhile
loop continues untili
is greater thanj
, which means all elements have been considered. -
Compare and place squares: During each loop iteration, the solution compares the squares of the values at index
i
andj
(nums[i] * nums[i]
vsnums[j] * nums[j]
) to decide which one should be placed at the current indexk
of theres
array. The larger square is placed atres[k]
, and the corresponding pointer (i
orj
) is moved.-
If
nums[i] * nums[i]
is greater thannums[j] * nums[j]
, this means that the square of the number pointed to byi
is currently the largest remaining square, so it's placed atres[k]
, andi
is incremented to move to the next element from the start. -
Conversely, if
nums[j] * nums[j]
is greater than or equal tonums[i] * nums[i]
, thennums[j]
squared is placed atres[k]
, andj
is decremented to move to the next element from the end.
-
-
Decrement
k
: After each iteration,k
is decremented to fill the next position in theres
array, starting from the end and moving towards the start. -
Return the result: Once the
while
loop is done, all elements have been squared and placed in the correct position, resulting in a sorted array of squares which is then returned.
This approach uses no additional data structures other than the res
array to produce the final sorted array of squares. It is space-optimal, requiring O(n) additional space, and time-optimal with O(n) time complexity because it avoids the need to sort the squares after computation, which would take O(n log n) if a sorting method was used after squaring the elements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. We will use the input array nums = [-3, -2, 1, 4]
. Our goal is to compute the squares of each number and get a sorted array as a result. Here's how it works:
-
Initialize pointers and an array: We initialize
i
to0
,j
to3
(since there are four elements,n - 1 = 3
), and an arrayres
with the length of4
to store the results:res = [0, 0, 0, 0]
. -
Iterate to fill result array: We start a
while
loop withk = 3
, which is the last index in theres
array. -
Compare and place squares:
- First iteration:
nums[i]
is-3
,nums[j]
is4
. - Squares:
nums[i] * nums[i] = 9
,nums[j] * nums[j] = 16
. - Since
16
is greater than9
, we place16
atres[k]
:res = [0, 0, 0, 16]
. - Decrement
j
to2
andk
to2
.
- First iteration:
-
Next iteration:
- Now
i = 0
(withnums[i] = -3
),j = 2
(withnums[j] = 1
). - Squares:
nums[i] * nums[i] = 9
,nums[j] * nums[j] = 1
. 9
is greater than1
, so we place9
atres[k]
:res = [0, 0, 9, 16]
.- Increment
i
to1
and decrementk
to1
.
- Now
-
Next iteration:
- Now
i = 1
(withnums[i] = -2
),j = 2
(withnums[j] = 1
). - Squares:
nums[i] * nums[i] = 4
,nums[j] * nums[j] = 1
. 4
is greater than1
, so we place4
atres[k]
:res = [0, 4, 9, 16]
.- Increment
i
to2
and decrementk
to0
.
- Now
-
Final iteration:
- Now
i = 2
(withnums[i] = 1
),j = 2
(withnums[j] = 1
), andk = 0
. - There's only one element left, so we square it and place it at
res[k]
:nums[i] * nums[i] = 1
. res
becomes[1, 4, 9, 16]
.
- Now
-
Return the result: At the end of the loop, we have the final sorted array of squares
res = [1, 4, 9, 16]
.
Following these steps, we have successfully transformed the nums
array into a sorted array of squares without needing to sort them again after squaring. This approach efficiently uses the original sorted order to place the squares directly in the correct sorted positions.
Solution Implementation
1from typing import List
2
3class Solution:
4 def sortedSquares(self, nums: List[int]) -> List[int]:
5 # Get the length of the input array
6 length = len(nums)
7
8 # Initialize a result array of the same length as the input array
9 result = [0] * length
10
11 # Initialize pointers for the start and end of the input array,
12 # and a pointer for the position to insert into the result array
13 start_pointer, end_pointer, result_pointer = 0, length - 1, length - 1
14
15 # Loop through the array from both ends towards the middle
16 while start_pointer <= end_pointer:
17 # Square the values at both pointers
18 start_square = nums[start_pointer] ** 2
19 end_square = nums[end_pointer] ** 2
20
21 # Compare the squared values and add the larger one to the end of the result array
22 if start_square > end_square:
23 result[result_pointer] = start_square
24 start_pointer += 1
25 else:
26 result[result_pointer] = end_square
27 end_pointer -= 1
28
29 # Move the result pointer to the next position
30 result_pointer -= 1
31
32 # Return the sorted square array
33 return result
34
1class Solution {
2
3 // Method that takes an array of integers as input and
4 // returns a new array with the squares of each number sorted in non-decreasing order.
5 public int[] sortedSquares(int[] nums) {
6 int length = nums.length; // Store the length of the input array
7 int[] sortedSquares = new int[length]; // Create a new array to hold the result
8
9 // Initialize pointers for the start and end of the input array,
10 // and a pointer 'k' for the position to insert into the result array, starting from the end.
11 for (int start = 0, end = length - 1, k = length - 1; start <= end;) {
12 // Calculate the square of the start and end elements
13 int startSquare = nums[start] * nums[start];
14 int endSquare = nums[end] * nums[end];
15
16 // Compare the squares to decide which to place next in the result array
17 if (startSquare > endSquare) {
18 // If the start square is greater, place it in the next open position at 'k',
19 // then increment the start pointer.
20 sortedSquares[k--] = startSquare;
21 ++start;
22 } else {
23 // If the end square is greater or equal, place it in the next open position at 'k',
24 // then decrement the end pointer.
25 sortedSquares[k--] = endSquare;
26 --end;
27 }
28 }
29
30 // Return the array with sorted squares
31 return sortedSquares;
32 }
33}
34
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 vector<int> sortedSquares(vector<int>& nums) {
7 int size = nums.size();
8 vector<int> result(size); // This will store the final sorted squares of numbers
9
10 // Use two pointers to iterate through the array from both ends
11 int left = 0; // Start pointer for the array
12 int right = size - 1; // End pointer for the array
13 int position = size - 1; // Position to insert squares in the result array from the end
14
15 // While left pointer does not surpass the right pointer
16 while (left <= right) {
17 // Compare the square of the elements at the left and right pointer
18 if (nums[left] * nums[left] > nums[right] * nums[right]) {
19 // If the left square is larger, place it in the result array
20 result[position] = nums[left] * nums[left];
21 ++left; // Move the left pointer one step right
22 } else {
23 // If the right square is larger or equal, place it in the result array
24 result[position] = nums[right] * nums[right];
25 --right; // Move the right pointer one step left
26 }
27 --position; // Move the position pointer one step left
28 }
29
30 // Return the result which now contains the squares in non-decreasing order
31 return result;
32 }
33};
34
1/**
2 * Returns an array of the squares of each element in the input array, sorted in non-decreasing order.
3 * @param {number[]} nums - The input array of integers.
4 * @return {number[]} - The sorted array of squares of the input array.
5 */
6const sortedSquares = (nums: number[]): number[] => {
7 // n is the length of the input array nums.
8 const n: number = nums.length;
9
10 // res is the resulting array of squares, initialized with the size of nums.
11 const res: number[] = new Array(n);
12
13 // Two pointers approach: start from the beginning (i) and the end (j) of the nums array.
14 // The index k is used for the current position in the resulting array res.
15 for (let i: number = 0, j: number = n - 1, k: number = n - 1; i <= j; ) {
16 // Compare squares of current elements pointed by i and j.
17 // The larger square is placed at the end of array res, at index k.
18 if (nums[i] * nums[i] > nums[j] * nums[j]) {
19 // Square of nums[i] is greater, so store it at index k in res and move i forward.
20 res[k--] = nums[i] * nums[i];
21 ++i;
22 } else {
23 // Square of nums[j] is greater or equal, so store it at index k in res and move j backward.
24 res[k--] = nums[j] * nums[j];
25 --j;
26 }
27 }
28
29 // Return the sorted array of squares.
30 return res;
31};
32
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
. Each element in the nums
array is accessed once during the while loop. Despite the fact that there are two pointers (i, j) moving towards each other from opposite ends of the array, each of them moves at most n
steps. The loop ends when they meet or cross each other, ensuring that the total number of operations does not exceed the number of elements in the array.
Space Complexity
The space complexity of the code is O(n)
. Additional space is allocated for the res
array, which stores the result. This array is of the same length as the input array nums
. No other additional data structures are used that grow with the size of the input, so the total space required is directly proportional to the input size n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!