Sort the given array after applying the given equation

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Sort array after applying f(x) = ax^2 + bx + c transformation. Two-pointer from sorted ends.

Algorithm

1If a >= 0: parabola opens up, min at vertex, max at ends. Two pointers fill result from ends.
2If a < 0: max at vertex, fill from middle.

Common Pitfalls

•Same as LC 360. O(n) two-pointer after O(n log n) sort. Direction depends on sign of a.

Sort the given array after applying the given equation.java

Java

// Approach: Apply the equation to all elements, sort the result (or use two-pointer since input is sorted).
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> sortArray(int[] arr, int A, int B, int C) {
        ArrayList<Integer> al = new ArrayList<>();
        for (int i : arr)
            al.add(A * (int) Math.pow(i, 2) + B * i + C);
        Collections.sort(al);
        return al;
    }
}

Was this solution helpful?