Sorted Order of Squares
Given a list of integers sorted in non-decreasing order, return the original values arranged by the increasing order of their squares. If two values have the same square, the value that appears earlier in the input list should appear earlier in the output.
Methods
Square Sorted Order
List<Integer> squareSortedOrder(List<Integer> nums)
- Returns all original elements ordered by increasing square value.
- The returned list must contain the original values, not their squared values.
- If two elements have equal square values, keep their relative order from the input list.
K-th Square Sorted Element
int kthSquareSortedElement(List<Integer> nums, int k)
- Returns the
k-th element from the square-sorted order.
k is 1-indexed.- The result must be the original value, not its squared value.
Constraints
1 ≤ nums.size() ≤ 100,000-1,000,000,000 ≤ nums[i] ≤ 1,000,000,000nums is sorted in non-decreasing order.1 ≤ k ≤ nums.size()- The output order must be deterministic.
Examples
Example 1
squareSortedOrder(nums = List.of(-5, -3, -1, 2, 4))
Output: List.of(-1, 2, -3, 4, -5)
Explanation: The square values are 25, 9, 1, 4, 16, so the original values are ordered as -1, 2, -3, 4, -5.
Example 2
squareSortedOrder(nums = List.of(-4, -2, 0, 3, 5))
Output: List.of(0, -2, 3, -4, 5)
Explanation: The square values are 16, 4, 0, 9, 25, so the original values are ordered as 0, -2, 3, -4, 5.
Example 3
kthSquareSortedElement(nums = List.of(-6, -2, -1, 3, 4), k = 4)
Output: 4
Explanation: The square-sorted order is List.of(-1, -2, 3, 4, -6). The 4th element is 4.
Example 4
kthSquareSortedElement(nums = List.of(-3, -1, 1, 2), k = 2)
Output: 1
Explanation: The square-sorted order is List.of(-1, 1, 2, -3). The 2nd element is 1. Since -1 appears before 1 in the input, it also appears first in the output.