Leetcode 977. Squares of a Sorted Array

Problem Explanation:

The problem is asking to return an array, sorted in non-decreasing order, of the squares of each number from the given sorted array. The time complexity should be O(n).

Example:

For Example, a given integer array is [-7,-3,2,3,11]. The squares of each number array would be [49,9,4,9,121] and after sorting it we would get [4,9,9,49,121].

Walk Through:

The solution is using the two-pointers technique. In this problem, the smallest square could be the first or the last element from the sorted array, because negatives square are positives. The solution arranges a new integer array, ans, with length of the number array, n, and initializes pointers at the start and end of the number array. While both pointers are not met, if the absolute value of the left pointer is greater than the right pointer, the solution squares the left pointer element, updates it and increments the left pointer. Else, it squares the right pointer element, updates it, and decrements the right pointer.

Python Solution:

1
2python
3class Solution:
4    def sortedSquares(self, nums):
5        n = len(nums)
6        ans = [0] * n
7        i, l, r = n -1, 0, n-1
8        while l <= r:
9            if abs(nums[l]) > abs(nums[r]):
10                ans[i] = nums[l]**2
11                l += 1
12            else:
13                ans[i] = nums[r]**2
14                r -= 1
15            i -= 1
16        return ans

Java Solution:

1
2java
3class Solution {
4    public int[] sortedSquares(int[] nums) {
5        int n = nums.length;
6        int[] ans = new int[n];
7        int i = n - 1, l = 0, r = n - 1;
8        while (l <= r) {
9            if (Math.abs(nums[l]) > Math.abs(nums[r])) {
10                ans[i] = nums[l] * nums[l];
11                l++;
12            } else {
13                ans[i] = nums[r] * nums[r];
14                r--;
15            }
16            i--;
17        }
18        return ans;
19    }
20}

JavaScript Solution:

1
2javascript
3class Solution {
4    sortedSquares(nums) {
5        const n = nums.length;
6        const ans = new Array(n);
7        let i = n - 1, l = 0, r = n - 1;
8        while (l <= r) {
9            if (Math.abs(nums[l]) > Math.abs(nums[r])) {
10                ans[i] = nums[l] * nums[l];
11                l++;
12            } else {
13                ans[i] = nums[r] * nums[r];
14                r--;
15            }
16            i--;
17        }
18        return ans;
19    }
20}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<int> sortedSquares(vector<int>& nums) {
6        const int n = nums.size();
7        vector<int> ans(n);
8        int i = n - 1;
9        for (int l = 0, r = n - 1; l <= r;)
10            if (abs(nums[l]) > abs(nums[r]))
11                ans[i--] = nums[l] * nums[l++];
12            else
13                ans[i--] = nums[r] * nums[r--];
14        return ans;
15    }
16};

C# Solution:

1
2csharp
3public class Solution {
4    public int[] SortedSquares(int[] nums) {
5        int n = nums.Length;
6        int[] ans = new int[n];
7        int i = n - 1, l = 0, r = n - 1;
8        while (l <= r) {
9            if (Math.Abs(nums[l]) > Math.Abs(nums[r])) {
10                ans[i] = nums[l] * nums[l];
11                l++;
12            } else {
13                ans[i] = nums[r] * nums[r];
14                r--;
15            }
16            i--;
17        }
18        return ans;
19    }
20}

Explanation:

The given solutions for this problem utilize a Two Pointer method. This method is proved to be efficient as both ends of the array are scanned simultaneously, reducing the time complexity to O(n).

Here, two pointers are maintained, one at the beginning and one at the end. Depending on which absolute value of the element is larger, that element's square is stored in a new array. This process continues till the pointers meet in the middle.

Following the same pattern, the Python, JavaScript, Java, C++, and C# solutions take the square of the elements and store them in the array based on conditionals that compare the absolute values.

Time Complexity:

As only one sweep of the array is required, the time complexity is O(n), where n is the number of elements in the given array.

Space Complexity:

The space complexity is also O(n) as a new array of size n is required to store the squared elements.

In conclusion, this Two Pointer method is not only efficient but also effective in solving the problem as it ensures the new array is sorted as required.

Always remember to consider practical time and space complexities based on the resources a programming language will use when implementing a solution. Therefore, always consider the most memory efficient and quick solution for tasks.


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 👨‍🏫