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


  • 0
    M

    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
        }
    }
    

Log in to reply
 

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