Understanding the Two Pointers Technique: Sorted Squares Problem

Line by Line breakdown

The two pointers technique is a fundamental approach for solving various coding challenges. Its effectiveness is often evaluated using Big O notation, which measures time and space complexity.

In this post, we'll apply the two pointers technique to the Sorted Squares problem from LeetCode. We will also examine how to analyze the time and space complexity of the solution.

Problem Statement

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

• Input: nums = [-4,-1,0,3,10]

• Output: [0, 1, 9, 16, 100]

• Explanation: After squaring, the array becomes [16, 1, 0, 9, 100]. Sorting it gives [0, 1, 9, 16, 100].

Example 2:

• Input: nums = [-7,-3,2,3,11]

• Output: [4, 9, 9, 49, 121]

Python Solution Using Two Pointers

Here's how you can solve this problem using Python:

def sortedSquares(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) < abs(nums[right]):
            square = nums[right]
            right -= 1
        else:
            square = nums[left]
            left += 1
        result[i] = square * square
    
    return result

Line-by-Line Breakdown

1. def sortedSquares(nums: List[int]) -> List[int]:
   Defines a function that takes a list of integers and returns a list of integers.

2. n = len(nums)
   Calculates the length of the input list.

3. result = [0] * n
   Initializes a list result of length n with all elements set to 0.

4. left, right = 0, n - 1
   Sets up two pointers, left at the start and right at the end of the list.

5. for i in range(n - 1, -1, -1):
   Iterates backwards through the result list.

6. if abs(nums[left]) < abs(nums[right]):
   Compares the absolute values of the elements at the left and right pointers.

7. square = nums[right]
   Assigns the value at the right pointer to square if its absolute value is larger.

8. right -= 1
   Moves the right pointer leftward.

9. else:
   If the absolute value at left is larger or equal.

10. square = nums[left]
    Assigns the value at the left pointer to square.

11. left += 1
    Moves the left pointer rightward.

12. result[i] = square * square
    Squares the value and stores it in the result list at index i.

Time and Space Complexity Analysis

The time complexity of the sortedSquares function is O(n), where n is the length of the input list nums. This is because the function iterates over the input list once using the left and right pointers, performing constant-time operations at each step.

• The space complexity is O(n) as well, since the function creates a new list result of the same length as the input list nums to store the squared and sorted elements.

  Here's a more detailed analysis:

  1. Time Complexity:

     • The line n = len(nums) takes O(1) time since it's a constant-time operation to get the length of a list.

     • The line result = [0] * n takes O(n) time to create a new list of length n.

     • The loop for i in range(n - 1, -1, -1): iterates n times.

     • Inside the loop, the operations abs(nums[left]), abs(nums[right]), square = nums[right], right -= 1, square = nums[left], left += 1, and result[i] = square * square all take constant time O(1).

     • Therefore, the overall time complexity is O(n) + O(n) = O(n).

  2. Space Complexity:

     • The function creates a new list result of length n, which takes O(n) space.

     • No other additional data structures are used that would increase the space complexity beyond O(n).

  In summary, the time complexity of the sortedSquares function is O(n), and the space complexity is O(n), where n is the length of the input list nums.