Sort Transformed Array (Apply Quadratic)

📋

Problem

Imagine you have a list of numbers representing heights of hills, and you want to apply a quadratic transformation to model some physical property, then sort the results efficiently.

Given a sorted integer array nums and integers a, b, and c representing a quadratic function f(x) = ax^2 + bx + c, apply the function to each element in nums and return the resulting array in sorted order.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i], a, b, c ≤ 10^4nums is sorted in ascending order

Edge cases: All elements are the same → output is all transformed values, same ordera = 0 (linear function) → output is sorted if b ≥ 0, reversed if b < 0a > 0 and nums sorted ascending → transformed array has a 'valley' shape

</>

IDE

def sortTransformedArray(nums: list[int], a: int, b: int, c: int) -> list[int]:public int[] sortTransformedArray(int[] nums, int a, int b, int c)vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c)function sortTransformedArray(nums, a, b, c)

def sortTransformedArray(nums, a, b, c):
    # Write your solution here
    pass

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    // Write your solution here
    return {};
}

function sortTransformedArray(nums, a, b, c) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [9, 3, 15, 33]Applied quadratic function but forgot to sort the transformed array.✅ Add a sorting step after applying the quadratic function to all elements.

Wrong: [-23, -2, 1, 2]Incorrect calculation of quadratic function values, especially sign errors with negative a.✅ Compute f(x) = a*x*x + b*x + c carefully, respecting signs and order of operations.

Wrong: [] or errorFunction does not handle empty input array properly, causing crash or wrong output.✅ Add a check for empty input and return empty list immediately.

Wrong: [8]Incorrect transformation for single element, possibly missing negative sign or wrong formula.✅ Apply f(x) = a*x*x + b*x + c correctly for single element input.

Wrong: [4, 1, 1, 0, 0]Incorrect handling of parabola shape; not using two-pointer approach to fill output in correct order.✅ Implement two-pointer approach filling output from ends inward based on sign of a.

Wrong: [3, 1, 0, -1, -3]Linear case with a=0 and b<0 not reversed to maintain sorted order.✅ Reverse output array when a=0 and b<0 to ensure sorted ascending order.

Wrong: [-1, -4, -9, -16, -25]Incorrect ordering for negative a parabola; output not sorted ascending.✅ Fill output array from start to end when a < 0 to maintain ascending order.

Wrong: TLE or timeoutUsing O(n log n) sorting after transformation instead of O(n) two-pointer approach.✅ Implement O(n) two-pointer approach exploiting parabola shape to avoid sorting.

✓

Test Cases

Try testing your solution on empty and single-element arrays to catch base case bugs.

Consider how the parabola shape affects the order of transformed values and test accordingly.

Think about how to avoid sorting by using two pointers exploiting the parabola shape.

t1_01basic

Input{"nums":[-4,-2,2,4],"a":1,"b":3,"c":5}

Expected[3,9,15,33]

⏱ Performance - must finish in 2000ms

Applying f(x) = x^2 + 3x + 5 to each element gives [9, 3, 15, 33]. Sorting these results in [3, 9, 15, 33].

💡 Apply the quadratic function to each element, then sort the results.

💡 Remember that the parabola shape affects the order of transformed values.

💡 Sort the transformed array after applying f(x) = ax^2 + bx + c.

Why it failed: Incorrect output means either the quadratic function was applied wrongly or sorting was missed. Fix by applying f(x) = a*x*x + b*x + c correctly and then sorting the array.

✓ Correctly applied quadratic and sorted transformed array.

t1_02basic

Input{"nums":[-3,0,1,2],"a":-1,"b":4,"c":-2}

Expected[-23,-2,1,2]

⏱ Performance - must finish in 2000ms

Applying f(x) = -x^2 + 4x - 2 gives f(-3) = -9 -12 -2 = -23, f(0) = -2, f(1) = 1, f(2) = 2. Sorted output is [-23, -2, 1, 2].

💡 Apply the quadratic function carefully to each element.

💡 Check signs when a is negative; parabola opens downward.

💡 Sort the transformed array after applying f(x).

Why it failed: Wrong output likely due to incorrect quadratic calculation or missing sort. Fix by correctly computing f(x) = a*x*x + b*x + c and sorting the results.

✓ Correctly handled negative 'a' and sorted transformed array.

t2_01edge

Input{"nums":[],"a":2,"b":3,"c":4}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array returns empty output.

💡 Consider what happens when input array is empty.

💡 Function should handle zero-length input gracefully.

💡 Return an empty array immediately if nums is empty.

Why it failed: Function crashes or returns non-empty output on empty input. Fix by adding a check for empty input and returning empty list.

✓ Correctly handles empty input array.

t2_02edge

Input{"nums":[5],"a":0,"b":-3,"c":7}

Expected[-8]

⏱ Performance - must finish in 2000ms

Single element with linear function f(x) = -3x + 7; f(5) = -15 + 7 = -8.

💡 Test single element input with linear function (a=0).

💡 Check that function handles single element without error.

💡 Return array with single transformed value.

Why it failed: Incorrect output for single element input, possibly due to indexing errors. Fix by ensuring single element is transformed and returned correctly.

✓ Correctly transforms and returns single element array.

t2_03edge

Input{"nums":[-10000,0,10000],"a":0,"b":0,"c":0}

Expected[0,0,0]

⏱ Performance - must finish in 2000ms

Function f(x) = 0; all transformed values are zero, output sorted as [0,0,0].

💡 Test boundary values with zero coefficients.

💡 Check that function returns correct constant output.

💡 Return array of zeros matching input length.

Why it failed: Incorrect output when all coefficients zero, possibly due to missing constant term. Fix by returning array of c repeated for each element.

✓ Correctly handles zero function coefficients.

t3_01corner

Input{"nums":[-2,-1,0,1,2],"a":1,"b":0,"c":0}

Expected[0,1,1,4,4]

⏱ Performance - must finish in 2000ms

f(x) = x^2; transformed values are [4, 1, 0, 1, 4], sorted is [0, 1, 1, 4, 4].

💡 Check if your solution handles the 'valley' shape correctly when a > 0.

💡 Use two pointers from ends to fill output from largest to smallest or vice versa.

💡 Fill output array from ends inward depending on parabola direction.

Why it failed: Failing this test means your solution does not handle the parabola shape correctly, likely missing two-pointer approach. Fix by implementing two-pointer fill based on a's sign.

✓ Correctly handles parabola valley shape with two-pointer approach.

t3_02corner

Input{"nums":[-3,-1,0,1,3],"a":0,"b":-1,"c":0}

Expected[-3,-1,0,1,3]

⏱ Performance - must finish in 2000ms

Linear function f(x) = -x; input sorted ascending, output is reversed input, so sorted output is [-3, -1, 0, 1, 3].

💡 Check if your solution handles linear case (a=0) correctly.

💡 If a=0, output is sorted ascending if b>=0 else descending.

💡 Reverse the transformed array if b < 0 to maintain sorted order.

Why it failed: Failing this test means linear case is not handled properly, likely missing reversal when b < 0. Fix by reversing output when a=0 and b<0.

✓ Correctly handles linear function with proper ordering.

t3_03corner

Input{"nums":[1,2,3,4,5],"a":-1,"b":0,"c":0}

Expected[-25,-16,-9,-4,-1]

⏱ Performance - must finish in 2000ms

f(x) = -x^2; transformed values are [-1, -4, -9, -16, -25], sorted ascending is [-25, -16, -9, -4, -1].

💡 Check if your solution handles 'hill' shape correctly when a < 0.

💡 Use two pointers from ends to fill output from smallest to largest.

💡 Fill output array from start to end based on parabola direction.

Why it failed: Failing this test means incorrect handling of negative a parabola shape, likely filling output in wrong order. Fix by adjusting two-pointer fill direction for a < 0.

✓ Correctly handles parabola hill shape with two-pointer approach.

t4_01performance

Input{"nums":[-10000,-99980,-99960,-99940,-99920,-99900,-99880,-99860,-99840,-99820,-99800,-99780,-99760,-99740,-99720,-99700,-99680,-99660,-99640,-99620,-99600,-99580,-99560,-99540,-99520,-99500,-99480,-99460,-99440,-99420,-99400,-99380,-99360,-99340,-99320,-99300,-99280,-99260,-99240,-99220,-99200,-99180,-99160,-99140,-99120,-99100,-99080,-99060,-99040,-99020,-99000,-98980,-98960,-98940,-98920,-98900,-98880,-98860,-98840,-98820,-98800,-98780,-98760,-98740,-98720,-98700,-98680,-98660,-98640,-98620,-98600,-98580,-98560,-98540,-98520,-98500,-98480,-98460,-98440,-98420,-98400,-98380,-98360,-98340,-98320,-98300,-98280,-98260,-98240,-98220,-98200,-98180,-98160,-98140,-98120,-98100,-98080,-98060,-98040,-98020,-98000],"a":2,"b":-3,"c":5}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 with quadratic function; O(n) solution must complete within 2 seconds.

💡 Brute force O(n log n) may pass but is slower than O(n) two-pointer approach.

💡 Use two pointers to fill output array from ends based on parabola shape.

💡 Avoid sorting after transformation to achieve O(n) time.

Why it failed: Solution times out due to O(n log n) or worse complexity. Fix by implementing O(n) two-pointer approach exploiting parabola shape.

✓ Solution runs within time limit using O(n) two-pointer approach.

Practice

1. You are given an array containing only three distinct values representing colors: red, white, and blue. The goal is to sort the array so that all reds come first, followed by whites, then blues, in a single pass with constant extra space. Which algorithmic approach guarantees this optimal solution?

easy

A. Use a standard comparison-based sort like quicksort or mergesort to sort the array.

B. Use a three-pointer partitioning approach that rearranges elements in one pass, known as the Dutch National Flag algorithm.

C. Count the occurrences of each color and then overwrite the array in multiple passes.

D. Use dynamic programming to decide the position of each color based on previous states.

Solution

1. Step 1: Understand the problem constraints

   The problem requires sorting three distinct values in a single pass with O(1) extra space.

2. Step 2: Identify the algorithm that meets these constraints

   The Dutch National Flag algorithm uses three pointers to partition the array in one pass without extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   One-pass, constant space sorting of three distinct values matches Dutch National Flag algorithm [OK]

Hint: One-pass, three-pointer partitioning solves this optimally [OK]

Common Mistakes:

• Thinking counting sort is optimal despite multiple passes
• Assuming comparison-based sorts are needed
• Confusing DP with sorting problems

2. What is the time complexity of the bucket sort / pigeonhole principle approach to find the maximum gap in an unsorted array of size n, assuming the numbers are integers within a known range [min, max]? Choose the most accurate complexity considering both sorting and bucket operations.

medium

A. O(n) because bucket distribution and scanning are linear

B. O(n + k) where k is the number of buckets, which can be up to n+1

C. O(n log n) due to sorting the entire array

D. O(n²) because of nested bucket comparisons

Solution

1. Step 1: Understand bucket sort steps

   Bucket sort distributes n elements into k buckets, then scans buckets to find max gap.

2. Step 2: Analyze complexity components

   Distribution is O(n), scanning buckets is O(k). Since k ≈ n+1, total is O(n + k) = O(n).

3. Step 3: Simplify complexity

   Because k is proportional to n, O(n + k) simplifies to O(n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bucket count k depends on input range but is linear in n [OK]

Hint: Bucket count k is linear in n, so O(n + k) = O(n) [OK]

Common Mistakes:

• Assuming sorting is always O(n log n)
• Ignoring bucket count impact
• Confusing bucket scanning with nested loops

3. The following code attempts to find the minimum absolute difference but contains a subtle bug. Which line causes incorrect results?

def minimum_abs_difference(arr):
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff < min_diff:
            min_diff = diff
    arr.sort()
    return min_diff

medium

A. Line 2: initializing min_diff before sorting

B. Line 6: sorting after scanning pairs

C. Line 7: returning min_diff without recomputing

D. Line 3: iterating without sorting first

Solution

1. Step 1: Identify order of operations

   The array is scanned for differences before sorting, so adjacent pairs are not guaranteed to be closest.

2. Step 2: Pinpoint the bug

   Line 3 iterates over unsorted array, causing incorrect min_diff.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting must happen before scanning adjacent pairs [OK]

Hint: Must sort before scanning adjacent pairs [OK]

Common Mistakes:

• Sorting after scanning
• Not updating min_diff correctly

4. What is the time complexity of the optimal diagonal sorting algorithm that uses a min-heap per diagonal for an m x n matrix, where each diagonal is sorted independently?

medium

A. O(m * n * min(m, n)) because sorting each diagonal requires scanning all elements multiple times.

B. O(m * n * log(m * n)) because all elements are pushed into heaps together.

C. O(m * n) because each element is processed once with constant-time heap operations.

D. O(m * n * log(min(m, n))) because each diagonal has at most min(m, n) elements and heap operations cost log of diagonal length.

Solution

1. Step 1: Identify diagonal lengths

   Each diagonal has at most min(m, n) elements, so heap operations per element cost O(log(min(m, n))).

2. Step 2: Calculate total heap operations

   All m*n elements are pushed and popped once, each operation O(log(min(m, n))). Total time is O(m * n * log(min(m, n))).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap operations dominate and depend on diagonal length, not total elements [OK]

Hint: Heap ops cost log of diagonal length, not total elements [OK]

Common Mistakes:

• Assuming log(m*n) instead of log(min(m,n))
• Ignoring heap operation cost
• Mistaking linear heap ops for constant time

5. Suppose the problem is modified so that elements can be reused unlimited times to form an infinitely long array with no two adjacent elements equal. Which modification to the heap-based algorithm correctly handles this variant?

hard

A. Remove the max frequency check and keep pushing elements back with updated counts indefinitely.

B. Use a queue instead of a heap to cycle through elements ensuring no two adjacent are equal.

C. Use a max heap but reset counts to original frequencies after each full pass through the heap.

D. Modify the algorithm to never decrement counts and always push elements back to allow infinite reuse.

Solution

1. Step 1: Understand infinite reuse implication

   Since elements can be reused unlimited times, counts do not decrease; the algorithm must allow repeated placement without decrementing counts.

2. Step 2: Modify heap usage accordingly

   Never decrement counts and always push elements back to heap to maintain availability, ensuring no two adjacent elements are equal.

3. Step 3: Evaluate other options

   Removing max frequency check or resetting counts breaks correctness or efficiency; queue does not prioritize frequency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Maintaining counts without decrement allows infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means counts stay constant [OK]

Common Mistakes:

• Removing checks without adjusting counts
• Resetting counts causing incorrect order