Solution Approach

The solution implements the standard binary search template to find the maximum valid font size. Let's walk through the implementation step by step:

1. Helper Function - tooLarge(fontSize):

def too_large(font_size: int) -> bool:
    if fontInfo.getHeight(font_size) > h:
        return True
    total_width = sum(fontInfo.getWidth(font_size, char) for char in text)
    return total_width > w

This function returns true if the font size is too large to fit, creating a monotonic pattern:

• For small fonts: false, false, false, ... (they fit)
• For large fonts: ..., true, true, true (they don't fit)

2. Binary Search Setup:

left, right = 0, len(fonts) - 1
first_true_index = -1

• left and right are indices into the fonts array
• first_true_index = -1 tracks the first font that is too large (initialized to -1 meaning "not found yet")

3. Binary Search Loop (Standard Template):

while left <= right:
    mid = (left + right) // 2
    if too_large(fonts[mid]):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

This implements the standard "find first true" template:

• Use while left <= right (not left < right)
• When tooLarge(fonts[mid]) is true, we found a font that doesn't fit - record it in first_true_index and search left for an earlier one (right = mid - 1)
• When false, the font fits - search right for the boundary (left = mid + 1)

4. Derive the Answer:

if first_true_index == -1:
    return fonts[-1]  # All fonts fit
elif first_true_index == 0:
    return -1  # Even smallest font doesn't fit
else:
    return fonts[first_true_index - 1]  # Font just before first too-large

The answer is the font just before first_true_index:

• If first_true_index == -1: All fonts fit, return the largest
• If first_true_index == 0: Even the smallest font is too large, return -1
• Otherwise: Return fonts[first_true_index - 1]

Time Complexity: O(m * log n) where m = len(text) and n = len(fonts)

Space Complexity: O(1) - only using a few variables

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• text = "abc"
• w = 12 (screen width)
• h = 8 (screen height)
• fonts = [1, 2, 3, 4, 5]
• FontInfo returns:
  • For font size 1: height = 2, widths: 'a'=2, 'b'=2, 'c'=2 → total = 6
  • For font size 2: height = 4, widths: 'a'=3, 'b'=3, 'c'=3 → total = 9
  • For font size 3: height = 6, widths: 'a'=4, 'b'=4, 'c'=4 → total = 12
  • For font size 4: height = 8, widths: 'a'=5, 'b'=5, 'c'=5 → total = 15
  • For font size 5: height = 10, widths: 'a'=6, 'b'=6, 'c'=6 → total = 18

tooLarge pattern: [false, false, false, true, true] (fonts 1,2,3 fit; fonts 4,5 don't)

Step-by-step Binary Search:

Initial Setup:

• left = 0, right = 4
• first_true_index = -1

Iteration 1:

• mid = (0 + 4) // 2 = 2
• Check tooLarge(fonts[2]) = tooLarge(3):
  • Height: 6 ≤ 8 ✓
  • Width: 12 ≤ 12 ✓
  • Returns false (font 3 fits)
• Since tooLarge is false, search right: left = 2 + 1 = 3

Iteration 2:

• left = 3, right = 4
• mid = (3 + 4) // 2 = 3
• Check tooLarge(fonts[3]) = tooLarge(4):
  • Height: 8 ≤ 8 ✓
  • Width: 15 > 12 ✗
  • Returns true (font 4 is too large)
• Since tooLarge is true: first_true_index = 3, right = 3 - 1 = 2

Iteration 3:

• left = 3, right = 2
• left > right, loop terminates

Derive Answer:

• first_true_index = 3 (first font that doesn't fit is at index 3)
• Answer = fonts[first_true_index - 1] = fonts[2] = 3

Result: The maximum font size that can display "abc" is 3.

This example demonstrates the standard binary search template:

• We track first_true_index to find the boundary
• The answer is fonts[first_true_index - 1] - the last font that fits
• We checked only 2 font sizes (3 and 4) out of 5 possible options

Time and Space Complexity

Time Complexity: O(n * log(m)) where n is the length of the text string and m is the number of fonts in the fonts array.

• The binary search performs O(log(m)) iterations to find the maximum valid font size
• In each iteration of the binary search, the check function is called once
• The check function iterates through all characters in the text string, making n API calls to getWidth() and one call to getHeight()
• Each API call is assumed to be O(1)
• Therefore, each check function call takes O(n) time
• Total time complexity: O(n * log(m))

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space for variables (left, right, ans, mid)
• The check function uses a generator expression with sum() which processes elements one at a time without storing them
• No additional data structures are created that scale with input size
• The space used does not depend on the length of the text or the number of fonts

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

Pitfall: Using while left < right with left = mid instead of the standard template.

# Wrong variant - prone to infinite loops
while left < right:
    mid = (left + right + 1) // 2
    if canFit(fonts[mid]):
        left = mid
    else:
        right = mid - 1

Solution: Use the standard template with first_true_index:

# Correct - standard template
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if tooLarge(fonts[mid]):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

2. Confusing Array Indices with Font Sizes

Pitfall: Mixing up the index in the fonts array with the actual font size value.

# Wrong - treating index as font size
if tooLarge(mid):  # mid is an index, not a font size!
    first_true_index = mid

Solution: Always use fonts[mid] when checking:

# Correct
if tooLarge(fonts[mid]):  # fonts[mid] is the actual font size
    first_true_index = mid

3. Forgetting Edge Cases When Deriving the Answer

Pitfall: Not handling all three cases for first_true_index:

# Wrong - missing edge cases
return fonts[first_true_index - 1]

Solution: Handle all three cases:

# Correct
if first_true_index == -1:
    return fonts[-1]  # All fonts fit
elif first_true_index == 0:
    return -1  # No font fits
else:
    return fonts[first_true_index - 1]

4. Integer Overflow in Width Calculation

Pitfall: For very long texts or large font sizes, the sum of character widths might overflow.

Solution: Break early if width exceeds limit:

def too_large(font_size):
    if fontInfo.getHeight(font_size) > h:
        return True
    total_width = 0
    for c in text:
        total_width += fontInfo.getWidth(font_size, c)
        if total_width > w:  # Early termination
            return True
    return False

5. Inverting the Feasible Function Logic

Pitfall: Defining feasible as "font fits" but forgetting to adjust the answer derivation.

The standard template finds the first true. If you define feasible(x) = font fits, then first_true_index is the first font that fits, and you'd need to find the last true instead.

Solution: Define tooLarge(x) = font doesn't fit. This creates the pattern [false, ..., false, true, ..., true], and first_true_index gives you the first font that doesn't fit. The answer is fonts[first_true_index - 1].