Data Structures && Algo Problems-1

Question-1(asked in Facebook)

Given a sorted array find the square sorted array out of it.

Input elements int [] array={-6,-5,-4,1,2,3,4}

Output  {1 ,4 ,9 ,16 ,25 ,25 ,36 }

Answer

• Now we are stated that we will be given a sorted array as input.
• Now simply squaring that will change the elements value and that array wont be sorted anymore.
• So squaring the element gives you 36,25,16,1,4,9,64 so that wont be sorted anymore
• Now the key is how to perform this kind of problems with optimal solution
• We will try to solve this problem by O(n) time complexity
• We will use some extra space complexity.

So know the key thing is each one of us knows that we will simply first square the elements 

and will apply the sort taking the sort function by Arrays.sort(array) but lets make this problem optimal in a single go..!!

So firstly will traverse the array taking the left pointer and the right pointer

like {-6,-5,-4,1,2,3,4}

          ^                    ^

         left                 Right

Now will use Math.abs(value) as we have negative values as well so we need to compare right and the left values one by one 

Case-1

we have left>right so will square the left value and and will make the pointer pointing towards the next node and will store the squared value in an another array at last index.

Case-2

Like wise if right>left will square the right index value and will decrease the right pointer by one and will start storing the squared values in an array from the last index

So here is the code which follows this methodology

 int[] num = {-6,-5,1,2,3,4,5 };
 int[] result = new int[num.length];
 int left = 0;
 int right = num.length - 1;
 for (int i = num.length - 1; i >= 0; i--) {
 	if (Math.abs(num[left]) > Math.abs(num[right])) {
 		result[i] = num[left] * num[left];
 		left++;
 	} else {
 		result[i] = num[right] * num[right];
 		right--;
 	}
 }

 for (int i: result) {
 	System.out.println(i);
 }

This is 100 % running code you can give suggestions in comments if any thanks..!!