# Swift short and clear O(n) solution with full comments

• To achieve an O(n) runtime, you need to have the insight that x^2 + x will form a parabola. You also need the sight that parameter A will cause the parabola to be either concave or convex. Once you have those, the implementation becomes clear.

``````class Solution {
func sortTransformedArray(_ nums: [Int], _ a: Int, _ b: Int, _ c: Int) -> [Int] {
// #1 insight: x^2 + x + 1 forms a parabola
// fill a calc array with the results
var calc: [Int] = []
for x in nums {
calc.append(a*x*x + b*x + c)
}

// #2 insight: param A dictates the shape of the parabola
// walk the calc results from low to high or high to low based on the
// sign of param A
var result: [Int] = []
if a < 0 {
// tails are low since x*x negates negative X values and negative
// param A amplifies the most significant component negatively
while !calc.isEmpty {
let val = calc.first! < calc.last! ? calc.removeFirst() : calc.removeLast()
// build from low to high, appending progressively larger values
result.append(val)
}
} else {
// tails are high since x*x negates negative X values and positive
// param A amplifies the most siginificant component positively
while !calc.isEmpty {
let val = calc.first! > calc.last! ? calc.removeFirst() : calc.removeLast()
// build from high to low, inserting progressively smaller values at index 0
result.insert(val, at: 0)
}
}

return result
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.