Algorithm not functioning for sort squared array based off of input

Question

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]

When the loop starts, the left pointer points to -50 (2500), and the right pointer points to 20 (400). Neither one of those is correct for the first element of the output array, but 400 is smaller, so that's the one that's chosen. — user3386109
– user3386109, Commented Apr 26, 2022 at 22:52
Is or isn't the array specified to be in increasing order? Does or doesn't in place mean additional space dominated by array size? — greybeard
– greybeard, Commented Jul 18, 2022 at 13:09

greybeard · Accepted Answer · 2022-04-27 06:33:33Z

1

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.)

answered Apr 27, 2022 at 6:33

greybeard

2,6769 gold badges40 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Frank · Accepted Answer · 2022-07-18 10:06:31Z

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.

Collectives™ on Stack Overflow

Algorithm not functioning for sort squared array based off of input

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related