[LeetCode] 977. Squares of a Sorted Array

問題

https://leetcode.com/problems/squares-of-a-sorted-array/description/

解答と解説

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        // 最後のindexから値を更新していくため、初期化が必要
        ans = [0] * n
        
        left, right = 0, n - 1
        i = n - 1
　　　　　　　　　　　　　　　　// forでもよい
        while left <= right:
            if abs(nums[left]) < abs(nums[right]):
                ans[i] = nums[right] * nums[right]
                right -= 1
            else:
                ans[i] = nums[left] * nums[left]
                left += 1
            i -= 1
            
        return ans

numsの長さをnとした時、

• Time Complexity: O(n)
• Space Complexity: O(1)

inputの配列がソートされていることで、二乗された値は必ず両端のいずれかが最大値になる。

それがわかれば、あとはTwo Pointersのパターンを使って、答えの最大値から埋めていけば良い。