LeetCode Solutions
977. Squares of a Sorted Array
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
const int n = A.size();
vector<int> ans(n);
int i = n - 1;
for (int l = 0, r = n - 1; l <= r;)
if (abs(A[l]) > abs(A[r]))
ans[i--] = A[l] * A[l++];
else
ans[i--] = A[r] * A[r--];
return ans;
}
};
class Solution {
public int[] sortedSquares(int[] A) {
final int n = A.length;
int[] ans = new int[n];
int i = n - 1;
for (int l = 0, r = n - 1; l <= r;)
if (Math.abs(A[l]) > Math.abs(A[r]))
ans[i--] = A[l] * A[l++];
else
ans[i--] = A[r] * A[r--];
return ans;
}
}
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
n = len(A)
l = 0
r = n - 1
ans = [0] * n
while n:
n -= 1
if abs(A[l]) > abs(A[r]):
ans[n] = A[l] * A[l]
l += 1
else:
ans[n] = A[r] * A[r]
r -= 1
return ans