How to find Squares of a Sorted Array in Java | Programming Blog

Java Solution for Find Squares of a Sorted Array | LeetCode Problem

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation: After squaring, 
    the array becomes [16, 1, 0, 9, 100].
After sorting, it becomes [0, 1, 9, 16, 100].

Example 2:

Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation: After squaring, 
    the array becomes [49, 9, 4, 9, 121].
After sorting, it becomes [4, 9, 9, 49, 121].

So lets see 3 solutions of this problem.

Lets see how we can achieve O(n) time complexity. 

Solution 1 : Using new array

class Solution {

    public int[] sortedSquares(int[] array) {
        
        int arrayLength = array.length;
        int[] sortedSquare = new int[arrayLength];
        int start = 0, end = arrayLength-1;
        
        for(int i = arrayLength-1; i >= 0; i--) {
            int number;
            
            if (Math.abs(array[start]) > Math.abs(array[end])) {
                number = array[start++];
            } else {
                number = array[end--];
            }
            sortedSquare[i] = number*number;
        }

        return sortedSquare;
    }
}

Solution explanation :

• We uses new array for above approach. Declare and initialize array same as given array length.
• Declare two int variable, start with 0 and end with array length - 1.
• Traverse array from right to left (n to 0).
• Declare int variable number.
• Now we are starting comparing from array[0] and last value of array. We uses Math.abs() function for getting positive int from negative int.
• If array[start] value is greater than array[end] value, increase start by one, square the number and stored in sortedSquare[i] (insert from last index).

Output explanation :

• array = [-4, -1, 0, 3, 10], sortedSquare = [0, 0, 0, 0, 0], arrayLength = 5, start = 0, end = 4
• i = 4
• Math.abs(nums[start]) > Math.abs(nums[end]) | 4 > 10 becomes false
• else condition
• number = nums[end--] | number = 10 
• sortedSquare[i] = number*number |  sortedSquare[4] = 100
  
  
• i = 3,  sortedSquare = [0, 0, 0, 0, 100], start = 0, end = 3
•  4 > 3 becomes true
• if condition
• number = nums[start++] | number = 4 
•  sortedSquare[3] = 16
  
  
• i = 2,  sortedSquare = [0, 0, 0, 16, 100], start = 1, end = 3
•  1 > 3 becomes false
• else condition
• number = nums[end--] | number = 3
  
•  sortedSquare[2] = 9
  
  
• i = 1,  sortedSquare = [0, 0, 9, 16, 100], start = 1, end =2
•  1 > 0 becomes true
  
• if condition
• number = nums[start++] | number = 1
  
•  sortedSquare[1] = 1
  
  
• i = 0,  sortedSquare = [0, 1, 9, 16, 100], start = 2, end =2
•  0 > 0 becomes false
  
• else condition
• number = nums[end--] | number = 0
•  sortedSquare[0] = 0
  
  
• Loop ends

return sortedSquare = [0, 1, 9, 16, 100 ]

Solution 2 :- Using Arrays.sort()

import java.util.Arrays;
import java.util.Scanner;

public class SquaresOfaSortedArray {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter Array Size");
        int arraySize = sc.nextInt();
        int[] array = new int[arraySize];
        
        System.out.println("Enter Array Values");
        for (int i = 0; i < arraySize; i++) {
            array[i] = sc.nextInt();
        }
        
        sortedSquares(array);
        
        System.out.println("Output");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
    
    public static int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        
        Arrays.sort(nums);
        return nums;
    }

}
Output :-
Enter Array Size
5
Enter Array Values
6 2 88 4 5
Output
4 16 25 36 7744

Explanation :-

1. For loop through array and get number one by one and store square of particular number at same position in array.
2. After done all square of array's number, Sort the array using Arrays.sort method.

Output Explanation :-

[6, 2, 88, 4, 5] after squaring become [36, 4, 7744, 16, 25].
After Square we Sort array and it become [4, 16, 25, 36, 7744].

Solution 3 :- Using Arrays.stream

import java.util.Arrays;
import java.util.Scanner;

public class SquaresOfaSortedArray {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter Array Size");
        int arraySize = sc.nextInt();
        int[] array = new int[arraySize];
        
        System.out.println("Enter Array Values");
        for (int i = 0; i < arraySize; i++) {
            array[i] = sc.nextInt();
        }
        
        array = sortedSquares(array);
        
        System.out.println("Output");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
    
    public static int[] sortedSquares(int[] nums) {

        return Arrays.stream(nums)
                    .map(n -> n * n)
                    .sorted()
                    .toArray();  
    }

}

Happy Coding

Other articles you may be like :-

• Find Numbers with Even Number of Digits in Java
  
• Java Generics HackerRank Solution