Sort Transformed Array (Apply Quadratic)

🎯

Sort Transformed Array (Apply Quadratic)

mediumSORT_SEARCHAmazonGoogle

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.

💡 This problem combines understanding how a quadratic function transforms numbers and how to efficiently sort the transformed array. Beginners often struggle because applying the function first and then sorting naively is inefficient, and understanding the parabola shape is key to an optimal solution.

📋

Problem Statement

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

💡

Example

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

Output[3, 9, 15, 33]

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

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

Output[-23, -5, 1, 7]

Applying f(x) = -x^2 + 3x + 5 gives [-23, -5, 1, 7]. The array is already sorted.

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

⚠️

Common Mistakes

Applying quadratic and sorting without leveraging input sorted property

Solution is inefficient (O(n log n)) and may time out on large inputs

✅ Use two-pointer approach to achieve O(n) time

Not handling the case when a=0 separately

Two-pointer logic may produce incorrect results or index errors

✅ Add explicit handling for linear function case

Filling output array in wrong direction based on sign of a

Output array is not sorted correctly

✅ Fill from end if a>0, from start if a<0

Using unstable or incorrect sort comparator in JavaScript

Output array is not sorted numerically but lex order

✅ Use numeric comparator (x, y) => x - y in sort

Not testing edge cases like all equal elements or single element arrays

Code may crash or produce wrong output

✅ Add tests for edge cases and handle them gracefully

🧠

Brute Force (Apply and Sort)

💡 This approach exists to establish a baseline solution that is straightforward but inefficient. It helps beginners understand the problem fully before optimizing.

Intuition

Apply the quadratic function to each element, then sort the resulting array. This uses built-in sorting without leveraging the input's sorted property or the quadratic shape.

Algorithm

1. Create a new array to store transformed values.
2. Iterate over each element in nums, apply f(x) = ax^2 + bx + c, and store the result.
3. Sort the transformed array using a built-in sort.
4. Return the sorted transformed array.

💡 The algorithm is easy to follow but doesn’t use the input’s sorted property or the parabola shape, so it’s not optimal.

</>

Code

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

    transformed = [quad(x) for x in nums]
    transformed.sort()
    return transformed

# Driver code
if __name__ == "__main__":
    print(sortTransformedArray([-4, -2, 2, 4], 1, 3, 5))  # Output: [3, 9, 15, 33]

Line Notes

def quad(x):Defines the quadratic function for reuse and clarity

transformed = [quad(x) for x in nums]Applies the quadratic function to each element

transformed.sort()Sorts the transformed array to meet problem requirements

return transformedReturns the sorted transformed array as output

import java.util.*;

public class Solution {
    public static int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] transformed = new int[n];
        for (int i = 0; i < n; i++) {
            transformed[i] = a * nums[i] * nums[i] + b * nums[i] + c;
        }
        Arrays.sort(transformed);
        return transformed;
    }

    public static void main(String[] args) {
        int[] result = sortTransformedArray(new int[]{-4, -2, 2, 4}, 1, 3, 5);
        System.out.println(Arrays.toString(result)); // Output: [3, 9, 15, 33]
    }
}

Line Notes

int n = nums.length;Stores length for iteration

for (int i = 0; i < n; i++) {Iterates over each element to apply quadratic

transformed[i] = a * nums[i] * nums[i] + b * nums[i] + c;Applies quadratic function to each element

Arrays.sort(transformed);Sorts the transformed array to get final output

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    int n = nums.size();
    vector<int> transformed(n);
    for (int i = 0; i < n; i++) {
        transformed[i] = a * nums[i] * nums[i] + b * nums[i] + c;
    }
    sort(transformed.begin(), transformed.end());
    return transformed;
}

int main() {
    vector<int> nums = {-4, -2, 2, 4};
    vector<int> result = sortTransformedArray(nums, 1, 3, 5);
    for (int val : result) cout << val << " "; // Output: 3 9 15 33
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Stores size for iteration

for (int i = 0; i < n; i++) {Loops through each element to apply quadratic

transformed[i] = a * nums[i] * nums[i] + b * nums[i] + c;Applies quadratic function to each element

sort(transformed.begin(), transformed.end());Sorts the transformed array for final output

function sortTransformedArray(nums, a, b, c) {
    function quad(x) {
        return a * x * x + b * x + c;
    }
    const transformed = nums.map(quad);
    transformed.sort((x, y) => x - y);
    return transformed;
}

// Driver code
console.log(sortTransformedArray([-4, -2, 2, 4], 1, 3, 5)); // Output: [3, 9, 15, 33]

Line Notes

function quad(x) {Defines quadratic function for reuse

const transformed = nums.map(quad);Applies quadratic function to each element

transformed.sort((x, y) => x - y);Sorts the transformed array numerically

return transformed;Returns the sorted transformed array

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Applying the function is O(n), sorting is O(n log n), total dominated by sorting.

💡 For n=100,000, this means about 1.5 million operations just for sorting, which can be slow.

Interview Verdict: Accepted but inefficient

This solution works but is not optimal. It’s useful to show understanding before optimizing.

🧠

Two Pointers with Parabola Shape (Optimal O(n))

💡 This approach leverages the parabola shape of the quadratic function and the sorted input to build the output in O(n) time without sorting.

Intuition

Because nums is sorted, and f(x) = ax^2 + bx + c is a parabola, the transformed values will be largest at the ends if a > 0 or smallest at the ends if a < 0. Use two pointers at the ends and fill the output array from the appropriate end.

Algorithm

1. Define a helper function to compute f(x) = ax^2 + bx + c.
2. Initialize two pointers: left at start, right at end of nums.
3. Create an output array of the same length.
4. If a >= 0, fill output from the end; else fill from the start.
5. Compare f(nums[left]) and f(nums[right]) and place the larger (or smaller) at the current output position.
6. Move pointers inward and output index accordingly until left > right.
7. Return the output array.

💡 This algorithm cleverly uses two pointers and the parabola shape to fill the output in sorted order without sorting.

</>

Code

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)
    result = [0] * n
    left, right = 0, n - 1
    index = n - 1 if a >= 0 else 0
    step = -1 if a >= 0 else 1

    while left <= right:
        left_val = quad(nums[left])
        right_val = quad(nums[right])
        if a >= 0:
            if left_val > right_val:
                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

# Driver code
if __name__ == "__main__":
    print(sortTransformedArray([-4, -2, 2, 4], 1, 3, 5))  # Output: [3, 9, 15, 33]
    print(sortTransformedArray([-4, -2, 2, 4], -1, 3, 5)) # Output: [-23, -5, 1, 7]

Line Notes

def quad(x):Defines quadratic function for reuse

left, right = 0, n - 1Initialize two pointers at array ends

index = n - 1 if a >= 0 else 0Decide output fill direction based on parabola shape

while left <= right:Loop until pointers cross to process all elements

import java.util.*;

public class Solution {
    public static int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int index = a >= 0 ? n - 1 : 0;
        int step = a >= 0 ? -1 : 1;

        while (left <= right) {
            int leftVal = a * nums[left] * nums[left] + b * nums[left] + c;
            int rightVal = a * nums[right] * nums[right] + b * nums[right] + c;
            if (a >= 0) {
                if (leftVal > rightVal) {
                    result[index] = leftVal;
                    left++;
                } else {
                    result[index] = rightVal;
                    right--;
                }
                index += step;
            } else {
                if (leftVal < rightVal) {
                    result[index] = leftVal;
                    left++;
                } else {
                    result[index] = rightVal;
                    right--;
                }
                index += step;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(sortTransformedArray(new int[]{-4, -2, 2, 4}, 1, 3, 5)));
        System.out.println(Arrays.toString(sortTransformedArray(new int[]{-4, -2, 2, 4}, -1, 3, 5)));
    }
}

Line Notes

int left = 0, right = n - 1;Initialize two pointers at array ends

int index = a >= 0 ? n - 1 : 0;Set output fill index based on parabola direction

while (left <= right) {Process elements until pointers cross

if (a >= 0) {Handle parabola opening upwards case

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    int n = nums.size();
    vector<int> result(n);
    int left = 0, right = n - 1;
    int index = (a >= 0) ? n - 1 : 0;
    int step = (a >= 0) ? -1 : 1;

    auto quad = [&](int x) { return a * x * x + b * x + c; };

    while (left <= right) {
        int leftVal = quad(nums[left]);
        int rightVal = quad(nums[right]);
        if (a >= 0) {
            if (leftVal > rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        } else {
            if (leftVal < rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {-4, -2, 2, 4};
    vector<int> res1 = sortTransformedArray(nums, 1, 3, 5);
    for (int v : res1) cout << v << " "; // 3 9 15 33
    cout << endl;
    vector<int> res2 = sortTransformedArray(nums, -1, 3, 5);
    for (int v : res2) cout << v << " "; // -23 -5 1 7
    cout << endl;
    return 0;
}

Line Notes

int left = 0, right = n - 1;Initialize pointers at array ends

int index = (a >= 0) ? n - 1 : 0;Set output index based on parabola shape

while (left <= right) {Loop until pointers cross

if (a >= 0) {Handle parabola opening upwards case

function sortTransformedArray(nums, a, b, c) {
    function quad(x) {
        return a * x * x + b * x + c;
    }
    const n = nums.length;
    const result = new Array(n);
    let left = 0, right = n - 1;
    let index = a >= 0 ? n - 1 : 0;
    const step = a >= 0 ? -1 : 1;

    while (left <= right) {
        const leftVal = quad(nums[left]);
        const rightVal = quad(nums[right]);
        if (a >= 0) {
            if (leftVal > rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        } else {
            if (leftVal < rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        }
    }
    return result;
}

// Driver code
console.log(sortTransformedArray([-4, -2, 2, 4], 1, 3, 5)); // [3, 9, 15, 33]
console.log(sortTransformedArray([-4, -2, 2, 4], -1, 3, 5)); // [-23, -5, 1, 7]

Line Notes

function quad(x) {Defines quadratic function for reuse

let index = a >= 0 ? n - 1 : 0;Determines output fill direction based on parabola

while (left <= right) {Processes elements until pointers cross

if (a >= 0) {Handles parabola opening upwards case

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is processed once with two pointers, no sorting needed.

💡 For n=100,000, this means about 100,000 operations, which is efficient and fast.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for efficiency and clarity.

🧠

Two Pointers with Separate Handling for a=0 (Linear Case)

💡 This approach explicitly handles the linear case (a=0) separately to simplify logic and avoid unnecessary complexity.

Intuition

When a=0, the function is linear, so the transformed array is either sorted or reversed sorted depending on b. We can fill the output accordingly without two-pointer comparisons.

Algorithm

1. If a == 0, check sign of b.
2. If b >= 0, apply f(x) to each element and return as is (already sorted).
3. If b < 0, apply f(x) and reverse the array before returning.
4. If a != 0, use the two-pointer approach from Approach 2.

💡 Separating linear case simplifies the main two-pointer logic and handles edge cases cleanly.

</>

Code

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)
    if a == 0:
        transformed = [quad(x) for x in nums]
        if b >= 0:
            return transformed
        else:
            return transformed[::-1]

    result = [0] * n
    left, right = 0, n - 1
    index = n - 1 if a > 0 else 0
    step = -1 if a > 0 else 1

    while left <= right:
        left_val = quad(nums[left])
        right_val = quad(nums[right])
        if a > 0:
            if left_val > right_val:
                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

# Driver code
if __name__ == "__main__":
    print(sortTransformedArray([-4, -2, 2, 4], 0, 3, 5))  # Output: [-7, -1, 1, 5]
    print(sortTransformedArray([-4, -2, 2, 4], 0, -3, 5)) # Output: [5, 1, -1, -7]

Line Notes

if a == 0:Handles linear function case separately

if b >= 0:If slope positive, transformed array is sorted ascending

return transformed[::-1]If slope negative, reverse to get ascending order

while left <= right:Two-pointer logic for quadratic case a != 0

import java.util.*;

public class Solution {
    public static int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] result = new int[n];

        if (a == 0) {
            int[] transformed = new int[n];
            for (int i = 0; i < n; i++) {
                transformed[i] = b * nums[i] + c;
            }
            if (b >= 0) {
                return transformed;
            } else {
                for (int i = 0; i < n; i++) {
                    result[i] = transformed[n - 1 - i];
                }
                return result;
            }
        }

        int left = 0, right = n - 1;
        int index = a > 0 ? n - 1 : 0;
        int step = a > 0 ? -1 : 1;

        while (left <= right) {
            int leftVal = a * nums[left] * nums[left] + b * nums[left] + c;
            int rightVal = a * nums[right] * nums[right] + b * nums[right] + c;
            if (a > 0) {
                if (leftVal > rightVal) {
                    result[index] = leftVal;
                    left++;
                } else {
                    result[index] = rightVal;
                    right--;
                }
                index += step;
            } else {
                if (leftVal < rightVal) {
                    result[index] = leftVal;
                    left++;
                } else {
                    result[index] = rightVal;
                    right--;
                }
                index += step;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(sortTransformedArray(new int[]{-4, -2, 2, 4}, 0, 3, 5)));
        System.out.println(Arrays.toString(sortTransformedArray(new int[]{-4, -2, 2, 4}, 0, -3, 5)));
    }
}

Line Notes

if (a == 0) {Separate handling for linear function

if (b >= 0) {If slope positive, transformed array is sorted ascending

for (int i = 0; i < n; i++) { result[i] = transformed[n - 1 - i]; }Reverse array if slope negative

while (left <= right) {Two-pointer logic for quadratic case

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    int n = nums.size();
    vector<int> result(n);

    if (a == 0) {
        vector<int> transformed(n);
        for (int i = 0; i < n; i++) {
            transformed[i] = b * nums[i] + c;
        }
        if (b >= 0) {
            return transformed;
        } else {
            for (int i = 0; i < n; i++) {
                result[i] = transformed[n - 1 - i];
            }
            return result;
        }
    }

    int left = 0, right = n - 1;
    int index = (a > 0) ? n - 1 : 0;
    int step = (a > 0) ? -1 : 1;

    auto quad = [&](int x) { return a * x * x + b * x + c; };

    while (left <= right) {
        int leftVal = quad(nums[left]);
        int rightVal = quad(nums[right]);
        if (a > 0) {
            if (leftVal > rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        } else {
            if (leftVal < rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {-4, -2, 2, 4};
    vector<int> res1 = sortTransformedArray(nums, 0, 3, 5);
    for (int v : res1) cout << v << " "; // -7 -1 1 5
    cout << endl;
    vector<int> res2 = sortTransformedArray(nums, 0, -3, 5);
    for (int v : res2) cout << v << " "; // 5 1 -1 -7
    cout << endl;
    return 0;
}

Line Notes

if (a == 0) {Handle linear function separately

if (b >= 0) {If slope positive, transformed array is sorted ascending

for (int i = 0; i < n; i++) { result[i] = transformed[n - 1 - i]; }Reverse array if slope negative

while (left <= right) {Two-pointer logic for quadratic case

function sortTransformedArray(nums, a, b, c) {
    function quad(x) {
        return a * x * x + b * x + c;
    }
    const n = nums.length;
    const result = new Array(n);

    if (a === 0) {
        const transformed = nums.map(x => b * x + c);
        if (b >= 0) {
            return transformed;
        } else {
            return transformed.reverse();
        }
    }

    let left = 0, right = n - 1;
    let index = a > 0 ? n - 1 : 0;
    const step = a > 0 ? -1 : 1;

    while (left <= right) {
        const leftVal = quad(nums[left]);
        const rightVal = quad(nums[right]);
        if (a > 0) {
            if (leftVal > rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        } else {
            if (leftVal < rightVal) {
                result[index] = leftVal;
                left++;
            } else {
                result[index] = rightVal;
                right--;
            }
            index += step;
        }
    }
    return result;
}

// Driver code
console.log(sortTransformedArray([-4, -2, 2, 4], 0, 3, 5)); // [-7, -1, 1, 5]
console.log(sortTransformedArray([-4, -2, 2, 4], 0, -3, 5)); // [5, 1, -1, -7]

Line Notes

if (a === 0) {Separate linear function case

if (b >= 0) {If slope positive, transformed array is sorted ascending

return transformed.reverse();Reverse if slope negative to get ascending order

while (left <= right) {Two-pointer logic for quadratic case

⏱

Complexity

TimeO(n)

SpaceO(n)

Linear case handled in O(n), quadratic case uses two pointers in O(n).

💡 This approach is efficient and handles all cases cleanly.

Interview Verdict: Accepted and clean

Separating linear case improves code clarity and correctness.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the two-pointer approach (Approach 2 or 3) in 95% of interviews for optimal performance and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	N/A	Mention only - never code
2. Two Pointers (Parabola Shape)	O(n)	O(n)	No	N/A	Code this for optimal solution
3. Two Pointers with Linear Case Handling	O(n)	O(n)	No	N/A	Code this for clean and robust solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to optimize. Read before every mock interview to build confidence.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Explain the parabola shape and how it affects sorting.Step 4: Introduce the two-pointer approach leveraging the input's sorted property.Step 5: Discuss edge cases, especially when a=0 (linear case).Step 6: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, knowledge of two-pointer technique, and handling of edge cases.

Common Follow-ups

• What if the input array is not sorted? → You must sort first or use a different approach.
• Can you do this in-place? → No, because output order differs from input order.

💡 These follow-ups test your adaptability and understanding of input assumptions.

🔍

Pattern Recognition

When to Use

1) Input array is sorted; 2) Need to apply a function to each element; 3) Result must be sorted; 4) Function is quadratic or has a parabola shape.

Signature Phrases

'apply quadratic function to each element''return the resulting array in sorted order'

NOT This Pattern When

Sorting arbitrary transformed arrays without sorted input or non-quadratic functions

Similar Problems

Squares of a Sorted Array - similar two-pointer approach for squaresMerge Sorted Array - merging sorted arrays using two pointers

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. Consider the following code snippet implementing the optimal solution to rearrange an array so no two adjacent elements are equal. What is the output of the function call make_array_beautiful_heap([1,1,2])?

easy

A. []

B. [1, 1, 2]

C. [1, 2, 1]

D. [2, 1, 1]

Solution

1. Step 1: Check max frequency condition

   Frequency counts: 1 -> 2, 2 -> 1; max_freq=2, n=3, (n+1)//2=2, so condition passes.

2. Step 2: Trace heap operations and result construction

   Heap: [(-2,1), (-1,2)] Pop (-2,1): res=[1], prev_count=-1, prev_num=1 Pop (-1,2): res=[1,2], push back (-1,1) since prev_count<0 Pop (-1,1): res=[1,2,1] Return [1,2,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected rearrangement with no adjacent duplicates [OK]

Hint: Check max frequency and simulate heap pops [OK]

Common Mistakes:

• Returning original array without rearrangement
• Confusing heap push/pop order

3. Given the following Python code for finding missing ranges, what is the final output when calling find_missing_ranges([0, 1, 3, 50, 75], 0, 99)?

easy

A. ['2', '4->49', '51->74', '76->99']

B. ['2', '4->49', '51->74', '76->98', '99']

C. ['2', '4->49', '51->74', '76->99']

D. ['2', '4->49', '51->74', '75->99']

Solution

1. Step 1: Trace pointer and bisect calls

   Start pointer=0, bisect finds 0 at idx=0, pointer updated to 1+1=2. At pointer=2, bisect finds idx=2 with curr=3, missing range 2 (single number) added. Pointer updated to 3+1=4. At pointer=4, bisect finds idx=3 with curr=50, missing range 4->49 added. Pointer updated to 50+1=51. At pointer=51, bisect finds idx=4 with curr=75, missing range 51->74 added. Pointer updated to 75+1=76. At pointer=76, bisect idx=5 (end), missing range 76->99 added. Loop ends.

2. Step 2: Confirm final missing ranges list

   Missing ranges: ['2', '4->49', '51->74', '76->99']

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All gaps between nums and bounds correctly identified [OK]

Hint: Check pointer updates and bisect indices carefully [OK]

Common Mistakes:

• Off-by-one errors in range ends
• Including last number incorrectly
• Misformatting single number ranges

4. 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

5. The following code attempts to implement the optimal relative sort array solution. Identify the line containing the subtle bug that causes incorrect output when arr1 contains elements not in arr2.

medium

A. Line 9: Missing resetting freq[val] to zero after processing

B. Line 8: Extending result with elements from arr2 order

C. Line 4: Incrementing frequency count for each num

D. Line 11: Extending result with leftover elements

Solution

1. Step 1: Understand frequency usage

   Frequency array counts occurrences; after outputting elements from arr2, freq[val] must be reset to zero to avoid duplicates.

2. Step 2: Identify missing reset

   Line 9 lacks freq[val] = 0, so leftover loop outputs duplicates of arr2 elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resetting freq[val] prevents duplicate output of arr2 elements [OK]

Hint: Check if frequency counts are zeroed after use [OK]

Common Mistakes:

• Forgetting to reset frequency after outputting arr2 elements
• Misplacing frequency increment or leftover output
• Assuming leftover loop excludes arr2 elements automatically