Jobs

Interviews

Discussions

Sort Transformed Array

Medium

Asked by:

14 views

Topics:

ArraysTwo Pointers

Given a sorted integer array nums and integers a, b, and c, apply a quadratic function of the form f(x) = a * x² + b * x + c to each element x in the array.

Return the array of transformed elements which is also sorted.

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

Constraints:

1 <= nums.length <= 200
-100 <= nums[i], a, b, c <= 100
nums is sorted in ascending order.

Try coding it in LeetCode

Sort Transformed Array

Medium

Asked by:

14 views

Topics:

ArraysTwo Pointers

Given a sorted integer array nums and integers a, b, and c, apply a quadratic function of the form f(x) = a * x² + b * x + c to each element x in the array.

Return the array of transformed elements which is also sorted.

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

Constraints:

1 <= nums.length <= 200
-100 <= nums[i], a, b, c <= 100
nums is sorted in ascending order.

Try coding it in LeetCode

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 `a`, `b`, and `c` in the transformation function f(x) = ax^2 + bx + c? Can they be negative, zero, or floating-point numbers?
What is the expected data type and range of values within the input `nums` array? Can it contain negative numbers, zeros, or floating-point numbers?
Can the input `nums` array be empty or null? If so, what should the function return in these cases?
Are duplicate numbers allowed in the input `nums` array, and if so, how should they be handled in the transformation and sorting process?
Is the input `nums` array guaranteed to be sorted in ascending order, or might it be unsorted?

Brute Force Solution

Approach

The brute force way to sort a transformed array involves calculating a value for each number in the original set based on a given formula. Then, we take all those calculated values and sort them from smallest to largest without considering their original order.

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

For each number we have, we apply the formula to find its transformed value.
We then gather all the transformed values into a new collection.
Finally, we arrange all the transformed values in the collection from the smallest to the largest.

Code Implementation

def sort_transformed_array_brute_force(numbers, a_coefficient, b_coefficient, c_constant):
    transformed_numbers = []

    # Transform each number using the given formula
    for number in numbers:
        transformed_value = a_coefficient * number * number + b_coefficient * number + c_constant
        transformed_numbers.append(transformed_value)

    # Sort the transformed numbers
    transformed_numbers.sort()

    return transformed_numbers

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the input array of size n to transform each element, resulting in n transformations. These transformed values are then stored in a new collection. The dominant operation is sorting this collection, which typically uses an efficient algorithm like merge sort or quicksort. Therefore, sorting n elements takes O(n log n) time. The linear transformation step is dominated by the sorting step.

Space Complexity

O(N) – The described solution creates a new collection to store the transformed values. The size of this collection grows linearly with the number of input elements, denoted as N, because each element in the input array has a corresponding transformed value stored in the new collection. Therefore, the auxiliary space required is proportional to N, leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to sort a transformed array efficiently. We exploit the properties of the quadratic function to avoid a full sort by smartly placing elements from the beginning and the end of the original array into a new sorted array.

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

First, figure out if the quadratic function (based on the coefficients provided) opens upwards or downwards. This will help determine how the numbers are ordered after the transformation.
Find out where the vertex (or turning point) of the quadratic function is. This point determines the minimum or maximum value of the transformed numbers.
Set up two 'pointers', one at the very start of the original numbers and one at the very end.
Compare the transformed values at the start and end 'pointers'. Because of the shape of the quadratic function, one of these values will be the next largest (if the parabola opens downwards) or smallest (if it opens upwards) in our final sorted transformed set of numbers.
Place the larger (or smaller, depending on whether it opens down or up) of the transformed values into the new, sorted transformed set of numbers.
Move the correct 'pointer' (the one that gave you the placed value) either one step forward (if it was the start 'pointer') or one step backward (if it was the end 'pointer').
Repeat the comparing, placing, and moving steps until all the original numbers have been transformed and placed into the new, sorted transformed numbers.
If the parabola opens downwards, the new sorted set will contain the transformed numbers in descending order, so reverse it. If it opens upwards it is already correctly ordered.

Code Implementation

def sort_transformed_array(numbers, coefficient_a, coefficient_b, coefficient_c):
    transformed_numbers = []
    for number in numbers:
        transformed_numbers.append(coefficient_a * number * number + coefficient_b * number + coefficient_c)

    array_length = len(transformed_numbers)
    sorted_transformed_numbers = [0] * array_length

    start_pointer = 0
    end_pointer = array_length - 1
    index = 0

    # If coefficient_a is positive, the parabola opens upwards.
    if coefficient_a >= 0:
        index = 0
        # We iterate from the beginning to build the sorted array.
        while start_pointer <= end_pointer:
            start_value = transformed_numbers[start_pointer]
            end_value = transformed_numbers[end_pointer]

            if start_value <= end_value:
                sorted_transformed_numbers[index] = start_value
                start_pointer += 1
            else:
                sorted_transformed_numbers[index] = end_value
                end_pointer -= 1
            index += 1
    # If coefficient_a is negative, the parabola opens downwards.
    else:
        index = array_length - 1
        # We iterate from the end to build the sorted array.
        while start_pointer <= end_pointer:
            start_value = transformed_numbers[start_pointer]
            end_value = transformed_numbers[end_pointer]

            if start_value <= end_value:
                sorted_transformed_numbers[index] = end_value
                end_pointer -= 1
            else:
                sorted_transformed_numbers[index] = start_value
                start_pointer += 1
            index -= 1

    # If coefficient_a is negative, reverse the sorted array.
    if coefficient_a < 0:
        return sorted_transformed_numbers
    else:
        return sorted_transformed_numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm 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 transformed values at these pointers and places the appropriate value into the result array. Since each pointer moves towards the center, the while loop iterates at most n times, where n is the number of elements in the original array. Therefore, the time complexity is directly proportional to the input size.

Space Complexity

O(N) – The algorithm creates a new array to store the transformed and sorted numbers. The size of this array is directly proportional to the number of elements in the original array, denoted as N. No other significant auxiliary data structures are used. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no elements to transform or sort.
Null input array	Throw an IllegalArgumentException or return null based on the API contract to indicate invalid input.
Array with single element	Transform the single element and return the array containing just that transformed value.
a = 0, resulting in a linear function	The transformed array will be sorted based on the sign of 'b', either ascending or descending.
a < 0, quadratic function opening downwards	The transformed array will have a peak (or valley) near x = -b/2a, requiring careful ordering.
Large values in the input array leading to integer overflow during transformation	Use long data type for intermediate calculations to prevent integer overflow.
Input array already sorted	Algorithm should handle sorted and reverse sorted input efficiently, potentially using a two-pointer approach.
a = 0 and b = 0, resulting in a constant function	All transformed values will be equal to c, and the sorted array will contain all identical values of c.

Empty input array

How to Handle:

Return an empty array since there are no elements to transform or sort.

Null input array

How to Handle:

Throw an IllegalArgumentException or return null based on the API contract to indicate invalid input.

Array with single element

How to Handle:

Transform the single element and return the array containing just that transformed value.

a = 0, resulting in a linear function

How to Handle:

The transformed array will be sorted based on the sign of 'b', either ascending or descending.

a < 0, quadratic function opening downwards

How to Handle:

The transformed array will have a peak (or valley) near x = -b/2a, requiring careful ordering.

Large values in the input array leading to integer overflow during transformation

How to Handle:

Use long data type for intermediate calculations to prevent integer overflow.

Input array already sorted

How to Handle:

Algorithm should handle sorted and reverse sorted input efficiently, potentially using a two-pointer approach.

a = 0 and b = 0, resulting in a constant function

How to Handle:

All transformed values will be equal to c, and the sorted array will contain all identical values of c.

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 `a`, `b`, and `c` in the transformation function f(x) = ax^2 + bx + c? Can they be negative, zero, or floating-point numbers?
What is the expected data type and range of values within the input `nums` array? Can it contain negative numbers, zeros, or floating-point numbers?
Can the input `nums` array be empty or null? If so, what should the function return in these cases?
Are duplicate numbers allowed in the input `nums` array, and if so, how should they be handled in the transformation and sorting process?
Is the input `nums` array guaranteed to be sorted in ascending order, or might it be unsorted?

Brute Force Solution

Approach

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

For each number we have, we apply the formula to find its transformed value.
We then gather all the transformed values into a new collection.
Finally, we arrange all the transformed values in the collection from the smallest to the largest.

Code Implementation

def sort_transformed_array_brute_force(numbers, a_coefficient, b_coefficient, c_constant):
    transformed_numbers = []

    # Transform each number using the given formula
    for number in numbers:
        transformed_value = a_coefficient * number * number + b_coefficient * number + c_constant
        transformed_numbers.append(transformed_value)

    # Sort the transformed numbers
    transformed_numbers.sort()

    return transformed_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, figure out if the quadratic function (based on the coefficients provided) opens upwards or downwards. This will help determine how the numbers are ordered after the transformation.
Find out where the vertex (or turning point) of the quadratic function is. This point determines the minimum or maximum value of the transformed numbers.
Set up two 'pointers', one at the very start of the original numbers and one at the very end.
Compare the transformed values at the start and end 'pointers'. Because of the shape of the quadratic function, one of these values will be the next largest (if the parabola opens downwards) or smallest (if it opens upwards) in our final sorted transformed set of numbers.
Place the larger (or smaller, depending on whether it opens down or up) of the transformed values into the new, sorted transformed set of numbers.
Move the correct 'pointer' (the one that gave you the placed value) either one step forward (if it was the start 'pointer') or one step backward (if it was the end 'pointer').
Repeat the comparing, placing, and moving steps until all the original numbers have been transformed and placed into the new, sorted transformed numbers.
If the parabola opens downwards, the new sorted set will contain the transformed numbers in descending order, so reverse it. If it opens upwards it is already correctly ordered.

Code Implementation

def sort_transformed_array(numbers, coefficient_a, coefficient_b, coefficient_c):
    transformed_numbers = []
    for number in numbers:
        transformed_numbers.append(coefficient_a * number * number + coefficient_b * number + coefficient_c)

    array_length = len(transformed_numbers)
    sorted_transformed_numbers = [0] * array_length

    start_pointer = 0
    end_pointer = array_length - 1
    index = 0

    # If coefficient_a is positive, the parabola opens upwards.
    if coefficient_a >= 0:
        index = 0
        # We iterate from the beginning to build the sorted array.
        while start_pointer <= end_pointer:
            start_value = transformed_numbers[start_pointer]
            end_value = transformed_numbers[end_pointer]

            if start_value <= end_value:
                sorted_transformed_numbers[index] = start_value
                start_pointer += 1
            else:
                sorted_transformed_numbers[index] = end_value
                end_pointer -= 1
            index += 1
    # If coefficient_a is negative, the parabola opens downwards.
    else:
        index = array_length - 1
        # We iterate from the end to build the sorted array.
        while start_pointer <= end_pointer:
            start_value = transformed_numbers[start_pointer]
            end_value = transformed_numbers[end_pointer]

            if start_value <= end_value:
                sorted_transformed_numbers[index] = end_value
                end_pointer -= 1
            else:
                sorted_transformed_numbers[index] = start_value
                start_pointer += 1
            index -= 1

    # If coefficient_a is negative, reverse the sorted array.
    if coefficient_a < 0:
        return sorted_transformed_numbers
    else:
        return sorted_transformed_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no elements to transform or sort.
Null input array	Throw an IllegalArgumentException or return null based on the API contract to indicate invalid input.
Array with single element	Transform the single element and return the array containing just that transformed value.
a = 0, resulting in a linear function	The transformed array will be sorted based on the sign of 'b', either ascending or descending.
a < 0, quadratic function opening downwards	The transformed array will have a peak (or valley) near x = -b/2a, requiring careful ordering.
Large values in the input array leading to integer overflow during transformation	Use long data type for intermediate calculations to prevent integer overflow.
Input array already sorted	Algorithm should handle sorted and reverse sorted input efficiently, potentially using a two-pointer approach.
a = 0 and b = 0, resulting in a constant function	All transformed values will be equal to c, and the sorted array will contain all identical values of c.

Empty input array

How to Handle:

Return an empty array since there are no elements to transform or sort.

Null input array

How to Handle:

Throw an IllegalArgumentException or return null based on the API contract to indicate invalid input.

Array with single element

How to Handle:

Transform the single element and return the array containing just that transformed value.

a = 0, resulting in a linear function

How to Handle:

The transformed array will be sorted based on the sign of 'b', either ascending or descending.

a < 0, quadratic function opening downwards

How to Handle:

The transformed array will have a peak (or valley) near x = -b/2a, requiring careful ordering.

Large values in the input array leading to integer overflow during transformation

How to Handle:

Use long data type for intermediate calculations to prevent integer overflow.

Input array already sorted

How to Handle:

Algorithm should handle sorted and reverse sorted input efficiently, potentially using a two-pointer approach.

a = 0 and b = 0, resulting in a constant function

How to Handle:

All transformed values will be equal to c, and the sorted array will contain all identical values of c.