Sort Transformed Array (Apply Quadratic)

▶

Steps

setup

Initialize variables and define quadratic function

Define the quadratic function f(x) = ax^2 + bx + c and initialize pointers left and right at the start and end of the input array. Prepare the result array to hold transformed values.

💡 Setting up pointers and the result array is essential to apply the two-pointer approach efficiently.

Line:

def quad(x):
    return a * x * x + b * x + c

n = len(nums)
left, right = 0, n - 1
result = [0] * n

💡 The algorithm will compare transformed values at both ends of the array to fill the result array from the correct end.

compare

Calculate transformed values at left and right pointers

Apply the quadratic function to nums[left] = -4 and nums[right] = 4, obtaining left_val = 9 and right_val = 33.

💡 Calculating transformed values at both ends helps decide which value to place next in the result array.

Line:

left_val = quad(nums[left])  # 9
right_val = quad(nums[right])  # 33

💡 Comparing these values will determine which pointer to move and where to place the next result.

insert

Compare left_val and right_val, place larger at result[index]

Since a > 0, place the larger value right_val=33 at result[3]. Move right pointer left and decrement index.

💡 For positive 'a', the parabola opens upward, so larger values are placed from the end backward.

Line:

if left_val > right_val:
    result[index] = left_val
    left += 1
else:
    result[index] = right_val
    right -= 1
index -= 1

💡 The algorithm fills the result array from the end with the largest transformed values first.

compare

Calculate transformed values at updated pointers

Apply quadratic function to nums[left] = -4 and nums[right] = 2, yielding left_val = 9 and right_val = 15.

💡 Re-evaluating transformed values at new pointers guides the next placement in the result array.

Line:

left_val = quad(nums[left])  # 9
right_val = quad(nums[right])  # 15

💡 The algorithm continuously compares values at the current pointers to decide placement.

insert

Place larger transformed value at result[index]

Right_val=15 is larger than left_val=9, so place 15 at result[2]. Move right pointer left and decrement index.

💡 Continuing to fill from the end ensures the result array is sorted correctly for a > 0.

Line:

if left_val > right_val:
    result[index] = left_val
    left += 1
else:
    result[index] = right_val
    right -= 1
index -= 1

💡 The algorithm prioritizes larger values at the end, shrinking the right pointer.

compare

Calculate transformed values at updated pointers

Apply quadratic function to nums[left] = -4 and nums[right] = -2, yielding left_val = 9 and right_val = 3.

💡 Comparing these values determines which to place next in the result array.

Line:

left_val = quad(nums[left])  # 9
right_val = quad(nums[right])  # 3

💡 The algorithm compares values at the current pointers to maintain sorted order.

insert

Place larger transformed value at result[index]

Left_val=9 is larger than right_val=3, so place 9 at result[1]. Move left pointer right and decrement index.

💡 Placing the larger value from the left pointer maintains the descending fill order for a > 0.

Line:

if left_val > right_val:
    result[index] = left_val
    left += 1
else:
    result[index] = right_val
    right -= 1
index -= 1

💡 The left pointer moves inward as its value is placed in the result array.

compare

Calculate transformed values at updated pointers

Apply quadratic function to nums[left] = -2 and nums[right] = -2 (same index), yielding left_val = 3 and right_val = 3.

💡 When pointers meet, compare the single remaining element's transformed value.

Line:

left_val = quad(nums[left])  # 3
right_val = quad(nums[right])  # 3

💡 The last element's transformed value will be placed next.

insert

Place last transformed value at result[index]

Both values are equal, place 3 at result[0]. Move left pointer right and decrement index.

💡 Placing the last value completes the result array filling.

Line:

if left_val > right_val:
    result[index] = left_val
    left += 1
else:
    result[index] = right_val
    right -= 1
index -= 1

💡 The algorithm finishes by placing the last transformed value correctly.

reconstruct

Completed filling result array

All transformed values have been placed in the result array in sorted order. The algorithm returns the final sorted transformed array.

💡 The two-pointer approach efficiently sorted the transformed values without extra sorting.

Line:

return result

💡 The final result array is sorted and ready to be returned.

from typing import List

def sortTransformedArray(nums: List[int], a: int, b: int, c: int) -> List[int]:
    def quad(x):
        return a * x * x + b * x + c

    n = len(nums)
    left, right = 0, n - 1
    result = [0] * n
    index = n - 1 if a > 0 else 0  # STEP 1
    step = -1 if a > 0 else 1

    while left <= right:  # STEP 2-9 loop
        left_val = quad(nums[left])  # STEP 2,6,8
        right_val = quad(nums[right])  # STEP 2,6,8

        if a > 0:
            if left_val > right_val:  # STEP 3,5,7,9 decisions
                result[index] = left_val
                left += 1
            else:
                result[index] = right_val
                right -= 1
            index += step
        else:
            if left_val < right_val:
                result[index] = left_val
                left += 1
            else:
                result[index] = right_val
                right -= 1
            index += step

    return result  # STEP 10

📊

Sort Transformed Array (Apply Quadratic) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the algorithm leverages the parabola shape to fill the result array in sorted order.

setup

left

-4

0

-2

1

2

2

index

4

3

Result: [0,0,0,0]

compare

left

-4

0

-2

1

2

2

index

4

3

Result: [0,0,0,0]

insert

left

-4

0

-2

1

index

2

2

4

3

Result: [0,0,0,33]

compare

left

-4

0

-2

1

index

2

2

4

3

Result: [0,0,0,33]

insert

left

-4

0

index

-2

1

2

2

4

3

Result: [0,0,15,33]

compare

left

-4

0

index

-2

1

2

2

4

3

Result: [0,0,15,33]

insert

index

-4

0

right

-2

1

2

2

4

3

Result: [0,9,15,33]

compare

index

-4

0

right

-2

1

2

2

4

3

Result: [0,9,15,33]

insert

-4

0

right

-2

1

left

2

2

4

3

Result: [3,9,15,33]

reconstruct

-4

0

-2

1

2

2

4

3

Result: [3,9,15,33]

Key Takeaways

✓ The two-pointer approach leverages the parabola shape to fill the result array from the largest or smallest values first.

This insight is hard to see from code alone because the pointer movements and fill order are implicit.

✓ Comparing transformed values at both ends allows the algorithm to avoid sorting after transformation.

Visualizing these comparisons clarifies why the algorithm is efficient and how it maintains sorted order.

✓ The direction of filling the result array depends on the sign of 'a', which controls the parabola's opening direction.

Seeing the index pointer move forward or backward based on 'a' helps understand this branching.

Practice

1. You have a list of citation counts for a researcher's papers. You want to find the maximum number h such that the researcher has at least h papers with at least h citations each. Which approach guarantees an optimal solution with time complexity better than O(n²)?

easy

A. Use a greedy algorithm that picks papers with the highest citations until the condition fails.

B. Check all possible h values from 0 to n by counting papers meeting the threshold each time.

C. Use dynamic programming to build a table of citation counts and possible h values.

D. Sort the citations in descending order and use binary search on possible h values to find the maximum valid h.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the maximum h such that at least h papers have citations >= h.

2. Step 2: Identify the optimal approach

   Sorting citations descending allows binary search on h values, checking counts efficiently, improving from O(n²) brute force to O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting + binary search is a classic pattern for this problem [OK]

Hint: Sort + binary search beats brute force [OK]

Common Mistakes:

• Assuming greedy without sorting works
• Using DP unnecessarily
• Brute force is too slow

2. You are given a sorted list of unique integers and a range defined by lower and upper. You need to find all the missing continuous ranges within this interval that are not present in the list. Which algorithmic approach best guarantees an optimal solution in terms of time complexity?

easy

A. Sorting the list and then scanning linearly to find gaps

B. Using binary search to quickly locate missing ranges between elements

C. Dynamic programming to build missing ranges from subproblems

D. Greedy approach scanning the entire range and adding missing numbers one by one

Solution

1. Step 1: Understand problem constraints

   The problem requires finding missing ranges efficiently within a sorted list and a given interval.

2. Step 2: Identify approach that leverages sorted data

   Since the list is already sorted, scanning linearly to find gaps between consecutive elements is optimal and straightforward.

3. Step 3: Evaluate binary search approach

   Using binary search to locate missing ranges is unnecessary overhead because the list is sorted and unique; a linear scan suffices.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Linear scan over sorted unique list is O(n), optimal for this problem [OK]

Hint: Linear scan over sorted unique list is optimal for missing ranges [OK]

Common Mistakes:

• Assuming binary search is needed despite sorted input
• Confusing DP with range search
• Ignoring linear scan benefits

3. The following code attempts to rearrange an array so no two adjacent elements are equal. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 15: Incorrect condition for pushing previous element back

B. Line 5: Missing check if max frequency > (n + 1) // 2

C. Line 10: Incorrect heap initialization with negative counts

D. Line 18: Incorrect increment of count variable

Solution

1. Step 1: Identify missing validation

   The code does not check if the max frequency exceeds half the array length, which makes rearrangement impossible.

2. Step 2: Understand impact of missing check

   Without this check, the function may return an invalid arrangement or fail silently on inputs like [1,1,1,2].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding the check prevents invalid outputs [OK]

Hint: Check max frequency before heap usage [OK]

Common Mistakes:

• Assuming heap initialization is buggy
• Misreading push condition for previous element

4. The following code attempts to implement the Dutch National Flag algorithm but contains a subtle bug:

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            # mid += 1  # Missing increment here
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Which line contains the bug that causes incorrect behavior or infinite loops?

medium

A. Line where mid is incremented after swapping 0 (missing here)

B. Line where nums[mid] and nums[high] are swapped and high is decremented

C. Line where mid is incremented when nums[mid] == 1

D. Line where nums[low], nums[mid] are swapped and low is incremented

Solution

1. Step 1: Identify missing pointer update

   After swapping 0 to the front, mid must increment to avoid reprocessing the same element.

2. Step 2: Consequence of missing mid increment

   Without mid increment, mid stays pointing to swapped 0, causing infinite loop or incorrect order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing mid increment after swapping 0 causes infinite loop [OK]

Hint: Always increment mid after swapping 0 to front [OK]

Common Mistakes:

• Forgetting to increment mid after swapping 0
• Incrementing mid after swapping 2 (wrong)
• Confusing roles of low and mid pointers

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