Sorting two arrays into one array in efficient way

Sorting two sorted square number array to single array

/**
 * inputs :
 * int[] a = { 100, 64, 36, 2 };
int[] b = { 1, 9, 36, 49, 81 };

output :

[1, 2, 9, 36, 36, 49, 64, 81, 100]

 */
package com.codecreeks.solutions;

import java.util.Arrays;

/**
 * @author Athul
 *
 */
public class SortingAlgorithm {

/**
* @param javacode
*/
public static void main(String[] javacode) {

int[] a = { 100, 64, 36, 2 };
int[] b = { 1, 9, 36, 49, 81 };

SortingAlgorithm algo = new SortingAlgorithm();
int[] output = algo.sort(a, b);
System.out.println(Arrays.toString(output));

}

private int[] sort(int[] a, int[] b) {
int bLen = b.length;
int aLen = a.length;
int len = aLen + bLen;
int aPtr = aLen - 1;
int bPtr = 0;

int[] output = new int[len];

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--;
}

}

return output;
}

}

One of the biggest mistakes we all make is thinking we need more time than we actually do.

- Admond Lee Kin Lim

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.