Squares of a Sorted Array

Squares of a Sorted Array

Question:

Given an integer array nums sorted in increasing order, find the squares of sorted array. Square the each number in input array and return them in sorted order.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in increasing order.

Example 1:

Input: nums = [1,4,5,10]

Output: [1,16,25,100]

Explanation: After squaring the each number (1*1 = 1, 4*4 = 16 and so on) numbers are in increasing order.

By looking at the example you can say that, since the input is sorted ,we can square the numbers from the start to end. But the catch is, input can contain negative number. So this approach doesn’t work. Look at the below example.

Example 2:

Input: nums = [-4,-1,0,3,10]

Output: [0,1,9,16,100]

 

One approach is squaring each number and sorting the array. For Example, Input:[-4,-1,0,3,10] After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100]. The time complexity of this solution is O(n+n*logn). O(n) for squaring each number and O(n*logn) for sorting numbers.
O(n) + O(n*logn) = O(n+nlogn)

Interviewer might ask you to solve the question in O(n). Is there any effecient way to solve in O(n) time complexity? Yes.

Two Pointers Approach:

We need to use the concept of Two Pointers to find the squares of sorted array. What is Two Pointer? In Two Pointers technique, we maintain two pointers to the array. Each pointer moves in different direction.In the input, we have both negative and positive numbers, so we maintain one pointer for negative side and another one for positive side.

Step 1:


Step 2:


Step 3:


Step 4:

 


Step 5:


Step 6:


Squares of Sorted Array Logic:

  1. First find the first positive number in the sorted array.
  2. Place the right/positive ptr at that position and left/negative ptr one step behind.
  3. Square both left ptr number and right ptr number.
  4. Compare the squared numbers.
  5.  Move the left ptr if the square of the elment is smaller than square of element in right ptr. If not move the right ptr.
  6. Repeat the same till we cover all the elements of array.

class Solution {
    public int[] sortedSquares(int[] nums)
    {
        int[] result = new int[nums.length];
        int firstPositive = nums.length-1;

	// Traversing array to find first postive
        for(int i =0; i<nums.length; i++)
        {
            if(nums[i]>=0)
            {
                firstPositive = i;
                break;
            }
        }
        int rightPtr = firstPositive;
        int leftPtr = firstPositive -1;
        for(int i=0; i<nums.length; i++)
        {
            //Both left ptr and right ptr should be withing array range
            if(leftPtr >=0 && rightPtr < nums.length)
            {
                int leftsq = nums[leftPtr]*nums[leftPtr];
                int rightsq = nums[rightPtr]*nums[rightPtr];
								 
                if(leftsq<rightsq)
                {
                    result[i] = leftsq;
                    leftPtr--;
                }
                else
                {
                    result[i] = rightsq;
                    rightPtr++;
                }
            }
						// Left pointer reached end, so adding elements from right  ptr
            else if(rightPtr < nums.length)
            {
                result[i] = nums[rightPtr] * nums[rightPtr];
                rightPtr++;
            }
						//Right pointer reached end, so adding elements from left ptr
            else if(leftPtr >=0)
            {
                result[i] = nums[leftPtr] * nums[leftPtr];
                leftPtr--;
            }
            
        }
        return result;
    }
}

 

You Might Also Like…

Maximum Subarray | Leetcode

Triplet Sum in Array | Amazon | Samsung

Thanks for reading 🙂 Share your thoughts in comments.

 

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
5 1 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x