Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Arturo Calderón
Using the fact that Python lists have O(1) insertion time

Arturo Calderón

Jul 22, 2023

For Python specifically, we can get away with simpler expressions if we take into account that inserting elements in a list is a O(1) operation. This makes the code easier to read IMO.

def SquareSortedArrayV2(nums):     idxLeft = 0     idxRight = len(nums) - 1     sortedSquares = []         while idxLeft <= idxRight:         valLeft = nums[idxLeft] ** 2         valRigth = nums[idxRight] ** 2         if valRigth > valLeft:             sortedSquares.insert(0, valRigth)             idxRight -= 1         else:             sortedSquares.insert(0, valLeft)             idxLeft += 1     return sortedSquares

0

0

Comments
Comments
 Sri
Sri2 years ago

why are you inserting at index 0 every time?

edisonfreire14
edisonfreire14 a year ago

they do not have O(1) insertion at the beginning, only at the end.

On this page

Problem Statement

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity