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 of integers and need to rearrange it so that no two adjacent elements are the same. Which approach guarantees an optimal solution for this problem?

easy

A. Count frequencies, then use a max heap to greedily place the most frequent elements first, ensuring spacing.

B. Use backtracking to generate all permutations and check for valid arrangements.

C. Sort the array and then swap adjacent elements to avoid duplicates.

D. Use dynamic programming to track valid sequences avoiding adjacent duplicates.

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging elements so no two adjacent are equal, which demands careful placement of frequent elements.

2. Step 2: Identify approach that handles frequency and spacing

   Using a max heap to always pick the most frequent element available and placing it ensures no two identical elements are adjacent, which brute force or simple sorting cannot guarantee efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach handles frequency and spacing correctly [OK]

Hint: Max heap ensures spacing of frequent elements [OK]

Common Mistakes:

• Thinking sorting alone avoids adjacent duplicates
• Assuming DP solves this without frequency tracking

2. Given the following code snippet implementing the optimal wiggle sort, what is the content of the array nums after the while loop completes when the input is [1, 3, 2]?

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 1, 2]

D. [1, 2, 3]

Solution

1. Step 1: Sort and find median

   Sorted nums = [1, 2, 3], median = nums[(3-1)//2] = nums[1] = 2.

2. Step 2: Apply virtual indexing and partition

   Virtual indices for i=0,1,2 are (1+2*0)%3=1, (1+2*1)%3=0, (1+2*2)%3=2. - i=0: nums[1]=2 equals median -> i=1 - i=1: nums[0]=1 less than median -> swap with nums[virtual_index(right=2)]=nums[2]=3, right=1 - After swap: nums=[3,2,1], i=1, right=1 - i=1: nums[0]=3 greater than median -> swap with nums[virtual_index(left=0)]=nums[1]=2, left=1, i=2 - Final nums=[2,3,1]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final array satisfies wiggle property: 2 < 3 > 1 [OK]

Hint: Trace virtual indices carefully to get final array [OK]

Common Mistakes:

• Confusing virtual index mapping
• Off-by-one in median calculation
• Not updating pointers correctly

3. What is the worst-case time complexity of the optimal approach using binary search to find missing ranges in a sorted list of size n within the range [lower, upper]?

medium

A. O(n log n)

B. O((upper - lower) * log n)

C. O(n + log(upper - lower))

D. O(n log(upper - lower))

Solution

1. Step 1: Analyze binary search calls per iteration

   Each iteration advances pointer to next missing range start or after current number. Each bisect call is O(log n). Since pointer can advance by 1 in worst case, total iterations can be up to (upper - lower + 1).

2. Step 2: Combine iteration count and bisect cost

   In worst case, pointer advances one by one through the entire range, each bisect O(log n), total O((upper - lower) * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per number in range leads to O((upper - lower) log n) [OK]

Hint: Pointer can advance one by one, so multiply range size by log n [OK]

Common Mistakes:

• Assuming pointer always skips ahead by elements
• Confusing n and range size
• Ignoring worst-case pointer increments

4. What is the time and space complexity of the optimal one-pass Dutch National Flag algorithm for sorting colors in an array of length n?

medium

A. Time: O(n log n), Space: O(1) due to in-place swaps

B. Time: O(n^2), Space: O(1) due to nested pointer updates

C. Time: O(n), Space: O(n) because it uses extra arrays for counting

D. Time: O(n), Space: O(1) because it scans array once with constant pointers

Solution

1. Step 1: Identify time complexity of outer loop

   The algorithm uses a single while loop with mid pointer moving forward, scanning each element at most once, so O(n).

2. Step 2: Identify space complexity

   Only three pointers (low, mid, high) are used, no extra arrays or recursion, so O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass with constant pointers -> O(n) time and O(1) space [OK]

Hint: One pass with constant pointers means O(n) time and O(1) space [OK]

Common Mistakes:

• Confusing counting sort space with Dutch Flag space
• Assuming nested loops cause O(n^2) time
• Thinking swaps add extra space

5. Suppose the problem is modified so that numbers can be reused unlimited times to form the largest number (e.g., from [3, 30, 34], you can use '3' multiple times). Which of the following approaches correctly adapts the solution?

hard

A. Generate all permutations with repetition allowed and select the maximum concatenation.

B. Use a greedy approach repeatedly picking the number that maximizes the next concatenation until length limit is reached.

C. Use the same custom comparator sort on the original list and concatenate all elements once.

D. Sort numbers with custom comparator and then repeatedly append the first element until desired length.

Solution

1. Step 1: Understand reuse implication

   Unlimited reuse means infinite permutations; brute force is infeasible.

2. Step 2: Identify correct approach

   A greedy approach that picks the number which maximizes concatenation at each step is needed to build the largest number incrementally.

3. Step 3: Why other options fail

   Sorting once and concatenating once ignores reuse; brute force with repetition is exponential; appending first element repeatedly ignores other candidates.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Greedy incremental selection handles reuse correctly [OK]

Hint: Reuse requires greedy incremental selection, not one-time sort [OK]

Common Mistakes:

• Assuming original sort suffices for reuse scenario