360. Sort Transformed Array

Problem Description

We're given an array nums which is sorted in ascending order, and three integers a, b, and c. These three integers are coefficients of a quadratic function f(x) = ax^2 + bx + c. Our task is to apply this function to each element in the array and then return the array with its elements sorted after the transformation. This transformed and sorted array needs to adhere to the standard non-decreasing order.

Intuition

The key to solving this problem lies in understanding how a quadratic function behaves. Depending on the value of the leading coefficient a, the graph of the function is either a parabola opening upwards (a > 0) or downwards (a < 0). When a > 0, the function's values are minimized at the vertex, and as you move away from the vertex, the values increase. When a < 0, the scenario is flipped; the values are maximized at the vertex, and as you move away, they decrease.

This understanding informs us that the transformed array will have its smallest or largest values at the ends if a is nonzero. If a is equal to 0, the function is linear, and the transformed array will maintain the same order as the input array, scaled and shifted by b and c.

The solution leverages this by comparing the transformed values of the start i and end j of the array nums, filling in the result array res from the start or the end, depending on the sign of a. With each comparison, it picks the extreme (either smallest or largest) of the transformed values and then increments or decrements the pointers accordingly.

For a < 0, we fill the res array from the beginning because we find that the smallest values will occur at the ends of the original array. Conversely, for a > 0, we fill the res array from the end because we'll encounter the largest values at the ends of the original array due to the "U" shape of the function.

The solution continues this process of comparison and selection until all elements in the input array have been transformed and placed in the result array in sorted order.

Learn more about Math, Two Pointers and Sorting patterns.

Solution Approach

The solution to this problem uses a two-pointer technique and knowledge of the properties of quadratic functions. The two-pointer technique is an algorithmic pattern where two pointers are used to iterate through the data structure—typically an array or string—usually from the beginning and end, to converge at some condition.

Here's a step-by-step breakdown based on the given Solution class and its method:

Function Definition - f(x): The method sortTransformedArray includes a nested function f(x) which applies the quadratic transformation to a passed value x. Applying f(x) to any number will give us the result of the quadratic function for that number, using the formula f(x) = ax^2 + bx + c.
Initialize Pointers and Result Array:
- Two pointers i (starting at 0) and j (starting at n - 1) are used, where n is the length of the original array nums.
- The pointer k is initialized differently based on the sign of a:
  - If a is negative (a < 0), k starts from 0 to fill in the result array from the start.
  - If a is positive (a >= 0), k starts from n - 1 to fill in the result array from the end.
Comparing and Filling the Result Array:
- We iterate while i is less than or equal to j.
- For each iteration, we calculate f(nums[i]) and f(nums[j]).
- We compare the transformed values, v1 and v2, and select the appropriate one based on the sign of a:
  - For a < 0, if v1 is less than or equal to v2, v1 is selected to fill the current position in the result array res[k], and i is incremented. Else, v2 is selected, and j is decremented. Pointer k is also incremented because we fill the res from the start.
  - For a >= 0, if v1 is greater than or equal to v2, v1 is selected to fill res[k], and i is incremented. Else, v2 is selected, and j is decremented. Here, k is decremented because we fill the res from the end.
Return the Transformed and Sorted Array:
- After the loop completes, every position in the res array has been filled correctly.
- The res array is then returned. It contains the elements of nums transformed by f(x) in sorted order.

The choice of whether to fill the result array from the start or end and the comparison logic within the loop all hinge on the behavior of the quadratic function. The two-pointer technique ensures that we traverse the array exactly once, giving us a time-efficient solution with O(n) complexity, where n is the number of elements in nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have the following array and coefficients for our quadratic function:

nums: [1, 2, 3, 4, 5]
a: -1
b: 0
c: 0

The quadratic function is f(x) = -x^2 + 0x + 0, which simplifies to f(x) = -x^2.

Step-by-Step Walkthrough:

Apply the Function f(x): To predict how the final array will look after applying f(x) to each element, we note that with a < 0, the function value is maximized at the vertex, and it decreases as we move away from the vertex. Since our nums array is sorted, the smallest transformed values will be at the ends, and the largest at the center.
Initialize Pointers and Result Array:
- We set pointers i = 0 and j = 4 since nums has 5 elements.
- Since a is negative (-1 in our case), we initialize the pointer k to fill the res array from the start. So k = 0.
Comparing and Filling the Result Array:
- We calculate f(nums[i]) which is f(1) = -1^2 = -1, and f(nums[j]) which is f(5) = -5^2 = -25.
- Since a < 0, we compare and find that f(nums[i]) > f(nums[j]), so we place -1 in res[0], and increment i to 1 and k to 1.
- We continue this process, comparing the transformed values at each end and always choosing the larger one, filling res sequentially as we go along:
  - Compare f(nums[i = 1]) = -2^2 = -4 and f(nums[j = 4]) = -25, put -4 in res[1], increment i to 2 and k to 2.
  - Compare f(nums[i = 2]) = -3^2 = -9 and f(nums[j = 4]) = -25, put -9 in res[2], increment i to 3 and k to 3.
  - Compare f(nums[i = 3]) = -4^2 = -16 and f(nums[j = 4]) = -25, put -16 in res[3], increment i to 4 and k to 4.
  - Now i equals j, we have one element left: f(nums[j = 4]) = -25, we put -25 in res[4].
Return the Transformed and Sorted Array:
- After iterating through the entire array, our result array res is fully populated with the transformed elements in sorted order: [-25, -16, -9, -4, -1].
- We return the res array.

By following the logic laid out in the solution approach and considering the properties of the quadratic function, we've successfully transformed the nums array and returned it sorted in non-decreasing order as required.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sort_transformed_array(
5        self, nums: List[int], a: int, b: int, c: int
6    ) -> List[int]:
7        # Function to calculate the transformed value based on input x
8        def quadratic(x):
9            return a * x ** 2 + b * x + c
10
11        # length of the input nums list
12        n = len(nums)
13      
14        # Initialize pointers:
15        # 'left' to start of array, 'right' to end of array
16        # 'index' to either start or end based on sign of a
17        left, right = 0, n - 1
18        index = 0 if a < 0 else n - 1
19      
20        # Initialize the result array with zeros
21        result = [0] * n
22      
23        # Iterate through the array until left exceeds right
24        while left <= right:
25            # Calculate the transformed values for both ends
26            left_val = quadratic(nums[left])
27            right_val = quadratic(nums[right])
28          
29            # If 'a' is negative, parabola opens downward.
30            # Smaller values are closer to the ends of the array.
31            if a < 0:
32                if left_val <= right_val:
33                    result[index] = left_val
34                    left += 1
35                else:
36                    result[index] = right_val
37                    right -= 1
38                index += 1
39            else:
40                # If 'a' is non-negative, parabola opens upward.
41                # Larger values are closer to the ends of the array.
42                if left_val >= right_val:
43                    result[index] = left_val
44                    left += 1
45                else:
46                    result[index] = right_val
47                    right -= 1
48                index -= 1
49      
50        # Return the sorted transformed array
51        return result
52

1class Solution {
2
3    // This method sorts a transformed array generated by applying a quadratic function to an input array.
4    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
5        int length = nums.length;
6
7        // Two pointers initialized to the start and end of the array respectively.
8        int startIndex = 0, endIndex = length - 1;
9
10        // Determine the sorting direction based on the leading coefficient 'a'.
11        // If 'a' is negative, sort ascending, otherwise sort descending.
12        int sortIndex = a < 0 ? 0 : length - 1;
13
14        // Create an array to store the result.
15        int[] result = new int[length];
16
17        // Use a while loop to process elements from both ends of the input array.
18        while (startIndex <= endIndex) {
19
20            // Apply the quadratic function to the elements at the start and end indices.
21            int transformedStart = applyQuadraticFunction(a, b, c, nums[startIndex]);
22            int transformedEnd = applyQuadraticFunction(a, b, c, nums[endIndex]);
23
24            // If 'a' is negative, we fill the result array starting from the beginning.
25            if (a < 0) {
26                if (transformedStart <= transformedEnd) {
27                    result[sortIndex] = transformedStart;
28                    startIndex++;
29                } else {
30                    result[sortIndex] = transformedEnd;
31                    endIndex--;
32                }
33                sortIndex++;
34
35            // If 'a' is positive, we fill the result array starting from the end.
36            } else {
37                if (transformedStart >= transformedEnd) {
38                    result[sortIndex] = transformedStart;
39                    startIndex++;
40                } else {
41                    result[sortIndex] = transformedEnd;
42                    endIndex--;
43                }
44                sortIndex--;
45            }
46        }
47
48        // Return the sorted transformed array.
49        return result;
50    }
51
52    // This helper method applies a quadratic function to the input value x.
53    private int applyQuadraticFunction(int a, int b, int c, int x) {
54        return a * x * x + b * x + c;
55    }
56}
57

1class Solution {
2public:
3    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
4        int n = nums.size(); // Size of the input vector nums
5
6        // Initialize two pointers for the start and end of the vector, and k for the position to fill in the result array
7        int start = 0, end = n - 1;
8        // If 'a' is positive, fill the result from the end; otherwise, from the start
9        int k = a >= 0 ? n - 1 : 0;
10
11        vector<int> result(n); // Initialize the result vector with the same size as nums
12        while (start <= end) {
13            // Apply the quadratic function to the current elements at the start and end pointers
14            int transformedStart = quadratic(a, b, c, nums[start]);
15            int transformedEnd = quadratic(a, b, c, nums[end]);
16
17            if (a >= 0) {
18                // For a positive 'a', larger values will be on the ends of the resulting array
19                if (transformedStart >= transformedEnd) {
20                    result[k--] = transformedStart; // Assign and then decrement k
21                    start++; // Move start pointer to the right
22                } else {
23                    result[k--] = transformedEnd; // Assign and then decrement k
24                    end--; // Move end pointer to the left
25                }
26            } else {
27                // For a non-positive 'a', smaller values will be at the start of the resulting array
28                if (transformedStart <= transformedEnd) {
29                    result[k++] = transformedStart; // Assign and then increment k
30                    start++; // Move start pointer to the right
31                } else {
32                    result[k++] = transformedEnd; // Assign and then increment k
33                    end--; // Move end pointer to the left
34                }
35            }
36        }
37        return result; // Return the sorted and transformed array
38    }
39
40    // Helper function to apply the quadratic formula
41    int quadratic(int a, int b, int c, int x) {
42        return a * x * x + b * x + c; // Calculate ax^2 + bx + c
43    }
44};
45

1// Function to transform the array using the quadratic equation ax^2 + bx + c
2function sortTransformedArray(nums: number[], a: number, b: number, c: number): number[] {
3    const n: number = nums.length; // Size of the input array nums
4
5    // Initialize two pointers for the start and end of the array, and index for the position to fill in the result array
6    let start: number = 0, end: number = n - 1;
7    // If 'a' is positive, fill the result from the end; otherwise, from the start
8    let index: number = a >= 0 ? n - 1 : 0;
9
10    const result: number[] = new Array(n); // Initialize the result array with the same size as nums
11    while (start <= end) {
12        // Apply the quadratic function to the current elements at the start and end pointers
13        const transformedStart: number = quadratic(a, b, c, nums[start]);
14        const transformedEnd: number = quadratic(a, b, c, nums[end]);
15
16        if (a >= 0) {
17            // For a positive 'a', larger values will be on the ends of the resulting array
18            if (transformedStart >= transformedEnd) {
19                result[index--] = transformedStart; // Assign and then decrement index
20                start++; // Move start pointer to the right
21            } else {
22                result[index--] = transformedEnd; // Assign and then decrement index
23                end--; // Move end pointer to the left
24            }
25        } else {
26            // For a non-positive 'a', smaller values will be at the start of the resulting array
27            if (transformedStart <= transformedEnd) {
28                result[index++] = transformedStart; // Assign and then increment index
29                start++; // Move start pointer to the right
30            } else {
31                result[index++] = transformedEnd; // Assign and then increment index
32                end--; // Move end pointer to the left
33            }
34        }
35    }
36    return result; // Return the sorted and transformed array
37}
38
39// Function to evaluate the quadratic equation ax^2 + bx + c
40function quadratic(a: number, b: number, c: number, x: number): number {
41    return a * x * x + b * x + c; // Calculate ax^2 + bx + c
42}
43

Time and Space Complexity

The given code has a time complexity of O(n), where n is the number of elements in the provided nums list. This is because it processes each element in the list exactly once. Despite having a while loop that iterates while i <= j, no element is ever processed more than once due to the pointers i and j moving towards the center from the ends. The function f(x) is called twice per iteration, but it executes in constant time O(1), thereby not affecting the overall linear time complexity.

The space complexity of the solution is also O(n), as it creates a new list res of size n to store the transformed and sorted values. The rest of the variables i, j, k, v1, and v2 use constant space, so the main contributing factor to the space complexity is the res array.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know