Jobs

Interviews

Discussions

Squares of a Sorted Array

Easy

Apple

1 view

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. Can you come up with an efficient solution for this problem?

For example:

nums = [-4, -1, 0, 3, 10] should return [0, 1, 9, 16, 100]
nums = [-7, -3, 2, 3, 11] should return [4, 9, 9, 49, 121]

Here are the constraints:

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

What are the edge cases to consider? How would you optimize the solution for the best time complexity? Squaring each element and then sorting is a trivial solution. Can you come up with an O(n) solution?

Squares of a Sorted Array

Easy

Apple

1 view

Topics:

ArraysTwo Pointers

For example:

nums = [-4, -1, 0, 3, 10] should return [0, 1, 9, 16, 100]
nums = [-7, -3, 2, 3, 11] should return [4, 9, 9, 49, 121]

Here are the constraints:

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

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? Could they be very large, potentially leading to integer overflow issues when squared?
Can the input array `nums` be empty or null?
Since the input array is sorted in non-decreasing order, does that mean it could contain duplicate values?
Should I return a *new* array, or can I modify the input array in place?
Are there any specific memory constraints I should be aware of, assuming optimal time complexity is the priority?

Brute Force Solution

Approach

We need to find the squares of numbers and arrange them in ascending order. The brute force approach is straightforward: we will square each number individually and then sort the resulting list of squares.

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

Take each number in the original list.
Calculate the square of that number.
Put the squared number in a new list.
Once you've done this for every number in the original list, you'll have a new list containing all the squares.
Finally, rearrange the squared numbers in this new list from smallest to largest.

Code Implementation

def squares_of_a_sorted_array_brute_force(numbers):
    squared_numbers = []

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

    # Sorting will arrange the squares in ascending order
    squared_numbers.sort()

    return squared_numbers

Big(O) Analysis

Time Complexity

O(n log n) – The described algorithm squares each of the n elements in the input array. This squaring operation takes O(n) time. Then, the resulting array of n squared elements is sorted. A typical comparison-based sorting algorithm like merge sort or quicksort takes O(n log n) time. Therefore, the overall time complexity is dominated by the sorting step, making it O(n log n).

Space Complexity

O(N) – The provided algorithm creates a new list to store the squares of the input numbers. Since we square each of the N numbers in the input array and store them in this new list, the auxiliary space used scales linearly with the input size N. After squaring, the algorithm sorts the new array in place which doesn't add to auxiliary space. Therefore, the overall space complexity is O(N).

Optimal Solution

Approach

The key idea is to avoid sorting after squaring. Since the original numbers are sorted, the largest squares will be at the extreme ends. We use two pointers, one at each end, and work inwards, placing the larger square into the result.

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

Recognize that squaring a negative number makes it positive, so the numbers at the beginning of the list, even though they are the smallest, can become big when squared.
Imagine you have two fingers, one pointing to the beginning and the other to the end of the list.
Compare the squares of the numbers your fingers are pointing to.
Put the larger square into a new list, starting from the end of the new list and working backwards.
Move the finger that pointed to the larger square one step closer to the middle of the list.
Keep comparing, squaring, and placing the larger square until both fingers meet in the middle.
The new list now contains the squares of the original numbers, sorted from largest to smallest.

Code Implementation

def sorted_squares(numbers):
    left_pointer = 0
    right_pointer = len(numbers) - 1
    results = [0] * len(numbers)
    result_index = len(numbers) - 1

    # Iterate until the pointers meet
    while left_pointer <= right_pointer:

        left_square = numbers[left_pointer] ** 2
        right_square = numbers[right_pointer] ** 2

        # Place larger square in result and adjust the appropriate pointer.
        if left_square > right_square:

            results[result_index] = left_square
            left_pointer += 1

        else:

            results[result_index] = right_square
            right_pointer -= 1

        # The result array is populated from the end.
        result_index -= 1

    return results

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array of size n using two pointers, one starting from the beginning and the other from the end. In each iteration, it compares the squares of the numbers pointed to by these pointers and places the larger square into the result array. Each pointer moves one step closer to the middle in each iteration. Therefore, each element is visited and processed exactly once. Hence the time complexity is proportional to the size of the array, n, making it O(n).

Space Complexity

O(N) – The algorithm creates a new list to store the squares of the original numbers. This new list grows linearly with the number of elements in the input array. Since the new list contains N elements, where N is the number of elements in the original sorted array, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on the specification.
Array with a single element	Square the element and return a new array containing only that squared value.
Array with all zero values	Return an array of the same size filled with zeros.
Array with all negative values	The squares will be positive and in decreasing order originally, so the algorithm must handle reversing the order or use a two-pointer approach.
Array with all positive values	The squares will be positive and already in non-decreasing order, so the algorithm should maintain this order.
Array with mixed positive and negative values	The algorithm should correctly handle the transition from decreasing squares (of negative numbers) to increasing squares (of positive numbers) by comparing values appropriately.
Integer overflow when squaring large numbers	Use a data type that can accommodate larger values (e.g., long) or perform explicit overflow checks.
Maximum size array (scalability)	The chosen algorithm (likely two-pointer) should perform efficiently in terms of time and space complexity, preferably O(n).

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? Could they be very large, potentially leading to integer overflow issues when squared?
Can the input array `nums` be empty or null?
Since the input array is sorted in non-decreasing order, does that mean it could contain duplicate values?
Should I return a *new* array, or can I modify the input array in place?
Are there any specific memory constraints I should be aware of, assuming optimal time complexity is the priority?

Brute Force Solution

Approach

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

Take each number in the original list.
Calculate the square of that number.
Put the squared number in a new list.
Once you've done this for every number in the original list, you'll have a new list containing all the squares.
Finally, rearrange the squared numbers in this new list from smallest to largest.

Code Implementation

def squares_of_a_sorted_array_brute_force(numbers):
    squared_numbers = []

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

    # Sorting will arrange the squares in ascending order
    squared_numbers.sort()

    return squared_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Recognize that squaring a negative number makes it positive, so the numbers at the beginning of the list, even though they are the smallest, can become big when squared.
Imagine you have two fingers, one pointing to the beginning and the other to the end of the list.
Compare the squares of the numbers your fingers are pointing to.
Put the larger square into a new list, starting from the end of the new list and working backwards.
Move the finger that pointed to the larger square one step closer to the middle of the list.
Keep comparing, squaring, and placing the larger square until both fingers meet in the middle.
The new list now contains the squares of the original numbers, sorted from largest to smallest.

Code Implementation

def sorted_squares(numbers):
    left_pointer = 0
    right_pointer = len(numbers) - 1
    results = [0] * len(numbers)
    result_index = len(numbers) - 1

    # Iterate until the pointers meet
    while left_pointer <= right_pointer:

        left_square = numbers[left_pointer] ** 2
        right_square = numbers[right_pointer] ** 2

        # Place larger square in result and adjust the appropriate pointer.
        if left_square > right_square:

            results[result_index] = left_square
            left_pointer += 1

        else:

            results[result_index] = right_square
            right_pointer -= 1

        # The result array is populated from the end.
        result_index -= 1

    return results

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 the specification.
Array with a single element	Square the element and return a new array containing only that squared value.
Array with all zero values	Return an array of the same size filled with zeros.
Array with all negative values	The squares will be positive and in decreasing order originally, so the algorithm must handle reversing the order or use a two-pointer approach.
Array with all positive values	The squares will be positive and already in non-decreasing order, so the algorithm should maintain this order.
Array with mixed positive and negative values	The algorithm should correctly handle the transition from decreasing squares (of negative numbers) to increasing squares (of positive numbers) by comparing values appropriately.
Integer overflow when squaring large numbers	Use a data type that can accommodate larger values (e.g., long) or perform explicit overflow checks.
Maximum size array (scalability)	The chosen algorithm (likely two-pointer) should perform efficiently in terms of time and space complexity, preferably O(n).