Sort squares is to sort the square of elements in a sorted array. If we use sorting algorithms such as bubble sort, the time complexity is O(n^2). The task is to optimize it so that The complexity should be O(n).
The solution is using two pointers. Initialize two pointers, one points to the first element, and the other points to the last element. Then compare the absolute value of these two elements pointed by the indices. Put the square of the larger one at the end of the output array. Then increase or decrease the larger one’s index. When all the elements have been compared, the output is the sorted square. This solution has the time complexity to O(n).
VMwave Interview Question:
Input: sorted integers: example: [-2, 1, 2, 3]
Output: sorted square if the input: [1, 4, 4 ,9]
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.Arrays; public class SortSquares { //Two pointers, Time O(n), Space O(n), n is array length public static int[] sortSquares(int[] a) { int n = a.length; int[] res = new int[n]; int i = 0, j = n - 1; for (int k = n-1; k >= 0; k--) { if (Math.abs(a[i]) > Math.abs(a[j])) { res[k] = a[i] * a[i]; i++; } else { res[k] = a[j] * a[j]; j--; } } return res; } public static void main(String[] args) { int[] a = {-2, 1, 2, 3}; System.out.print("Input: "); System.out.println(Arrays.toString(a)); int[] b = sortSquares(a); System.out.print("Sort squares: "); System.out.println(Arrays.toString(b)); } } |
Output:
Input: [-2, 1, 2, 3]
Sort squares: [1, 4, 4, 9]
O Notation:
Time complexity: O(n)
Space complexity: O(n)
Download SortSquares.java
Sort squares with optimization (YouTube)
Merge two sorted arrays (2 solutions)