Jobs

Interviews

Discussions

Squares of a Sorted Array

Easy

Asked by:

+11

40 views

Topics:

ArraysTwo Pointers

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].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Squares of a Sorted Array

Easy

Asked by:

40 views

Topics:

ArraysTwo Pointers

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].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array `nums` be empty or null?
Is it acceptable to modify the input array in place, or should I create a new array for the result?
Are there any specific space complexity constraints I should be aware of?
Given the array is sorted in non-decreasing order, is it possible for all numbers to be negative?

Brute Force Solution

Approach

We need to find the squares of numbers in a sorted list and then sort the squares. The brute force method will individually compute the square of each number and then sort the entire collection of squares.

Here's how the algorithm would work step-by-step:

Go through the given list of numbers one by one.
For each number, calculate its square.
Store all these calculated squares in a new list.
Finally, sort the new list of squares in ascending order.

Code Implementation

def squares_of_a_sorted_array_brute_force(numbers):
    squares = []

    # Calculate the square of each number
    for number in numbers:
        square = number * number
        squares.append(square)

    # The next step is to sort the squares
    squares.sort()

    return squares

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the input array of size n, calculating the square of each number. This takes O(n) time. After calculating the squares, the algorithm sorts the new list of n squares. A typical comparison-based sorting algorithm, like merge sort or quicksort, has a time complexity of O(n log n). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm creates a new list to store the squares of the numbers. The size of this list is directly proportional to the input size N, where N is the number of elements in the input array. Therefore, the auxiliary space required is O(N) due to storing the squared values.

Optimal Solution

Approach

Since the input numbers are sorted, we can use this to our advantage. The core idea is to realize that the largest squares will be at the edges of the input, either from the most negative or most positive numbers. We then work inward from the edges to build the sorted squares.

Here's how the algorithm would work step-by-step:

Imagine two pointers, one at the very beginning and one at the very end of the list of numbers.
Compare the absolute values of the numbers at these two locations. This tells us which number, when squared, will be the largest.
Place the larger square at the end of a new list.
Move the pointer that pointed to the number you just squared closer to the middle.
Repeat the comparison and placement, working your way from the outside inward, filling your new list from the back to the front.
Continue this process until the two pointers meet in the middle. At this point, your new list will contain all the squared numbers in sorted order.

Code Implementation

def squares_of_a_sorted_array(numbers):
    number_of_elements = len(numbers)
    squared_numbers = [0] * number_of_elements
    left_pointer = 0
    right_pointer = number_of_elements - 1
    result_index = number_of_elements - 1

    while left_pointer <= right_pointer:
        # Determine which square is larger.
        if abs(numbers[left_pointer]) > abs(numbers[right_pointer]):

            squared_numbers[result_index] = numbers[left_pointer] ** 2
            left_pointer += 1

        else:
            squared_numbers[result_index] = numbers[right_pointer] ** 2

            # Decrement, since we placed the largest at end.
            right_pointer -= 1

        # Fill array from the end to the beginning.
        result_index -= 1

    return squared_numbers

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, one starting from the beginning and the other from the end of the input array. In each iteration, it compares the absolute values of the numbers pointed to by these pointers, squares the larger number, and places it in the correct position in the result array. Since both pointers move towards the middle, each element is visited and processed exactly once. Therefore, the time complexity is directly proportional to the size of the input array, n, resulting in O(n).

Space Complexity

O(N) – The algorithm creates a new list to store the squared and sorted numbers. The size of this new list is equal to the size of the input array, which we denote as N. Therefore, the auxiliary space required is directly proportional to the input size N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on requirements, ensuring to handle the absence of input gracefully.
Input array with only one element	Return an array containing the square of the single element, as it's already sorted by default.
Input array with all identical values (e.g., [2, 2, 2])	The squaring and sorting logic should handle identical values correctly, resulting in an array of the squares of the identical values, also sorted.
Input array with a large range of negative and positive numbers (e.g., [-1000, -1, 0, 1, 1000])	The solution must correctly square negative numbers and then efficiently sort the resulting squared values, considering magnitude changes upon squaring.
Input array with extremely large numbers that, when squared, could lead to integer overflow	Use a data type with a larger range (e.g., long) or consider using arbitrary-precision arithmetic to prevent overflow issues during the squaring operation.
Input array containing zeros	Zeroes will be squared to zero and should be placed correctly in the sorted output array.
Very large input array to test for performance	The algorithm should have a time complexity of O(n log n) or better (like O(n)) to efficiently handle large datasets where 'n' is the size of the array.
Array already sorted with all positive numbers	The result will be the square of each element sorted in increasing order, no modifications necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array `nums` be empty or null?
Is it acceptable to modify the input array in place, or should I create a new array for the result?
Are there any specific space complexity constraints I should be aware of?
Given the array is sorted in non-decreasing order, is it possible for all numbers to be negative?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the given list of numbers one by one.
For each number, calculate its square.
Store all these calculated squares in a new list.
Finally, sort the new list of squares in ascending order.

Code Implementation

def squares_of_a_sorted_array_brute_force(numbers):
    squares = []

    # Calculate the square of each number
    for number in numbers:
        square = number * number
        squares.append(square)

    # The next step is to sort the squares
    squares.sort()

    return squares

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine two pointers, one at the very beginning and one at the very end of the list of numbers.
Compare the absolute values of the numbers at these two locations. This tells us which number, when squared, will be the largest.
Place the larger square at the end of a new list.
Move the pointer that pointed to the number you just squared closer to the middle.
Repeat the comparison and placement, working your way from the outside inward, filling your new list from the back to the front.
Continue this process until the two pointers meet in the middle. At this point, your new list will contain all the squared numbers in sorted order.

Code Implementation

def squares_of_a_sorted_array(numbers):
    number_of_elements = len(numbers)
    squared_numbers = [0] * number_of_elements
    left_pointer = 0
    right_pointer = number_of_elements - 1
    result_index = number_of_elements - 1

    while left_pointer <= right_pointer:
        # Determine which square is larger.
        if abs(numbers[left_pointer]) > abs(numbers[right_pointer]):

            squared_numbers[result_index] = numbers[left_pointer] ** 2
            left_pointer += 1

        else:
            squared_numbers[result_index] = numbers[right_pointer] ** 2

            # Decrement, since we placed the largest at end.
            right_pointer -= 1

        # Fill array from the end to the beginning.
        result_index -= 1

    return squared_numbers

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on requirements, ensuring to handle the absence of input gracefully.
Input array with only one element	Return an array containing the square of the single element, as it's already sorted by default.
Input array with all identical values (e.g., [2, 2, 2])	The squaring and sorting logic should handle identical values correctly, resulting in an array of the squares of the identical values, also sorted.
Input array with a large range of negative and positive numbers (e.g., [-1000, -1, 0, 1, 1000])	The solution must correctly square negative numbers and then efficiently sort the resulting squared values, considering magnitude changes upon squaring.
Input array with extremely large numbers that, when squared, could lead to integer overflow	Use a data type with a larger range (e.g., long) or consider using arbitrary-precision arithmetic to prevent overflow issues during the squaring operation.
Input array containing zeros	Zeroes will be squared to zero and should be placed correctly in the sorted output array.
Very large input array to test for performance	The algorithm should have a time complexity of O(n log n) or better (like O(n)) to efficiently handle large datasets where 'n' is the size of the array.
Array already sorted with all positive numbers	The result will be the square of each element sorted in increasing order, no modifications necessary.