LeetCode #977 Squares of a Sorted Array Solution & Explanation

Problem Description

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number 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?

Solution

When I saw this question, my first thought was to loop through, square each element, and then sort. I thought it was too simple.

C# Solution

⚠️Solution1

public class Solution {
    public int[] SortedSquares(int[] nums) {
        for(int i=0; i<nums.Length; i++){
            nums[i]*=nums[i];
        }

        Array.Sort(nums);

        return nums;
    }
}

Time Complexity : O(n log n)

⚠️Solution1.1 – LINQ

public class Solution {
    public int[] SortedSquares(int[] nums) {
        var newNums = nums.Select(x => x * x).ToArray();

        Array.Sort(newNums);

        return newNums;
    }
}

Time Complexity : O(n log n)

When faced with the time complexity constraint in the follow-up, it’s important to search for an approach that can solve the problem within a single loop.

I thought about using the concept of two pointers to tackle this problem. We set up two pointers to initially point to the beginning and end of the array. Then, in each iteration of the loop, we compare the absolute values of the elements pointed to by these pointers.

Since the array is sorted, we don’t need to worry about elements suddenly becoming larger or smaller. Instead, we can simply compare the absolute values of the elements. This allows us to accurately determine which element has a larger square value. Therefore, we calculate the square of the element with the larger absolute value and add it to the new array. We fill the new array starting from the last position and moving backwards.

⭐Solution2 – two pointers

public class Solution {
    public int[] SortedSquares(int[] nums) {
        
        int i = 0;
        int j = nums.Length-1;
        int nowIdx = nums.Length-1;
        int[] newNums = new int[nums.Length];

        while(i<=j){
            var iNum = nums[i];
            var jNum = nums[j];

            if(Math.Abs(iNum)>Math.Abs(jNum)){
                newNums[nowIdx] = iNum*iNum;
                i+=1;
            }
            else {
                newNums[nowIdx] = jNum*jNum;
                j-=1;
            }
            nowIdx-=1;
        }

        return newNums;
    }
}

Time Complexity : O(n)

The advantage of this method is that it requires only one loop to complete all operations, without the need for additional sorting of the new array. Thus, its time complexity is O(n), meeting the requirement in the follow-up and achieving the goal of solving the problem in linear time.

Java Solution

Solution1

class Solution {
    public int[] sortedSquares(int[] nums) {
        int i = 0;
        int j = nums.length-1;
        int nowIdx = nums.length-1;
        int[] newNums = new int[nums.length];

        while(i<=j){
            int iNum = nums[i];
            int jNum = nums[j];

            if(Math.abs(iNum)>Math.abs(jNum)){
                newNums[nowIdx] = iNum*iNum;
                i+=1;
            }
            else {
                newNums[nowIdx] = jNum*jNum;
                j-=1;
            }
            nowIdx-=1;
        }

        return newNums;
    }
}

Time Complexity : O(n)

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link: Squares of a Sorted Array – LeetCode

Some Random LeetCode posts