Sort Transformed Array - Practice Coding Problems

Sort Transformed Array - Problem

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

The quadratic function transforms each element, and the resulting values need to be sorted before returning.

Note: The input array is already sorted, but after applying the quadratic transformation, the order may change depending on the coefficients.

Input & Output

Example 1 — Upward Parabola

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

› Output: [3,9,15,33]

💡 Note: f(x) = x² + 3x + 5. f(-4) = 16-12+5 = 9, f(-2) = 4-6+5 = 3, f(2) = 4+6+5 = 15, f(4) = 16+12+5 = 33. Sorted: [3,9,15,33]

Example 2 — Downward Parabola

$ Input: nums = [-2,-1,0,1,2], a = -1, b = 2, c = 1

› Output: [-3,-1,1,1,-3]

💡 Note: f(x) = -x² + 2x + 1. f(-2) = -4-4+1 = -7, f(-1) = -1-2+1 = -2, f(0) = 1, f(1) = -1+2+1 = 2, f(2) = -4+4+1 = 1. Sorted: [-7,-2,1,1,2]

Example 3 — Linear Case

$ Input: nums = [1,2,3], a = 0, b = 2, c = 1

› Output: [3,5,7]

💡 Note: f(x) = 2x + 1 (linear). f(1) = 3, f(2) = 5, f(3) = 7. Already sorted since input is sorted and coefficient is positive.

Constraints

1 ≤ nums.length ≤ 200
-100 ≤ nums[i] ≤ 100
-10⁴ ≤ a, b, c ≤ 10⁴
nums is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array nums and quadratic coefficients a, b, c

Transform

Apply f(x) = ax² + bx + c to each element

Sort

Return transformed values in sorted order

Key Takeaway

🎯 Key Insight: Parabolas have extreme values at the ends - use two pointers to build result in O(n) time instead of O(n log n) sorting

Asked in

G Google 25 f Facebook 18 M Microsoft 12

The key insight is recognizing that quadratic functions form parabolas - for upward parabolas (a ≥ 0), extreme values are at the ends of a sorted array. Best approach uses two pointers to compare values from both ends and build result efficiently. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Transform and Sort	O(n log n)	O(n)	Apply quadratic function to all elements, then sort the result
Two Pointers Approach	O(n)	O(1)	Use two pointers from both ends, leveraging parabola properties

Transform and Sort — Algorithm Steps

Apply f(x) = ax² + bx + c to each element
Store transformed values in result array
Sort the result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Apply f(x) = ax² + bx + c to each element

Sort

Sort the transformed values

Result

Return sorted transformed array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int numsSize, int a, int b, int c, int* returnSize) {
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;
    
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        result[i] = a * x * x + b * x + c;
    }
    
    qsort(result, numsSize, sizeof(int), compare);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int returnSize;
    int* result = solution(nums, numsSize, a, b, c, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) for transformation + O(n log n) for sorting

⚡ Linearithmic

Space Complexity

O(n)

New array to store transformed values

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~18 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Transform and Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler