Largest Number (Custom Comparator Sort)

🎯

Largest Number (Custom Comparator Sort)

mediumSORT_SEARCHAmazonFacebookGoogle

Imagine you have a list of numbers and want to arrange them to form the largest possible number, like arranging puzzle pieces to get the biggest picture.

💡 This problem is about sorting numbers not by their numeric value but by how their concatenations compare. Beginners often struggle because normal numeric or lexicographic sorting doesn't work here; the order depends on combined strings.

📋

Problem Statement

Given a list of non-negative integers, arrange them such that they form the largest number and return it as a string. The result may be very large, so return a string instead of an integer.

1 ≤ n ≤ 10^50 ≤ nums[i] ≤ 10^9The result may contain leading zeros only if the entire number is zero

💡

Example

Input"[10, 2]"

Output"210"

Concatenating '2' + '10' = '210' is larger than '10' + '2' = '102', so '2' should come before '10'.

Input"[3, 30, 34, 5, 9]"

Output"9534330"

Ordering by custom comparator yields '9', '5', '34', '3', '30' to form the largest number.

• All zeros → output should be '0'
• Single element array → output is that element as string
• Numbers with same prefix → ensure correct order by concatenation
• Large array with maximum size and values → test efficiency

⚠️

Common Mistakes

Sorting numbers as integers instead of strings

Incorrect order, e.g., '30' before '3' leading to wrong largest number

✅ Convert numbers to strings and use custom comparator based on concatenation

Not handling the all zeros case

Output like '000' instead of '0'

✅ Check if the first sorted string is '0' and return '0' immediately

Using lexicographic sort without custom comparator

Incorrect ordering, e.g., '30' before '3' because '3' < '30' lex order

✅ Implement custom comparator comparing a+b and b+a

Comparing concatenations inefficiently inside sort

Slower runtime due to repeated string concatenations

✅ Use efficient string operations and avoid unnecessary conversions

Returning integer instead of string

Integer overflow or loss of leading zeros

✅ Return the result as a string

🧠

Brute Force (Generate All Permutations)

💡 This approach tries every possible order to find the largest number, which is conceptually simple but impractical for large inputs due to factorial time complexity.

Intuition

Try all permutations of the numbers, convert each permutation to a concatenated string, and pick the maximum string lexicographically.

Algorithm

1. Generate all permutations of the input array.
2. For each permutation, concatenate the numbers into a string.
3. Compare all concatenated strings lexicographically to find the maximum.
4. Return the maximum concatenated string.

💡 The challenge is realizing that brute force is straightforward but quickly becomes impossible as input size grows.

</>

Code

from itertools import permutations

def largestNumber(nums):
    max_num = ''
    for perm in permutations(nums):
        candidate = ''.join(str(num) for num in perm)
        if candidate > max_num:
            max_num = candidate
    # Handle case where all numbers are zero
    return '0' if max_num[0] == '0' else max_num

# Driver code
if __name__ == '__main__':
    print(largestNumber([3, 30, 34, 5, 9]))  # Expected: '9534330'

Line Notes

from itertools import permutationsImport permutations to generate all possible orderings

for perm in permutations(nums):Iterate over every possible ordering of nums

candidate = ''.join(str(num) for num in perm)Concatenate numbers in current permutation to form a candidate string

if candidate > max_num:Update max_num if current candidate is lexicographically larger

return '0' if max_num[0] == '0' else max_numReturn '0' if the largest number starts with zero (all zeros case)

import java.util.*;

public class LargestNumberBruteForce {
    public static String largestNumber(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        permute(nums, 0, permutations);
        String maxNum = "";
        for (List<Integer> perm : permutations) {
            StringBuilder candidate = new StringBuilder();
            for (int num : perm) {
                candidate.append(num);
            }
            if (candidate.toString().compareTo(maxNum) > 0) {
                maxNum = candidate.toString();
            }
        }
        if (maxNum.length() > 0 && maxNum.charAt(0) == '0') return "0";
        return maxNum;
    }

    private static void permute(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) perm.add(num);
            result.add(perm);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, result);
            swap(nums, start, i);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // Driver code
    public static void main(String[] args) {
        int[] nums = {3, 30, 34, 5, 9};
        System.out.println(largestNumber(nums)); // Expected: 9534330
    }
}

Line Notes

permute(nums, 0, permutations);Generate all permutations starting from index 0

if (start == nums.length)Base case: one full permutation generated

swap(nums, start, i);Swap elements to generate new permutation

if (candidate.toString().compareTo(maxNum) > 0)Update maxNum if current candidate is lexicographically larger

if (maxNum.length() > 0 && maxNum.charAt(0) == '0') return "0";Handle all zeros case by returning '0'

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

using namespace std;

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

string largestNumber(vector<int>& nums) {
    vector<vector<int>> permutations;
    permute(nums, 0, permutations);
    string maxNum = "";
    for (auto& perm : permutations) {
        string candidate = "";
        for (int num : perm) {
            candidate += to_string(num);
        }
        if (candidate > maxNum) {
            maxNum = candidate;
        }
    }
    if (!maxNum.empty() && maxNum[0] == '0') return "0";
    return maxNum;
}

int main() {
    vector<int> nums = {3, 30, 34, 5, 9};
    cout << largestNumber(nums) << endl; // Expected: 9534330
    return 0;
}

Line Notes

permute(nums, 0, permutations);Start generating permutations from index 0

if (start == nums.size())Base case: full permutation collected

swap(nums[start], nums[i]);Swap elements to explore new permutations

if (candidate > maxNum)Update maxNum if current candidate string is lexicographically larger

if (!maxNum.empty() && maxNum[0] == '0') return "0";Return '0' if all numbers are zero

function permute(nums, start, result) {
    if (start === nums.length) {
        result.push(nums.slice());
        return;
    }
    for (let i = start; i < nums.length; i++) {
        [nums[start], nums[i]] = [nums[i], nums[start]];
        permute(nums, start + 1, result);
        [nums[start], nums[i]] = [nums[i], nums[start]];
    }
}

function largestNumber(nums) {
    const permutations = [];
    permute(nums, 0, permutations);
    let maxNum = "";
    for (const perm of permutations) {
        const candidate = perm.map(String).join("");
        if (candidate > maxNum) {
            maxNum = candidate;
        }
    }
    return maxNum[0] === '0' ? '0' : maxNum;
}

// Driver code
console.log(largestNumber([3, 30, 34, 5, 9])); // Expected: '9534330'

Line Notes

permute(nums, 0, permutations);Begin generating permutations from index 0

if (start === nums.length)Base case: one complete permutation formed

[nums[start], nums[i]] = [nums[i], nums[start]];Swap elements to create new permutations

if (candidate > maxNum)Update maxNum if current candidate string is lexicographically larger

return maxNum[0] === '0' ? '0' : maxNum;Return '0' if all numbers are zero

⏱

Complexity

TimeO(n! * n * k) where n is number of elements and k is average digit length

SpaceO(n! * n) to store all permutations

Generating all permutations is factorial in n, and each permutation requires concatenation and comparison of strings of length proportional to n*k.

💡 For n=10, this means 3,628,800 permutations, which is already too large to compute in reasonable time.

Interview Verdict: TLE

This approach is only useful to demonstrate correctness and problem understanding, but it is not practical for large inputs.

🧠

Sorting with Custom Comparator

💡 This approach uses sorting with a custom comparator that compares concatenated strings to decide order, which is much more efficient and the standard solution.

Intuition

Instead of trying all permutations, sort the numbers so that for any two numbers a and b, the order is decided by which concatenation a+b or b+a is larger.

Algorithm

1. Convert all numbers to strings.
2. Sort the array with a comparator that compares concatenation of pairs in both orders.
3. Concatenate the sorted array into a single string.
4. If the result starts with '0', return '0' instead.

💡 The key insight is the custom comparator that ensures the final concatenation is the largest possible.

</>

Code

from functools import cmp_to_key

def largestNumber(nums):
    nums_str = list(map(str, nums))

    def compare(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        else:
            return 0

    nums_str.sort(key=cmp_to_key(compare))
    result = ''.join(nums_str)
    return '0' if result[0] == '0' else result

# Driver code
if __name__ == '__main__':
    print(largestNumber([3, 30, 34, 5, 9]))  # Expected: '9534330'

Line Notes

from functools import cmp_to_keyImport cmp_to_key to use custom comparator in sort

nums_str = list(map(str, nums))Convert all integers to strings for concatenation comparison

def compare(a, b):Define comparator that compares concatenations a+b and b+a

nums_str.sort(key=cmp_to_key(compare))Sort using the custom comparator to order numbers correctly

return '0' if result[0] == '0' else resultHandle case where all numbers are zero

import java.util.*;

public class LargestNumberCustomSort {
    public static String largestNumber(int[] nums) {
        String[] numsStr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsStr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(numsStr, new Comparator<String>() {
            public int compare(String a, String b) {
                String order1 = a + b;
                String order2 = b + a;
                return order2.compareTo(order1); // descending order
            }
        });
        if (numsStr[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : numsStr) sb.append(s);
        return sb.toString();
    }

    // Driver code
    public static void main(String[] args) {
        int[] nums = {3, 30, 34, 5, 9};
        System.out.println(largestNumber(nums)); // Expected: 9534330
    }
}

Line Notes

String[] numsStr = new String[nums.length];Convert integers to strings for concatenation

Arrays.sort(numsStr, new Comparator<String>() {Sort using a custom comparator

return order2.compareTo(order1);Compare concatenations in descending order to get largest number

if (numsStr[0].equals("0")) return "0";If highest number is zero, all are zero, return '0'

StringBuilder sb = new StringBuilder();Efficiently build the final concatenated string

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

using namespace std;

bool compare(const string& a, const string& b) {
    return a + b > b + a;
}

string largestNumber(vector<int>& nums) {
    vector<string> numsStr;
    for (int num : nums) numsStr.push_back(to_string(num));
    sort(numsStr.begin(), numsStr.end(), compare);
    if (numsStr[0] == "0") return "0";
    string result;
    for (const string& s : numsStr) result += s;
    return result;
}

int main() {
    vector<int> nums = {3, 30, 34, 5, 9};
    cout << largestNumber(nums) << endl; // Expected: 9534330
    return 0;
}

Line Notes

bool compare(const string& a, const string& b)Custom comparator comparing concatenations a+b and b+a

sort(numsStr.begin(), numsStr.end(), compare);Sort strings using the custom comparator

if (numsStr[0] == "0") return "0";Return '0' if all numbers are zero

for (const string& s : numsStr) result += s;Concatenate sorted strings to form the largest number

for (int num : nums) numsStr.push_back(to_string(num));Convert integers to strings for sorting

function largestNumber(nums) {
    const numsStr = nums.map(String);
    numsStr.sort((a, b) => (b + a).localeCompare(a + b));
    if (numsStr[0] === '0') return '0';
    return numsStr.join('');
}

// Driver code
console.log(largestNumber([3, 30, 34, 5, 9])); // Expected: '9534330'

Line Notes

const numsStr = nums.map(String);Convert numbers to strings for concatenation comparison

numsStr.sort((a, b) => (b + a).localeCompare(a + b));Sort with custom comparator comparing concatenations

if (numsStr[0] === '0') return '0';Handle all zeros case by returning '0'

return numsStr.join('');Concatenate sorted strings to form the largest number

⏱

Complexity

TimeO(n log n * k) where n is number of elements and k is max digit length

SpaceO(n * k) for string conversions

Sorting n strings with custom comparator that compares concatenations takes O(n log n) comparisons, each comparison takes O(k) time.

💡 For n=10^5 and k=10, this is efficient enough to run within time limits.

Interview Verdict: Accepted

This is the standard and efficient approach to solve the problem in interviews.

🧠

Optimized Sorting with Preprocessing and Early Exit

💡 This approach improves the previous by adding early exit for all zeros and minor optimizations to reduce overhead in large inputs.

Intuition

If after sorting the largest number is '0', return '0' immediately. Also, avoid unnecessary string operations by careful implementation.

Algorithm

1. Convert numbers to strings.
2. Sort with the custom comparator comparing concatenations.
3. Check if the first string is '0', return '0' if true.
4. Concatenate all strings to form the result.

💡 The early exit prevents unnecessary concatenation when all numbers are zero.

</>

Code

from functools import cmp_to_key

def largestNumber(nums):
    nums_str = list(map(str, nums))

    def compare(a, b):
        return -1 if a + b > b + a else 1 if a + b < b + a else 0

    nums_str.sort(key=cmp_to_key(compare))
    if nums_str[0] == '0':
        return '0'
    return ''.join(nums_str)

# Driver code
if __name__ == '__main__':
    print(largestNumber([0, 0, 0]))  # Expected: '0'

Line Notes

from functools import cmp_to_keyImport cmp_to_key to use custom comparator in sort

nums_str = list(map(str, nums))Convert integers to strings for comparison

def compare(a, b):Custom comparator to decide order based on concatenation

nums_str.sort(key=cmp_to_key(compare))Sort using the custom comparator

if nums_str[0] == '0':Early exit if all numbers are zero

return ''.join(nums_str)Concatenate sorted strings to form the largest number

import java.util.*;

public class LargestNumberOptimized {
    public static String largestNumber(int[] nums) {
        String[] numsStr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsStr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(numsStr, (a, b) -> (b + a).compareTo(a + b));
        if (numsStr[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : numsStr) sb.append(s);
        return sb.toString();
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 0};
        System.out.println(largestNumber(nums)); // Expected: 0
    }
}

Line Notes

Arrays.sort(numsStr, (a, b) -> (b + a).compareTo(a + b));Sort with concise lambda comparator for efficiency

if (numsStr[0].equals("0")) return "0";Early return if all numbers are zero

StringBuilder sb = new StringBuilder();Efficient string concatenation

for (String s : numsStr) sb.append(s);Build the final largest number string

for (int i = 0; i < nums.length; i++)Convert integers to strings

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

using namespace std;

bool compare(const string& a, const string& b) {
    return a + b > b + a;
}

string largestNumber(vector<int>& nums) {
    vector<string> numsStr;
    numsStr.reserve(nums.size());
    for (int num : nums) numsStr.push_back(to_string(num));
    sort(numsStr.begin(), numsStr.end(), compare);
    if (numsStr[0] == "0") return "0";
    string result;
    result.reserve(nums.size() * 10); // reserve space to avoid reallocations
    for (const string& s : numsStr) result += s;
    return result;
}

int main() {
    vector<int> nums = {0, 0, 0};
    cout << largestNumber(nums) << endl; // Expected: 0
    return 0;
}

Line Notes

numsStr.reserve(nums.size());Reserve vector capacity to improve performance

sort(numsStr.begin(), numsStr.end(), compare);Sort with custom comparator

if (numsStr[0] == "0") return "0";Early exit if all numbers are zero

result.reserve(nums.size() * 10);Reserve string capacity to avoid multiple reallocations

for (int num : nums) numsStr.push_back(to_string(num));Convert integers to strings

function largestNumber(nums) {
    const numsStr = nums.map(String);
    numsStr.sort((a, b) => (b + a).localeCompare(a + b));
    if (numsStr[0] === '0') return '0';
    return numsStr.join('');
}

// Driver code
console.log(largestNumber([0, 0, 0])); // Expected: '0'

Line Notes

const numsStr = nums.map(String);Convert numbers to strings for sorting

numsStr.sort((a, b) => (b + a).localeCompare(a + b));Sort with custom comparator based on concatenation

if (numsStr[0] === '0') return '0';Return '0' early if all numbers are zero

return numsStr.join('');Concatenate sorted strings to form the largest number

⏱

Complexity

TimeO(n log n * k) same as previous approach

SpaceO(n * k) for string storage

Early exit and minor optimizations do not change asymptotic complexity but improve runtime in practice.

💡 This approach is the practical one to implement in interviews for best performance.

Interview Verdict: Accepted

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

📊

All Approaches - One-Glance Tradeoffs

💡 Use the custom comparator sorting approach in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n * k)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Sorting with Custom Comparator	O(n log n * k)	O(n * k)	No	N/A	Code this approach
3. Optimized Sorting with Early Exit	O(n log n * k)	O(n * k)	No	N/A	Code this approach for best performance

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the custom comparator approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints, especially input size and output format.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient and introduce the custom comparator sorting approach.Step 4: Write clean code for the custom comparator solution.Step 5: Test with edge cases, especially all zeros and numbers with same prefixes.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of custom sorting, string manipulation, edge case handling, and efficiency.

Common Follow-ups

• What if numbers are very large? → Use strings to avoid integer overflow.
• Can you do this without converting all numbers to strings? → No, string concatenation is essential here.

💡 These follow-ups check your understanding of data types and the necessity of string operations in this problem.

🔍

Pattern Recognition

When to Use

1) Need to arrange numbers to form largest/smallest concatenation 2) Sorting alone is insufficient 3) Custom comparator based on concatenation order 4) Output as string due to size

Signature Phrases

'arrange numbers to form the largest number''compare concatenations of strings'

NOT This Pattern When

Sorting numbers by numeric value or lexicographic order without concatenation comparisons

Similar Problems

Form Largest Number from Array - same pattern of custom comparatorArrange Numbers to Form Minimum Number - similar but for smallest numberSort Strings by Custom Order - general custom sorting pattern

Practice

1. Consider the following Python function to find the minimum absolute difference in an array. What is the returned value when the input is [4, 2, 1, 3]?

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

print(minimum_abs_difference([4, 2, 1, 3]))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 2, 3, 4].

2. Step 2: Iterate and check adjacent differences

   Differences: 2-1=1 -> triggers early return 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Early exit on diff==1 returns 1 [OK]

Hint: Early exit returns 1 on first adjacent difference of 1 [OK]

Common Mistakes:

• Forgetting early exit
• Returning difference between non-adjacent pairs

2. Consider the following Python code implementing the optimal approach for relative sorting. Given arr1 = [3,1,2,2] and arr2 = [2,3], what is the final returned list?

easy

A. [2, 3, 1, 2]

B. [3, 2, 2, 1]

C. [2, 2, 3, 1]

D. [1, 2, 2, 3]

Solution

1. Step 1: Build frequency array for arr1

   arr1 = [3,1,2,2], max_val=3, freq = [0,1,2,1] (indices 0 to 3)

2. Step 2: Construct result using arr2 order then leftovers

   Output elements for arr2: 2 appears twice -> [2,2], 3 appears once -> [2,2,3]. Leftover is 1 once -> [2,2,3,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency counts and order match output [OK]

Hint: Trace frequency array and output order carefully [OK]

Common Mistakes:

• Appending leftover elements before arr2 order
• Miscounting frequencies or off-by-one in freq array
• Mixing order of arr2 elements in output

3. Consider the following Python code that sorts a matrix diagonally using min-heaps. What is the final matrix returned when the input is [[3,3,1,1],[2,2,1,2],[1,1,1,2]]?

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i - j], mat[i][j])
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])
    return mat

matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
print(diagonalSort(matrix))

easy

A. [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

B. [[1,1,1,1],[1,2,2,2],[1,1,3,3]]

C. [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

D. [[1,1,1,1],[1,2,2,2],[1,1,1,2]]

Solution

1. Step 1: Build min-heaps keyed by diagonal (row - col)

   For each element, push into heap keyed by i - j. For example, diagonal key 0 has elements [3,2,1], which heapify to [1,2,3].

2. Step 2: Pop from heaps to replace matrix elements

   Traverse matrix again, replacing each element with the smallest from its diagonal heap. This sorts each diagonal ascending.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys and heaps produce sorted diagonals matching [[1,1,1,1],[1,2,2,2],[1,2,3,3]] [OK]

Hint: Heap per diagonal ensures sorted order on replacement [OK]

Common Mistakes:

• Off-by-one errors in heap keys
• Mixing up heap push/pop order
• Incorrectly reconstructing matrix from heaps

4. You are given an unsorted array of integers and need to reorder it so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4] and so on, ensuring a "wiggle" pattern. Which approach guarantees an optimal solution that runs in O(n log n) time and uses O(1) extra space?

easy

A. Use a greedy approach by swapping adjacent elements whenever the wiggle property is violated.

B. Sort the array, find the median, then rearrange elements in-place using virtual indexing and three-way partitioning.

C. Use dynamic programming to find the longest wiggle subsequence and reconstruct the array accordingly.

D. Sort the array and then alternate picking elements from the start and end into a new array.

Solution

1. Step 1: Understand the wiggle property requirements

   The problem requires elements to be reordered so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4]..., which is not guaranteed by simple sorting or greedy swaps.

2. Step 2: Identify the approach that ensures correct interleaving

   Sorting and then using the median with virtual indexing and three-way partitioning ensures elements greater than median are placed at odd indices and smaller at even indices, maintaining the wiggle property in O(n log n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Virtual indexing and median partitioning guarantee wiggle order [OK]

Hint: Virtual indexing with median partitioning ensures wiggle order [OK]

Common Mistakes:

• Assuming greedy swaps fix all cases
• Using DP for rearrangement instead of subsequence
• Ignoring in-place rearrangement for space efficiency

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