Squaring and Sorting an input array contains negative and positive number

Questions asked in hackerearth and codeforgeeks

/**
 * Squaring and Sorting an input array contains negative and positive number
 *
 * Complexity O(2n)
 *
 */
package com.konzerntech.kozhikode;

import java.util.Arrays;

/**
 * @author Consumerfed Information Technology Section kozhikode
 * +91 8281 8080 29
 */
public class SquareAndSort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int[] input = { -10, -8, -3, -1, 4, 6, 8 };
int len = input.length;
int[] output = new int[len];

int[] a = new int[len];
int[] b = new int[len];

int aLen = 0;
int bLen = 0;

for (int i = 0; i < len; i++) {
int value = input[i];
int square = value * value;
if (value < 0) {
a[aLen] = square;
aLen++;
} else {
b[bLen] = square;
bLen++;
}
}


int aPtr = aLen-1;
int bPtr = 0;


for (int i = 0; i < len; i++) {

if (bPtr > (bLen - 1)) {
while (aPtr >= 0) {
output[i] = a[aPtr];
i++;
aPtr--;
}
break;
}

if (aPtr < 0) {
while (bPtr < bLen) {
output[i] = b[bPtr];
i++;
bPtr++;
}
break;
}

if (b[bPtr] < a[aPtr]) {
output[i] = b[bPtr];
bPtr++;
} else {
output[i] = a[aPtr];
aPtr--;
}

}
System.out.println("Input : "+Arrays.toString(input));
System.out.println("Output : "+Arrays.toString(output));

}

}

Output

Input : [-10, -8, -3, -1, 4, 6, 8]

Output : [1, 9, 16, 36, 64, 64, 100]

Description :

Squaring and Sorting is petty tricky problem.

The array may contains both negative as well as positive integer values, so while square the array the output may not be a sorted one.

So what we did here is we divided the input array into two based on the negative and positive values after squaring it.

Then we compare the two array n th position of one array to the zero th position of the other to find the minimum value, thus found minimum value is inserted into output array.

we used pointer to point each elements in array.