Welcome to Subscribe On Youtube

360. Sort Transformed Array

Description

Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax2 + bx + c to each element nums[i] in the array, and return the array in a sorted order.

 

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

 

Constraints:

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

 

Follow up: Could you solve it in O(n) time?

Solutions

Similar to 302-Smallest-Rectangle-Enclosing-Black-Pixels/ using Callable/Caller to simplify code with two branches.

The provided Python code is a solution for transforming and sorting an array based on the quadratic equation f(x) = ax^2 + bx + c, where a, b, and c are given integers, and x represents elements of the input array nums. The solution uses a two-pointer approach to efficiently sort the transformed values in either ascending or descending order, depending on the coefficient a.

Code Breakdown

  1. Initialization:
    • n stores the length of the input array nums.
    • result is initialized to store the sorted transformed array, initially filled with zeros.
    • Two pointers i and j are initialized to the start and end of the array, respectively.
    • idx determines the position in the result array where the next value will be placed. Its initial value depends on the sign of a:
      • If a <= 0, the parabola opens upwards (concave up), and the smallest values are on the edges; thus, idx starts at 0.
      • If a > 0, the parabola opens downwards (concave down), and the largest values are on the edges; thus, idx starts at n - 1.
  2. Lambda Function caller:
    • This lambda function is defined to decide whether to take the left_val or right_val based on the sign of a. It facilitates the comparison condition for populating the result array with the correct order of transformed values.
  3. Main Loop:
    • The loop runs as long as i <= j, indicating that there are elements left to be considered.
    • left_val and right_val are calculated by applying the given quadratic formula to nums[i] and nums[j], respectively.
    • The caller function is used to compare left_val and right_val. Based on this comparison and the sign of a, either left_val or right_val is placed in the current idx position of the result array.
    • The pointer i is incremented if left_val is chosen, and j is decremented if right_val is chosen, moving the pointers towards the center of nums.
    • idx is adjusted accordingly after each iteration: incremented if a <= 0 (filling result from start to end) and decremented if a > 0 (filling result from end to start).
  4. Function calculate:
    • A helper method to apply the quadratic transformation to a given value x.
  • class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
        int[] res = new int[n];
        while (i <= j) {
            int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
            if (a < 0) {
                if (v1 <= v2) {
                    res[k] = v1;
                    ++i;
                } else {
                    res[k] = v2;
                    --j;
                }
                ++k;
            } else {
                if (v1 >= v2) {
                    res[k] = v1;
                    ++i;
                } else {
                    res[k] = v2;
                    --j;
                }
                --k;
            }
        }
        return res;
    }

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

  • class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size();
        int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
        vector<int> res(n);
        while (i <= j) {
            int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
            if (a < 0) {
                if (v1 <= v2) {
                    res[k] = v1;
                    ++i;
                } else {
                    res[k] = v2;
                    --j;
                }
                ++k;
            } else {
                if (v1 >= v2) {
                    res[k] = v1;
                    ++i;
                } else {
                    res[k] = v2;
                    --j;
                }
                --k;
            }
        }
        return res;
    }

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

  • class Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        n = len(nums)
        result = [0] * n
        i, j = 0, n - 1
        idx = 0 if a <= 0 else n - 1
        # This lambda function is then used to determine the comparison condition
        #   for assigning values to the result array
        caller = lambda x, y: x >= y if a >= 0 else x <= y

        while i <= j:
            left_val = self.calculate(nums[i], a, b, c)
            right_val = self.calculate(nums[j], a, b, c)

            if caller(left_val, right_val):
                result[idx] = left_val
                i += 1
            else:
                result[idx] = right_val
                j -= 1

            idx += (1 if a <= 0 else -1)

        return result

    def calculate(self, x: int, a: int, b: int, c: int) -> int:
        return a * x * x + b * x + c


#############

# reverse() will not work: if (a < 0) reverse(ans.begin(), ans.end());
class Solution:
    def sortTransformedArray(
        self, nums: List[int], a: int, b: int, c: int
    ) -> List[int]:
        def f(x):
            return a * x * x + b * x + c

        n = len(nums)
        i, j, k = 0, n - 1, 0 if a < 0 else n - 1
        res = [0] * n
        while i <= j:
            v1, v2 = f(nums[i]), f(nums[j]) # here duplicated calculation
            if a < 0:
                if v1 <= v2:
                    res[k] = v1
                    i += 1
                else:
                    res[k] = v2
                    j -= 1
                k += 1
            else:
                if v1 >= v2:
                    res[k] = v1
                    i += 1
                else:
                    res[k] = v2
                    j -= 1
                k -= 1
        return res


  • func sortTransformedArray(nums []int, a int, b int, c int) []int {
	n := len(nums)
	i, j, k := 0, n-1, 0
	if a >= 0 {
		k = n - 1
	}
	res := make([]int, n)
	for i <= j {
		v1, v2 := f(a, b, c, nums[i]), f(a, b, c, nums[j])
		if a < 0 {
			if v1 <= v2 {
				res[k] = v1
				i++
			} else {
				res[k] = v2
				j--
			}
			k++
		} else {
			if v1 >= v2 {
				res[k] = v1
				i++
			} else {
				res[k] = v2
				j--
			}
			k--
		}
	}
	return res
}

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

  • function sortTransformedArray(nums: number[], a: number, b: number, c: number): number[] {
    const f = (x: number): number => a * x * x + b * x + c;
    const n = nums.length;
    let [i, j] = [0, n - 1];
    const ans: number[] = Array(n);
    for (let k = 0; k < n; ++k) {
        const y1 = f(nums[i]);
        const y2 = f(nums[j]);
        if (a > 0) {
            if (y1 > y2) {
                ans[n - k - 1] = y1;
                ++i;
            } else {
                ans[n - k - 1] = y2;
                --j;
            }
        } else {
            if (y1 > y2) {
                ans[k] = y2;
                --j;
            } else {
                ans[k] = y1;
                ++i;
            }
        }
    }
    return ans;
}


  • /**
 * @param {number[]} nums
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number[]}
 */
var sortTransformedArray = function (nums, a, b, c) {
    const f = x => a * x * x + b * x + c;
    const n = nums.length;
    let [i, j] = [0, n - 1];
    const ans = Array(n);
    for (let k = 0; k < n; ++k) {
        const y1 = f(nums[i]);
        const y2 = f(nums[j]);
        if (a > 0) {
            if (y1 > y2) {
                ans[n - k - 1] = y1;
                ++i;
            } else {
                ans[n - k - 1] = y2;
                --j;
            }
        } else {
            if (y1 > y2) {
                ans[k] = y2;
                --j;
            } else {
                ans[k] = y1;
                ++i;
            }
        }
    }
    return ans;
};

All Problems

All Solutions