CODEWITHSUNDEEP
arraysalgorithmarray-algorithms
Candace
Candace

Reputation: 53

Algorithm not functioning for sort squared array based off of input

I'm working on building an algorithm that sorts in place for an array of nondecreasing integers, and it's not passing some of my tests. I was wondering why? I've included a sample input and output as well.

import java.util.*;

class Program {

  public int[] sortedSquaredArray(int[] array) {
        int[] res = new int[array.length];
        int leftPointer = 0; 
        int rightPointer = array.length - 1;
        int counter = 0; 
        while (counter < array.length) {
            int leftSquared = array[leftPointer] * array[leftPointer];
            int rightSquared = array[rightPointer] * array[rightPointer]; 
            if (leftSquared < rightSquared) {
                res[counter] = leftSquared;
                leftPointer++;
            } else if (rightSquared <= leftSquared) {
                res[counter] = rightSquared; 
                rightPointer--;
            }
            counter++;
        }
        return res;
  }
}

"array": [-50, -13, -2, -1, 0, 0, 1, 1, 2, 3, 19, 20]

expected output:

[0, 0, 1, 1, 1, 4, 4, 9, 169, 361, 400, 2500]

what I'm getting:

[400, 361, 9, 4, 1, 1, 0, 0, 1, 4, 169, 2500]

Upvotes: 0

Views: 57

Answers (2)

Frank
Frank

Reputation: 1004

Just as @greybeard wrote: your mistake is to fill from the lower end, but you do not know the lowest square yet, since you are checking the two numbers with the BIGGEST square value.

This function should do what you want:

    public int[] sortedSquaredArray(int[] array)
    {
        if (array.length == 0 || array[0] >= 0)
            return array;
            
        int[] res = new int[array.length];
        int leftPointer = 0; 
        int leftSquared = array[leftPointer] * array[leftPointer];
        int rightPointer = array.length - 1;
        int rightSquared = array[rightPointer] * array[rightPointer]; 
        int counter = rightPointer; 
        while (counter >= 0)
        {
            if (leftSquared >= rightSquared)
            {
                res[counter] = leftSquared;
                leftPointer++;
                leftSquared = array[leftPointer] * array[leftPointer];
            }
            else
            {
                res[counter] = rightSquared; 
                rightPointer--;
                rightSquared = array[rightPointer] * array[rightPointer];
            }
            counter--;
        }
        return res;
    }

Note the optimisations in line 3 and 4 and calculating the squared values only when needed. Also this function is NOT doing in-place sorting! It is returning a new array with the sorted squares. Doing an in-place sorting could be accomplished by re-assigning the values from the sorted array to the passed-in array before returning or using the passed-in array directly but having to move around the array-values a lot, if the left pointer is pointing to the bigger value.

You can watch the code in action with your example data here.

Upvotes: 0

greybeard
greybeard

Reputation: 2497

If the array was specified to be in increasing order, your attempt was very close:
Just fill the result from larger squares to lower.
(If the array starts with a non-negative value, just return (a copy of) the input array.)

Upvotes: 1

Related Questions