Teaching Kids Programming – Square of a List using Two Pointer Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers sorted in ascending order nums, square the elements and give the output in sorted order.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [-9, -2, 0, 2, 3]
Output
[0, 4, 4, 9, 81]
Example 2
Input
nums = [1, 2, 3, 4, 5]
Output
[1, 4, 9, 16, 25]

Square and Sort

We can do what it says: square each number and then sort it – which is trivial:

1
2
3
4
5
6

class Solution:
    def solve(self, nums):
        ans = []
        for i in nums:
            ans.append(i**2)
        return sorted(ans)

class Solution:
    def solve(self, nums):
        ans = []
        for i in nums:
            ans.append(i**2)
        return sorted(ans)

The time complexity is O(NLogN) due to sorting N numbers. We can do this one liner:

1
2
3

return sorted(x**2 for x in nums)
# or using the map function
return sorted(map(lambda x: x**2, nums))

return sorted(x**2 for x in nums)
# or using the map function
return sorted(map(lambda x: x**2, nums))

Two Pointer Algorithm to Square a List

Since the original array/list is sorted, we can fill the answer array from largest square to the smallest. We have two pointers on both sides, and then we can compare and pick the larger square.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def solve(self, nums):
        n = len(nums)
        l = 0
        index = r = n - 1
        res = nums[:]
        while index >= 0:
            if abs(nums[l]) >= abs(nums[r]):
                res[index] = nums[l]**2
                l += 1
            else:
                res[index] = nums[r]**2
                r -= 1
            index -= 1
        return res

class Solution:
    def solve(self, nums):
        n = len(nums)
        l = 0
        index = r = n - 1
        res = nums[:]
        while index >= 0:
            if abs(nums[l]) >= abs(nums[r]):
                res[index] = nums[l]**2
                l += 1
            else:
                res[index] = nums[r]**2
                r -= 1
            index -= 1
        return res

The time complexity is O(N) linear. The Two Pointer will meet in the middle and then we will have N squared numbers filled.

–EOF (The Ultimate Computing & Technology Blog) —