Problem Description

You need to find the maximum font size that can be used to display a given string text on a screen with width w and height h.

You're given:

• A string text to display
• Screen dimensions: width w and height h
• An array fonts containing available font sizes in ascending order
• A FontInfo interface with two methods:
  • getWidth(fontSize, ch): returns the width of character ch at the given font size
  • getHeight(fontSize): returns the height of any character at the given font size

The text will be displayed on a single line. For the text to fit on the screen with a particular font size:

1. The total width (sum of widths of all characters) must be ≤ w
2. The height must be ≤ h

The problem guarantees that:

• Font metrics are consistent (same parameters always return same values)
• Larger font sizes have larger or equal dimensions:
  • getHeight(fontSize) ≤ getHeight(fontSize+1)
  • getWidth(fontSize, ch) ≤ getWidth(fontSize+1, ch)

The solution uses binary search on the fonts array. The check function verifies if a given font size works by:

1. Checking if the height fits: fontInfo.getHeight(size) ≤ h
2. Checking if the total width fits: sum of all character widths ≤ w

Since fonts is sorted and larger fonts have larger dimensions, binary search efficiently finds the maximum valid font size. If no font size works, return -1.

Intuition

The key insight is recognizing this as an optimization problem with a monotonic property. Since the fonts array is sorted in ascending order and larger font sizes produce larger dimensions (both width and height), we have a clear pattern: if a font size is too large to fit, all larger font sizes will also be too large.

This monotonic property immediately suggests binary search. Think of it this way - we're looking for a threshold: the largest font size that still fits. Everything below this threshold works, everything above doesn't work. This creates a partition in our sorted fonts array:

• [fonts that fit] | [fonts that don't fit]

We want to find the last element in the "fonts that fit" section.

Why not just check each font size from largest to smallest? While this would work, it could require checking every font size in the worst case, giving us O(n) checks where n is the number of fonts. Binary search reduces this to O(log n) checks.

The checking logic itself is straightforward: for any given font size, we need to verify two constraints:

1. Height constraint: The font height must fit within screen height h
2. Width constraint: The sum of all character widths must fit within screen width w

If either constraint fails, the font is too large. The height check is quick (O(1)), and if it fails, we can skip the width calculation entirely. The width check requires summing widths for all characters (O(m) where m is text length), but we only do this O(log n) times due to binary search.

The binary search implementation uses the pattern of finding the rightmost valid position - we're looking for the maximum valid font size, not just any valid font size. This is why when we find a valid font at mid, we search the right half (left = mid) to potentially find an even larger valid font.

Learn more about Binary Search patterns.

Solution Approach

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

1. Helper Function - check(size):

def check(size):
    if fontInfo.getHeight(size) > h:
        return False
    return sum(fontInfo.getWidth(size, c) for c in text) <= w

This function validates whether a given font size can display the text within screen constraints:

• First, it checks the height constraint. If fontInfo.getHeight(size) > h, the font is too tall and we return False immediately
• If height is valid, it calculates the total width by summing fontInfo.getWidth(size, c) for each character c in the text
• Returns True if total width ≤ w, otherwise False

2. Binary Search Setup:

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

• left and right are indices into the fonts array, not the font sizes themselves
• We search the index range [0, len(fonts)-1]
• ans is initialized to -1 (the default return value if no font works)

3. Binary Search Loop:

while left < right:
    mid = (left + right + 1) >> 1
    if check(fonts[mid]):
        left = mid
    else:
        right = mid - 1

This implements the "find rightmost valid position" pattern:

• Calculate mid = (left + right + 1) >> 1. The +1 is crucial here - it ensures we round up when left and right are adjacent, preventing infinite loops
• The >> 1 is a bitwise right shift, equivalent to integer division by 2
• If fonts[mid] is valid (text fits), we search the right half by setting left = mid, looking for potentially larger valid fonts
• If fonts[mid] is invalid (text doesn't fit), we search the left half by setting right = mid - 1

4. Final Check and Return:

return fonts[left] if check(fonts[left]) else -1

After the loop, left equals right, pointing to our candidate answer. We perform one final validation:

• If check(fonts[left]) is True, return fonts[left] (the actual font size, not the index)
• Otherwise, return -1 indicating no valid font size exists

Time Complexity:

• Binary search performs O(log n) iterations where n = len(fonts)
• Each check call takes O(m) time where m = len(text) due to the width summation
• Total: O(m * log n)

Space Complexity:

• O(1) - only using a few variables for the binary search

The algorithm efficiently finds the maximum usable font size by leveraging the monotonic property of font sizes and binary search's logarithmic time complexity.

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
  • For font size 2: height = 4, widths: 'a'=3, 'b'=3, 'c'=3
  • For font size 3: height = 6, widths: 'a'=4, 'b'=4, 'c'=4
  • For font size 4: height = 8, widths: 'a'=5, 'b'=5, 'c'=5
  • For font size 5: height = 10, widths: 'a'=6, 'b'=6, 'c'=6

Step-by-step Binary Search:

Initial Setup:

• left = 0, right = 4 (indices into fonts array)
• ans = -1

Iteration 1:

• mid = (0 + 4 + 1) >> 1 = 2
• Check fonts[2] = 3:
  • Height check: getHeight(3) = 6 ≤ 8 ✓
  • Width check: getWidth(3,'a') + getWidth(3,'b') + getWidth(3,'c') = 4 + 4 + 4 = 12 ≤ 12 ✓
  • Font size 3 works!
• Since it works, search right half: left = 2

Iteration 2:

• Now left = 2, right = 4
• mid = (2 + 4 + 1) >> 1 = 3
• Check fonts[3] = 4:
  • Height check: getHeight(4) = 8 ≤ 8 ✓
  • Width check: 5 + 5 + 5 = 15 ≤ 12 ✗
  • Font size 4 doesn't work!
• Since it doesn't work, search left half: right = 3 - 1 = 2

Iteration 3:

• Now left = 2, right = 2
• Loop terminates (left == right)

Final Check:

• left = 2, so we check fonts[2] = 3
• We already know from iteration 1 that font size 3 works
• Return fonts[2] = 3

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

This example demonstrates how binary search efficiently narrows down the search space:

• We only checked 2 font sizes (3 and 4) out of 5 possible options
• We found that font size 3 fits perfectly (uses exactly the width limit)
• Font size 4 would exceed the width, even though the height would fit
• The algorithm correctly identified the boundary between valid and invalid font sizes

Solution Implementation

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. Incorrect Binary Search Midpoint Calculation

Pitfall: Using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 when searching for the maximum valid value.

When left and right are adjacent (e.g., left = 3, right = 4), using (left + right) // 2 gives mid = 3. If fonts[3] is valid, we set left = mid = 3, causing an infinite loop since the search space doesn't shrink.

Solution: Always use mid = (left + right + 1) // 2 when searching for the rightmost valid position. This ensures mid rounds up when left and right are adjacent, preventing infinite loops.

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 check(mid):  # mid is an index, not a font size!
    left = mid

Solution: Always use fonts[mid] when calling check() and remember that left, right, and mid are indices:

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

3. Forgetting the Final Validation

Pitfall: Directly returning fonts[left] without checking if it's actually valid.

# Wrong - assumes fonts[left] is always valid
return fonts[left]

This is problematic when no font size works (e.g., even the smallest font is too large).

Solution: Always validate the final result before returning:

# Correct
return fonts[left] if check(fonts[left]) else -1

4. Integer Overflow in Width Calculation

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

# Potential overflow for large values
total_width = sum(fontInfo.getWidth(size, c) for c in text)

Solution: Check for overflow or break early if width exceeds limit:

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

5. Wrong Binary Search Pattern

Pitfall: Using the wrong binary search pattern (finding minimum vs maximum):

# Wrong pattern for finding maximum
while left < right:
    mid = (left + right) // 2  # Wrong midpoint for maximum
    if check(fonts[mid]):
        left = mid + 1  # Wrong: skips valid values
    else:
        right = mid

Solution: Use the correct pattern for finding maximum valid value:

# Correct pattern for finding maximum
while left < right:
    mid = (left + right + 1) // 2  # Correct midpoint
    if check(fonts[mid]):
        left = mid  # Keep valid value in range
    else:
        right = mid - 1  # Exclude invalid value