Sorted Parabola Values

Medium

You are given an integer array xs sorted in non-decreasing order and three integer coefficients a, b and c. Plug every element x into f(x) = a·x² + b·x + c and return all the resulting values in non-decreasing order. Sorting the results directly in O(n log n) is easy. Can you do it in O(n) by using the fact that xs is already sorted?

Example 1

xs=[-3, -1, 0, 2], a=2, b=0, c=-1 → [-1, 1, 7, 17]

f(x) = 2x² − 1 gives 17, 1, −1, 7; in ascending order: −1, 1, 7, 17.

Example 2

xs=[-2, 0, 1, 3], a=-1, b=2, c=4 → [-4, 1, 4, 5]

f(x) = −x² + 2x + 4 gives −4, 4, 5, 1; in ascending order: −4, 1, 4, 5.

Example 3

xs=[1, 4, 6], a=0, b=-3, c=2 → [-16, -10, -1]

Constraints

1 ≤ len(xs) ≤ 200
-100 ≤ xs[i], a, b, c ≤ 100
xs is sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Two Pointers Sorting

Similar problems

End Stones Close Ranks Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Flags in Three Colors Medium

Input

xs=[-3, -1, 0, 2], a=2, b=0, c=-1

Expected

[-1, 1, 7, 17]

Run checks the first 3 tests in your browser. Submit checks all 123 tests on the server, hidden ones included.