Sort Transformed Array

Medium Arrays & Hashing Two Pointer Original on LeetCode

Reported atLinkedInZomato

Sort Transformed Array is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers from the ends), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (transform, then sort) up.

Problem

You are given an integer array nums sorted in non-decreasing order and three integers a, b and c. Apply the quadratic function f(x) = a·x² + b·x + c to every element.

Return the transformed values as an array sorted in non-decreasing order.

Can you do it in O(n) time, without a general-purpose sort?

Examples

Example 1

Input
nums = [-3,-1,0,2,5], a = 1, b = -2, c = 1
Output
[1,1,4,16,16]
Why
f(x) = x² - 2x + 1 = (x - 1)² maps the values to 16, 4, 1, 1, 16, which sorted are [1,1,4,16,16].

Example 2

Input
nums = [-2,0,3], a = 0, b = -3, c = 4
Output
[-5,4,10]
Why
With a = 0 the function is the line -3x + 4, which reverses the order: 10, 4, -5.

Example 3

Input
nums = [-4,-2,1,3], a = -1, b = 0, c = 10
Output
[-6,1,6,9]
Why
The parabola opens downward, so the values far from 0 become the smallest: -6, 6, 9, 1 sorted.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (transform, then sort)O(n log n)O(n)
Optimal (two pointers from the ends)O(n)O(n)

1Brute force (transform, then sort)

TimeO(n log n)The transform is linear and the sort costs n log n.
SpaceO(n)The output array.

Compute f(x) for every element and sort the results.

  1. res[i] = a · nums[i]² + b · nums[i] + c.
  2. Sort res and return it.
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = a * nums[i] * nums[i] + b * nums[i] + c;
        Arrays.sort(res);
        return res;
    }
}

2Optimal (two pointers from the ends)

TimeO(n)Each step places one value and moves one pointer.
SpaceO(n)Only the output array; O(1) extra besides it.

A quadratic is monotonic on each side of its vertex, so for a sorted input the extreme results sit at the two ends. If a >= 0 the ends hold the largest values, so fill the output from the back with the larger of f(nums[left]) and f(nums[right]). If a < 0 the ends hold the smallest values, so fill from the front with the smaller one. A straight line (a = 0) works with either rule.

  1. left = 0, right = n - 1; idx = a >= 0 ? n - 1 : 0.
  2. While left <= right: fl = f(nums[left]), fr = f(nums[right]).
  3. If a >= 0: put max(fl, fr) at res[idx--] and move that pointer inward.
  4. Else: put min(fl, fr) at res[idx++] and move that pointer inward.
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1;
        int idx = a >= 0 ? n - 1 : 0;
        while (left <= right) {
            int fl = f(nums[left], a, b, c), fr = f(nums[right], a, b, c);
            if (a >= 0) {
                if (fl >= fr) { res[idx--] = fl; left++; }
                else { res[idx--] = fr; right--; }
            } else {
                if (fl <= fr) { res[idx++] = fl; left++; }
                else { res[idx++] = fr; right--; }
            }
        }
        return res;
    }

    private int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}

Edge cases to test

  • a = 0: the function is a straight line (increasing, decreasing, or constant when b = 0 too)
  • a < 0: the parabola opens downward
  • All inputs on one side of the vertex, so the result keeps or reverses the input order
  • Duplicate values in nums
  • A single element

Hints

Hint 1

The simplest correct answer: apply the function to each value and sort.

Hint 2

For a > 0 the parabola is U-shaped: the largest results come from the two ends of the sorted input, and they shrink toward the vertex.

Hint 3

Use two pointers at the ends. If a >= 0, repeatedly place the larger of f(left) and f(right) at the back of the output; if a < 0, place the smaller one at the front.

FAQ

What is the best time complexity for Sort Transformed Array?

Optimal (two pointers from the ends) runs in O(n) time and O(n) extra space. Each step places one value and moves one pointer.

Which pattern does Sort Transformed Array use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Sort Transformed Array?

Yes. Brute force (transform, then sort) takes O(n log n) time and O(n) space. Compute f(x) for every element and sort the results.

Which edge cases should I test for Sort Transformed Array?

a = 0: the function is a straight line (increasing, decreasing, or constant when b = 0 too); a < 0: the parabola opens downward; All inputs on one side of the vertex, so the result keeps or reverses the input order; Duplicate values in nums; A single element.