LC-0977 Easy LeetCode

977. Squares of a Sorted Array

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 73% Topics: Array, Two Pointers, Sorting

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

import bisect


class Solution(object):
    def sortedSquares(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        right = bisect.bisect_left(A, 0)
        left = right-1
        result = []
        while 0 <= left or right < len(A):
            if right == len(A) or \
               (0 <= left and A[left]**2 < A[right]**2):
                result.append(A[left]**2)
                left -= 1
            else:
                result.append(A[right]**2)
                right += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT