Day 8

Welcome to 100 Days of Leetcode Challenge.

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

How to approach this problem?

It’s a very interesting problem. When we look at the question, the first thing which comes to our mind is Sorting (Arrays.Sort()). That’s the good approach but not the best approach. Because Arrays.Sort() method takes O(nlogn) time complexity.

So without using Arrays.Sort() method how can we solve this problem.

There is one best way, which helps to solve this problem with O(n) time complexity, it’s much better than Arrays.Sort() – O(nlogn) time complexity.

That’s the Two Pointer Approach.

Solution

C# Program

public class Solution {

    public int[] SortedSquares(int[] A) {
        
        int frontPointer = 0, lastPointer = A.Length-1,n = A.Length;
        
        int[] result = new int[n];
        
        for(int index = n-1; index >= 0; index--)
        {
            if(Math.Abs(A[frontPointer]) > Math.Abs(A[lastPointer]))
            {
                result[index] = A[frontPointer] * A[frontPointer];
                frontPointer++;
            }
            else{
                result[index] = A[lastPointer] * A[lastPointer];
                lastPointer--;
            }
        }
        
        return result;
    }
}

Take two pointers, place one pointer at the first position of the array and another pointer at the last position of the array.

Construct the result array. Use index, which points last position of the result array.

Compare first pointer position of array element with the last pointer of array element. If it is larger than last pointer of array element, then store the squared value of that array element in result array.

Repeat the same process again and again. Look at my solution for brief understanding.

That’s all about Squares of Sorted Array.

Time Complexity : O(n)

Time complexity is reduced to O(n), because here we didn’t used any Arrays.Sort() method. Just we solved the problem with Two pointer approach.

Space Complexity : O(n)

It denotes the result array, which we processed using that.