Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
public Integer[] sqArray(int[] arr)
{
ArrayList<Integer> arr_negetive = new ArrayList<Integer>();
ArrayList<Integer> arr_positive = new ArrayList<Integer>();
for(int i=0;i<arr.length;i++){
if(arr[i] < 0){
arr_negetive.add(arr[i] * arr[i]);
}
else{
arr_positive.add(arr[i] * arr[i]);
}
}
Integer[] array_result = new Integer[arr.length];
int n = arr_negetive.size()-1;//negetive counter
int p = 0;//positive counter
int count = 0;
while(count < arr.length)
{
System.out.println(p+","+n);
if(n < 0 && p < arr_positive.size())
{
array_result[count] = (arr_positive.get(p));
p++;
}
else if (p == arr_positive.size() && n >= 0)
{
array_result[count]=(arr_negetive.get(n));
n--;
}
else if(arr_negetive.get(n) < arr_positive.get(p))
{
array_result[count]=(arr_negetive.get(n));
n--;
}
else
{
array_result[count]=(arr_positive.get(p));
p++;
}
count++;
}
if(arr_negetive.size() == 0)
{
return arr_positive.toArray(new Integer[arr_positive.size()]);
}
else if( arr_positive.size() == 0)
{
return arr_negetive.toArray(new Integer[arr_negetive.size()]);
}
else
{
return array_result;
}
}
This is the best solution as it will run O(n)
Beating the horse...
Obvious naive solution is to square and sort, which is O(nlogn) time and O(1) assuming the sorting is performed in place.
Better solution is a play on merge sort to reach O(n) time and O(n) space because of the spare array.
Insane solution performs merge in place (someone posted the reference above) for O(1) space, but you'd be insane to implement the algorithm during an interview (or even outside of an interview).
Straight C version
static void merge(int *a, int len, int split, int *b)
{
int j = split;
int k = split+1;
for (int i = 0; i < len; i++)
a[i] = a[i] * a[i];
for (int i = 0; i < len; i++) {
if (j < 0)
b[i] = a[k++];
else if (k >= len)
b[i] = a[j--];
else if (a[k] < a[j])
b[i] = a[k++];
else
b[i] = a[j--];
}
}
static void squaresort(int *a, int len, int *b)
{
if (a[0] >= 0)
return merge(a, len, 0, b);
for (int i = 0; i < len-1; i++) {
if (a[i] < 0 && a[i+1] >= 0)
return merge(a, len, i, b);
}
return merge(a, len, len-1, b);
}
#include <stdio.h>
int main(int argc, char **argv)
{
int len = 8;
int a[8] = { -6, -5, -4, -3, 0, 1, 2, 3, };
int b[8];
squaresort(a, len, b);
for (int i = 0; i < len; i++)
printf("%i %i\n", i, b[i]);
return 0;
}
O(n) - single pass
int[] sortedSquare(int[] sortedArray)
{
var sortedSquare = new int[sortedArray.Length];
int front = 0;
int back = sortedArray.Length - 1;
int currentPos = sortedArray.Length - 1;
while(front <= back)
{
int frontSq = sortedArray[front] * sortedArray[front];
int backSq = sortedArray[back] * sortedArray[back];
if(frontSq <= backSq)
{
sortedSquare[currentPos--] = backSq;
--back;
}
else
{
sortedSquare[currentPos--] = frontSq;
++front;
}
}
return sortedSquare;
}
Notice that a sorted array with negative integers can be thought of as two sorted lists, one sorted from greatest abs value to lowest abs value, and the other sorted from lowest abs value to greatest abs value.
1) Use a merge method working from the start of the array for negative numbers, and the end of the array for positive numbers. Square the largest numbers, and use the resulting values when building a new array from largest to smallest value.
def sortedSquaredArray(sortedArray):
sqSortedArray = []
negIndex = 0
posIndex = len(sortedArray) - 1
while negIndex <= posIndex:
if (sortedArray[negIndex])**2 > (sortedArray[posIndex])**2:
sqSortedArray = [(sortedArray[negIndex])**2] + sqSortedArray
negIndex += 1
else:
sqSortedArray = [(sortedArray[posIndex])**2] + sqSortedArray
posIndex -= 1
if negIndex >= len(sortedArray) or sortedArray[negIndex] >= 0:
break
elif posIndex <= 0 or sortedArray[posIndex] <= 0:
break
if negIndex > posIndex:
return sqSortedArray
elif negIndex >= len(sortedArray) or sortedArray[negIndex] >= 0:
while posIndex >= negIndex:
sqSortedArray = [(sortedArray[posIndex])**2] + sqSortedArray
posIndex -= 1
return sqSortedArray
elif posIndex <= 0 or sortedArray[posIndex] <= 0:
while negIndex <= posIndex:
sqSortedArray = [(sortedArray[negIndex])**2] + sqSortedArray
negIndex += 1
return sqSortedArray
sortedData = [-3, -1, 0, 2, 5, 7]
sqSortedData = sortedSquaredArray(sortedData)
print('Orig: ' + str(sortedData))
print('Sqst: ' + str(sqSortedData))
C#, O(n) time, using List<>, could use arrays and still keep it to O(n) time
public static int[] SortedSquare(int[] inp)
{
List<int> negatives = new List<int>();
List<int> positives = new List<int>();
List<int> r = new List<int>();
for (int i = 0; i < inp.Length; i++)
{
if (inp[i] < 0)
{
negatives.Add(inp[i] * inp[i]);
}
else
{
positives.Add(inp[i] * inp[i]);
}
}
int p = 0;
int n = 0;
bool keepGoing = true;
while (keepGoing)
{
if (n < negatives.Count())
{
if (p < positives.Count())
{
if (negatives[n] < positives[p])
{
r.Add(negatives[n]);
n += 1;
}
else
{
r.Add(positives[p]);
p += 1;
}
}
else
{
{
r.Add(negatives[n]);
n += 1;
}
}
}
else
{
if (p < positives.Count())
{
r.Add(positives[p]);
p += 1;
}
else
{
keepGoing = false;
}
}
}
return r.ToArray();
}
}
/**
* Two pointer solution - 1st pointer points to the first +ve integer, second pointer points to the last -ve integer
* Implement merge routine like algorithm
* @param nums
* @return
*/
private int[] go(int[] nums){
int[] res = new int[nums.length];
int pos = Integer.MAX_VALUE;
int neg = -1;
for(int i=0;i<nums.length;i++){
if(nums[i] >= 0){
pos = Math.min(pos, i);
}
else{
neg = i;
}
}
int fill = 0;
while(neg >=0 || pos < nums.length){
if(neg >=0 && pos < nums.length){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
else{
res[fill++] = nums[pos]*nums[pos];
pos++;
}
}
return res;
}
/**
* Two pointer solution - 1st pointer points to the first +ve integer, second pointer points to the last -ve integer
* Implement merge routine like algorithm
* @param nums
* @return
*/
private int[] go(int[] nums){
int[] res = new int[nums.length];
int pos = Integer.MAX_VALUE;
int neg = -1;
for(int i=0;i<nums.length;i++){
if(nums[i] >= 0){
pos = Math.min(pos, i);
}
else{
neg = i;
}
}
int fill = 0;
while(neg >=0 || pos < nums.length){
if(neg >=0 && pos < nums.length){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
else{
res[fill++] = nums[pos]*nums[pos];
pos++;
}
}
return res;
}
/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}
/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}
/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}
/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}
public static void main(String args[]) {
final int[] numbers = {-9,-1,1,3,5};
PriorityQueue pq = squareOfSortedData(numbers);
while (!pq.isEmpty())
System.out.println(pq.poll() + ",");
}
public static PriorityQueue squareOfSortedData(final int[] data) {
PriorityQueue pq = new PriorityQueue();
if (data == null || data.length == 0) {
return pq;
}
for (int i = 0; i < data.length; ++i) {
pq.add(BigInteger.valueOf(data[i]).pow(2).intValue());
}
return pq;
}
O(n) solution
Use two pointers, back and front.
Increment front if sqaure > sqaure of back else decrement back. Fill the array from behind
int[] sortedSquare(int[] sortedArray)
{
var sortedSquare = new int[sortedArray.Length];
int front = 0;
int back = sortedArray.Length - 1;
int currentPos = sortedArray.Length - 1;
while(front <= back)
{
int frontSq = sortedArray[front] * sortedArray[front];
int backSq = sortedArray[back] * sortedArray[back];
if(frontSq <= backSq)
{
sortedSquare[currentPos--] = backSq;
--back;
}
else
{
sortedSquare[currentPos--] = frontSq;
++front;
}
}
return sortedSquare;
}
Like mentiones previosly con be solved in O(n) is an example of join two sorted lists
public static int[] GetSortedArrayOfSquares(int[] a)
{
if (a == null || a.Length == 0)
return a;
// Set I at the begining of positive numbers and J in the last negative number
int i=0;
while (a[i] < 0)
i++;
int j = i - 1;
int index = 0;
int[] result = new int[a.Length];
// Join both sorted lists
while (j >=0 && i < a.Length)
{
int n1 = a[i] * a[i];
int n2 = a[j] * a[j];
if (n1 <= n2)
{
result[index] = n1;
i++;
}
else
{
result[index] = n2;
j--;
}
index++;
}
// Copy the remainder
while (j >=0)
{
result[index] = a[j] * a[j];;
j--;
index++;
}
while (i < a.Length)
{
result[index] = a[i] * a[i];
i++;
index++;
}
return result;
}
// this is O(n) solution
void compute_sorted_squares(int *sqrs, int * arr, int num)
{
if ( !arr || (num < 1)) return;
int begin = 0;
int end = num - 1;
int change = -1;
int val;
int prev_val = arr[0];
for (int i = 0; i < num; i++) {
val = arr[i];
if ( prev_val < 0 && val > 0){
change = i;
}
prev_val = val;
}
/* all -ve or all +ve */
if (change == -1) {
for(int i = 0; i < num; i++) {
sqrs[i] = arr[i] * arr[i];
}
return;
}
int fwd = change;
int bwd = change - 1;
int pos = 0;
int dir = 0;
int dir_start = -1;
while ( pos < num ) {
int fwd_sqr = arr[fwd] * arr[fwd];
int bwd_sqr = arr[bwd] * arr[bwd];
if (bwd_sqr > fwd_sqr) {
sqrs[pos] = fwd_sqr;
fwd++;
} else {
sqrs[pos] = bwd_sqr;
bwd--;
}
pos++;
if ( bwd == -1 ) {
dir = 1;
dir_start = fwd;
break;
}
if ( fwd == num ) {
dir = -1;
dir_start = bwd;
break;
}
}
if ( dir != 0) {
for (int i = pos; i < num; i++) {
sqrs[i] = arr[dir_start] * arr[dir_start];
dir_start = dir_start + dir;
}
}
}
Couldn't you binary search to find the first positive number. Store this as stopping point, stp.
Create two pointers, one starting off at the 0th index(neg_idx), and the other starting at stp(pos_idx).
Then implement a merge like routine where you selct the minimum of the elements corresponding values. Insert the square of that in a new list, and increment the corresponding pointer.
Do this while the neg_idx < stp and pos_idx<arr.length;
This would run in O(n)
In-place O(n) solution-
public static void sortedSq(){
int[] a = {-7,-6,-2,0,3,4,6,8};
int r = a.length-1;
while(r>=0){
if(r == 0) {
a[r] = a[r]*a[r];
}
else if(a[0]*a[0] < a[r]*a[r]) {
a[r] = a[r]*a[r];
}else if(a[0]*a[0] >= a[r]*a[r]) {
int t = a[r];
a[r] = a[0]*a[0];
a[0] = t;
if(r>1 && Math.abs(a[1]) > a[0]) {
int tmp = a[0];
a[0] = a[1];
a[1] = tmp;
}
}
r--;
}
}
public static void sortedSq(){
int[] a = {-7,-6,-2,0,3,4,5,8};
int r = a.length-1;
while(r>=0){
if(r == 0) {
a[r] = a[r]*a[r];
}
else if(a[0]*a[0] < a[r]*a[r]) {
a[r] = a[r]*a[r];
}else if(a[0]*a[0] >= a[r]*a[r]) {
int t = a[r];
a[r] = a[0]*a[0];
a[0] = t;
if(r>1 && Math.abs(a[1]) > a[0]) {
int tmp = a[0];
a[0] = a[1];
a[1] = tmp;
}
}
r--;
}
}
Complexity:
O(n) time
O(1) space
class SquareOfSortedArray {
public static void main(String args[]) {
int []num = {-5,-4,-3,0,1,6,7,8};
//int []num = {-5,-3,-3,3};
//int []num = {1,2,3,4,5};
//int []num = {-5,-4,-3,-2, -1, 1,6,7,8};
//int []num = {-5};
squareSortedArrayConstantSpace(num);
for(int i: num) {
System.out.println(i);
}
}
static void squareSortedArrayConstantSpace(int []n) {
int len = n.length;
if(len <= 0)
return;
int i = 0;
int j = 0;
while(i < len) { //square all negative numbers, if any
n[i] = n[i] * n[i];
i++;
if(j == 0 && n[i] >= 0)
j = i; // Get the mid point from negative to positive
} // O(n)
i = j - 1; // Two pointer starting from mid (negative to positive)
int index = 0;
while(i >= 0 && i > index && j < len) {
if(n[j] > n[i]) {
swap(n, index, i);
i--;
} else {
swap(n, index, j);
j++;
}
index ++;
}
if(index < n.length && j < n.length) { // At this point all items till index are sorted, just compare n swap the remaining items starting from index
while(index < j) {
if(n[index] > n[j]) {
swap(n, index, j);
}
index++;
j--;
}
} // O(n) including the above while loop
}
static void swap(int []num, int i, int j) {
num[i] ^= num[j];
num[j] ^= num[i];
num[i] ^= num[j];
}
}
Trivial Answer in Kotlin
class Exersises {
companion object {
@JvmStatic fun main(args: Array<String> ){
val input = listOf(-4,-2,-1,2,4,10)
print ( toOrderedListOfSquares( input ))
}
fun toOrderedListOfSquares( originalArray: List<Int> ) : List<Int> {
val returnArray = originalArray.map { it * it }.toMutableList()
returnArray.sort()
return returnArray
}
}
}
An O(n) answer in Kotlin
class SortedSquares {
companion object {
@JvmStatic fun main(args: Array<String>) {
val original = listOf(-10, -6, -2, 1, 5, 12)
println(SortedSquares().sort(original))
}
}
private fun sort(original: List<Int>): List<Int> {
val (positive, negative) = original.partition { it > 0 }
val positiveSq = positive.map { it * it }
val negativeSq = negative.map { it * it }
val final = mutableListOf<Int>()
var positiveIndex = 0
var negativeIndex = negativeSq.size - 1
while (positiveIndex < positiveSq.size || negativeIndex >= 0) {
when {
positiveIndex >= positiveSq.size -> final.add(negativeSq[negativeIndex--])
negativeIndex < 0 -> final.add(positiveSq[positiveIndex++])
positiveSq[positiveIndex] > negativeSq[negativeIndex] -> final.add(negativeSq[negativeIndex--])
else -> final.add(positiveSq[positiveIndex++])
}
}
return final
}
}
/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })
val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }
var negInd: Int = 0
var posSqr: Int = 0
while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}
fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}
/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })
val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }
var negInd: Int = 0
var posSqr: Int = 0
while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}
fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}
/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })
val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }
var negInd: Int = 0
var posSqr: Int = 0
while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}
fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}
/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })
val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }
var negInd: Int = 0
var posSqr: Int = 0
while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}
fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}
Java solution with 2 pointers in O(N)
public int[] getSortedPowers(int[] nums] {
int[] sorted = new int[nums.length];
int i=0, j=nums.length-1, index = nums.length-1;
while (index >= 0) {
int left = Math.abs(nums[i]), right = Math.abs(nums[j]);
if (left > right) {
sorted[index] = left * left;
i++;
} else {
sorted[index] = right * right;
j--;
}
index--;
}
return sorted;
}
private static int[] power(int[] sortedArray) {
int start = -1;
for (int i = 0; i < sortedArray.length; i++) {
if (sortedArray[i] > 0) {
start = i;
break;
}
}
if (start < 0) {
start = sortedArray.length - 1;
}
int result[] = new int[sortedArray.length];
int left = start - 1;
int right = start;
int i = 0;
while (left >= 0 || right < sortedArray.length) {
if (left >= 0) {
int leftValue = -sortedArray[left];
if (right < sortedArray.length) {
int rightValue = sortedArray[right];
if (leftValue < rightValue) {
result[i++] = leftValue * leftValue;
left--;
} else {
result[i++] = rightValue * rightValue;
right++;
}
} else {
result[i++] = leftValue * leftValue;
left--;
}
} else {
if (right >= sortedArray.length) {
break;
} else {
int rightValue = sortedArray[right];
result[i++] = rightValue * rightValue;
right++;
}
}
}
return result;
}
function getSortedSquares(numbers) {
if (!numbers) {
return []
} else if (numbers[0] >= 0) {
return numbers.map(aNumber => aNumber * aNumber)
}
const squares = []
// find the first positive index, guaranteed to be > 0
let j = 0
while (numbers[j] < 0) {
j++
}
let i = j - 1
while (i >= 0 || j < numbers.length) {
if (i < 0) {
squares.push(numbers[j] * numbers[j])
j++
} else if (j === numbers.length) {
squares.push(numbers[i] * numbers[i])
i--
} else if (Math.abs(numbers[i]) < Math.abs(numbers[j])) {
squares.push(numbers[i] * numbers[i])
i--
} else {
squares.push(numbers[j] * numbers[j])
j++
}
}
return squares
}
console.log(getSortedSquares([-4, -2, 1, 3, 5]))
public class SquareOfSortedArray {
public static void main(String[] arg) {
int[] arr = { -5,-4,-3, -2, 1, 4, 5 ,7,8};
int positivePointer = Integer.MAX_VALUE;
int negativePointer = -1;
for (int i = 0; i < arr.length; i++) {
if ((arr[i] > 0)) {
positivePointer = Math.min(positivePointer, i);
} else {
negativePointer = i;
}
arr[i] = arr[i] * arr[i];
}
int m = 0;
int n = negativePointer;
while (m < n) {
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
m++;
n--;
}
//Arrays.sort(arr);
arr = merge(arr,0,positivePointer);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static int[] merge(int[]arr,int l , int h){
int[] temp = new int[arr.length];
int k = l;
int low = l;
int high = h;
while (low<h && high<arr.length){
if(arr[low]<arr[high]){
temp[k] = arr[low];
low++;
k++;
}else{
temp[k] = arr[high];
high++;
k++;
}
}
while(low <h){
temp[k] = arr[low];
low++;
k++;
}
while(high<arr.length){
temp[k] = arr[high];
high++;
k++;
}
return temp;
}
}
from collections import deque
a = [-3, -1, 2, 4]
neg = deque()
pos = deque()
for x in a:
if x < 0: neg.append(x**2)
else: pos.appendleft(x**2)
final = []
while neg or pos:
if not pos: final.append(neg.pop())
elif not neg: final.append(pos.pop())
elif neg[-1] > pos[-1]: final.append(pos.pop())
else: final.append(neg.pop())
print final
static int[] squared(int[] arr) {
if (arr == null || arr.length == 0)
return arr;
int[] sq = new int[arr.length];
int i=0, j=arr.length-1;
int k=j;
while( i <= j ) {
if( Math.abs(arr[i] ) <= Math.abs( arr[j] ) ) {
sq[k--]= arr[j]*arr[j];
j--;
}else{
sq[k--]= arr[i]*arr[i];
i++;
}
}
return sq;
}
1 approach
- Sergey September 21, 20161) sort array by abs(x) as key (e.g. [1,2,3,-4,5,-6])
2) return [x**2 for x in array]
O(n log n) time
O(1) additional space
2 approach
1) do sqr for all negative and reverse list, do sqr for positive
2) merge 2 arrays like in merge sort but only 1 iteration needed
O(n) time
O(n) additional space (because of merge)
Actually it IS possible to do merge in linear time and constant extra space. By algorithm is not trivial :)
Google for it: Bing-Chao Huang, Michael A. Langston, “Practical In-Place Merging” (1988).
So best solution will be:
O(n) time
O(1) extra space