977. Squares of a Sorted Array

EasyArrayTwo PointersSorting
Leetcode Link

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:

  1. We create two pointers, i at the start of the array and j at the end.
  2. We also create an array res of the same length as nums to store our results.
  3. We iterate from the end of the res array backward, deciding whether the square of nums[i] or nums[j] should occupy the current position based on which one is larger. This ensures that the largest square is placed at the end of res array first.
  4. We move pointer i to the right if nums[i] squared is greater than nums[j] squared since we have already placed the square of nums[i] in the result array.
  5. Similarly, we move pointer j to the left if the square of nums[j] is greater to ensure we are always placing the next largest square.
  6. We continue this process until all positions in res are filled with the squares of nums in non-decreasing order.
  7. Finally, the res array is returned.

Learn more about Two Pointers and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

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:

  1. Initialize pointers and an array: A pointer i is initialized to the start of the array (0), a pointer j is initialized to the end of the array (n - 1 where n is the length of the array), and an array res of the same length as nums is created to store the results.

  2. Iterate to fill result array: A loop is used, where the index k starts from the end of the res array (n - 1) and decrements with each iteration. The while loop continues until i is greater than j, which means all elements have been considered.

  3. Compare and place squares: During each loop iteration, the solution compares the squares of the values at index i and j (nums[i] * nums[i] vs nums[j] * nums[j]) to decide which one should be placed at the current index k of the res array. The larger square is placed at res[k], and the corresponding pointer (i or j) is moved.

    • If nums[i] * nums[i] is greater than nums[j] * nums[j], this means that the square of the number pointed to by i is currently the largest remaining square, so it's placed at res[k], and i is incremented to move to the next element from the start.

    • Conversely, if nums[j] * nums[j] is greater than or equal to nums[i] * nums[i], then nums[j] squared is placed at res[k], and j is decremented to move to the next element from the end.

  4. Decrement k: After each iteration, k is decremented to fill the next position in the res array, starting from the end and moving towards the start.

  5. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

Example 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:

  1. Initialize pointers and an array: We initialize i to 0, j to 3 (since there are four elements, n - 1 = 3), and an array res with the length of 4 to store the results: res = [0, 0, 0, 0].

  2. Iterate to fill result array: We start a while loop with k = 3, which is the last index in the res array.

  3. Compare and place squares:

    • First iteration: nums[i] is -3, nums[j] is 4.
    • Squares: nums[i] * nums[i] = 9, nums[j] * nums[j] = 16.
    • Since 16 is greater than 9, we place 16 at res[k]: res = [0, 0, 0, 16].
    • Decrement j to 2 and k to 2.

  4. Next iteration:

    • Now i = 0 (with nums[i] = -3), j = 2 (with nums[j] = 1).
    • Squares: nums[i] * nums[i] = 9, nums[j] * nums[j] = 1.
    • 9 is greater than 1, so we place 9 at res[k]: res = [0, 0, 9, 16].
    • Increment i to 1 and decrement k to 1.

  5. Next iteration:

    • Now i = 1 (with nums[i] = -2), j = 2 (with nums[j] = 1).
    • Squares: nums[i] * nums[i] = 4, nums[j] * nums[j] = 1.
    • 4 is greater than 1, so we place 4 at res[k]: res = [0, 4, 9, 16].
    • Increment i to 2 and decrement k to 0.

  6. Final iteration:

    • Now i = 2 (with nums[i] = 1), j = 2 (with nums[j] = 1), and k = 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].

  7. 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
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

Sorting Summary

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫