Sort squares with optimization – Code

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

sort square

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:

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)

Comments are closed