Sort array after converting to squares

Question

class Solution {
    public int[] sortedSquares(int[] arr) {
        for(int i = 0; i < arr.length; i++){
            for(int j=i+1;j<arr.length;j++){
                arr[i]=arr[i]*arr[i];
                arr[j]=arr[j]*arr[j];
                if(arr[j]<arr[i]){
                    int temp=0;
                    temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                    
                    
                }
            }
        }
        return arr;
}
}

Can you tell me where am going wrong? For input [-4,-1,0,3,10], output should be [0,1,9,16,100] . My current output is [0,1,43046721,0,1874919424]. I don't want to use Array.sort() . I wanted to write my own code.

Computable · Accepted Answer · 2022-09-08T17:43:17.007

1

Your sort loop is functional but you are squaring each entry 4 times in a cumulative manner. One approach is to first square all the elements and then sort.

From your results you can see evidence:

(((3^2)^2)^2)^2 = 43046721

The second 0 is interesting:

(((-4^2)^2)^2)^2 = 4,294,967,296

which for a 32-bit int becomes 0.

And for 10:

(((10^2)^2)^2)^2 = 10,000,000,000,000,000

rolls over to 187491924.

So your code can simply be updated by first squaring the entries and then sort:

public int[] sortedSquares(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        arr[i] = arr[i] * arr[i];
    }
    for(int i = 0; i < arr.length; i++){
        for(int j=i+1;j<arr.length;j++){
            if(arr[j]<arr[i]){
                int temp=0;
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
    return arr;
}

edited Sep 08 '22 at 17:43

answered Sep 08 '22 at 17:32

Computable

976
2
4
16

Thanks so much Gardner. The code actually worked.. But one more thing i have faced.. public class squaresort { public static int[] squareno(int[] arr) { for(int i=0;i – Jeevan Jitu Sep 08 '22 at 17:44
Try `System.out.println(Arrays.toString(squareno(arr)));` see https://stackoverflow.com/a/409795/17856705 . – Computable Sep 08 '22 at 17:51
1

Thanks for being such good tutor gardner.. Its resolved – Jeevan Jitu Sep 08 '22 at 17:53

score 1 · Answer 2 · answered Sep 08 '22 at 18:33

You are square each number multiple times during the sort. I recommend the following solution which will still let you sort on the square values using only the nested loops. But you need to swap the sorted values and the unsorted ones to keep them in sync.

public static int[] sortedSquares(int[] arr) {
        for(int i = 0; i < arr.length-1; i++){
            int t1 = arr[i]*arr[i];
            for(int j=i+1;j<arr.length;j++){
                int t2 = arr[j] * arr[j];
                if(t1<t2){
                  int  temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                    temp = t1;
                    t1 = t2;
                    t2 = temp;
                }
            }
            arr[i] = t1;  // now assign t1 to arr[i].  The first element will no 
                          // longer be accessed so it won't taint the results.
            
          
        }
        return arr;
}

Sort array after converting to squares

2 Answers2