1618. Maximum Font to Fit a Sentence in a Screen

MediumArrayStringBinary SearchInteractive
Leetcode Link

Problem Description

The problem requires us to display a given string text on a screen with specific width w and height h. We are given a list of possible font sizes fonts sorted in ascending order, and we need to find out the largest font size we can use to display the entire text on the screen.

We are provided with a FontInfo interface that contains two methods:

  • getWidth(fontSize, ch): which returns the width of character ch when fontSize is used.
  • getHeight(fontSize): which provides the height of any character when fontSize is used.

We must ensure that the total width of text, calculated by summing up the width of each character in text using a given fontSize, does not exceed the screen width w. Additionally, the height of the text for the chosen fontSize, given by getHeight(fontSize), cannot be greater than the screen height h. The text is displayed in a single line.

Constraints are applied to both font width and height to ensure that they are non-decreasing with the increase in font size. If no font size can make the text fit on the screen, we are to return -1.

Intuition

This problem can naturally be approached with a binary search strategy, since the font sizes are sorted and we need to find the maximum fontSize that fits the constraints. The key steps when applying binary search in this context are:

  • Define a function check() that determines if a given fontSize can be used to fit the text within the dimensions of the screen (w and h).
  • Run a binary search over the array of font sizes. At each step, the middle font size is tested using the check() function.
  • If check() returns true, indicating the current font size fits the text within the screen, we search in the higher (larger font size) half of the remaining fonts, since our goal is to find the maximum size.
  • If check() returns false, we search in the lower half, discarding the current and larger font sizes as they will also not fit.
  • We keep narrowing our search range until we pinpoint the maximum size that fits, or we determine that no font size is suitable, in which case we return -1.

The binary search concludes either when we have successfully found the largest fontSize that allows the text to fit within the given w and h, or when we have checked all possible font sizes, and none can fit the text.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

Solution Approach

The provided solution in Python implements the binary search strategy to identify the maximum usable font size as follows:

  1. A helper function check(size) is defined that accepts a font size and determines if the text can be displayed on the screen using that particular font size. The function checks two conditions:

    • Whether the height of the text using the specified fontSize exceeds the available height h of the screen.
    • Whether the total width of text at the specified fontSize can fit within the width w of the screen by summing the widths of all characters in text with getWidth(fontSize, c).

  2. The binary search algorithm is used by initializing two pointers: left and right. left starts at 0, and right starts at the last index of the fonts array.

  3. The main loop of the binary search continues until left and right converge. In each iteration of the loop, a variable mid is calculated to find the middle index of the current search range (left and right). We calculate mid using the expression (left + right + 1) >> 1, which is a bit manipulation technique to calculate the average of left and right and shift one bit to the right, effectively dividing by 2.

  4. The check(fonts[mid]) function call tests if the font size indicated by the mid index along with text will fit both width and height constraints on the screen. Two scenarios are possible:

    • If true, it means the text fits the screen with fonts[mid], so the search continues in the right half (including mid) to see if a larger font size could also fit.
    • If false, the text does not fit with fonts[mid], and hence all larger font sizes will not fit either, so the search is confined to the left half, excluding mid.

  5. Upon completion of the loop, if the check function returns true for fonts[left], that means fonts[left] is the largest font size that the text can be displayed with on the screen. If check fails for fonts[left], then no available font sizes can display the text within the screen limits, and -1 is returned.

The solution leverages the sorted nature of the fonts array and the binary search algorithm to efficiently zone in on the maximum font size that satisfies the display constraints. The time complexity of the binary search algorithm is O(log n), which significantly reduces the number of checks needed compared to a linear search, especially for larger font arrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's consider a small example to illustrate the solution approach using a binary search strategy mentioned in the problem description.

Suppose we have the following scenario:

  • The given text is "LeetCode".
  • The screen dimension, width (w), is 100 units, and the height (h), is 20 units.
  • We have a sorted array of possible font sizes fonts = [10, 12, 14, 16, 18, 20].
  • A FontInfo interface with two hypothetical results:
    • getWidth(fontSize, ch) returns fontSize * 1.2 units for each ch.
    • getHeight(fontSize) returns fontSize units.

Let's walk through the steps of the binary search strategy using this example:

  1. We need to define a helper function check(size). This function will determine whether or not the text can be displayed using a specific font size without exceeding the screen dimensions.

  2. Our binary search starts with setting left to 0 and right to the last index of the fonts array, which is 5 in this case.

  3. We enter a loop that will continue until left and right converge. Initially, left = 0 and right = 5.

  4. Calculate mid. Let's begin with the first iteration:

    • mid = (0 + 5 + 1) >> 1 evaluates to 3, so fontSize = fonts[3] is 16.

  5. We call check(16) to see if we can use a font size of 16 units. The height at this size is 16 units, which does not exceed our screen height of 20 units. The width would be the sum of each character's width using getWidth(16, ch), which is 16 * 1.2 * len("LeetCode"). If this sum is less than or equal to 100 units, check(16) returns true.

  6. Depending on the result, we adjust our left and right:

    • If check(16) is true, it means we can potentially use an even larger font size, so we set left = mid.
    • If check(16) is false, then we need to try smaller font sizes, and we set right = mid - 1.

  7. We then repeat this process until left and right converge on the largest font size that can be used without exceeding the screen dimensions.

  8. Eventually, suppose left converges on index 2, with check(fonts[2]) returning true and check(fonts[3]) returning false. This would indicate that 14 is the largest font size we can use.

If during this iterative process no fontSize passes the check function, then no font size will fit the text on the screen and we return -1.

In our example, let's say after iterating we have found that 14 is the maximum size we can use to fit "LeetCode" within the screen dimensions, so that would be our function's return value. If every font size tested returns false in our check function, then we would return -1, indicating no suitable font size is available.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxFont(self, text: str, width: int, height: int, fonts: List[int], fontInfo: 'FontInfo') -> int:
5        # Helper function to check if a given font size is valid
6        # for the text with the given width and height constraints
7        def is_valid_size(font_size):
8            # Check if the height of the font is within the allowed height
9            if fontInfo.getHeight(font_size) > height:
10                return False
11            # Check if the total width of all characters is within the allowed width
12            return sum(fontInfo.getWidth(font_size, char) for char in text) <= width
13
14        # Initialize the pointers for binary search
15        left, right = 0, len(fonts) - 1
16        # Variable to store the maximum valid font size found so far
17        max_valid_font = -1
18      
19        # Perform a binary search to find the largest valid font size
20        while left <= right:
21            mid = (left + right) // 2
22            if is_valid_size(fonts[mid]):
23                # If the current size is valid, store it as the max found
24                max_valid_font = fonts[mid]
25                # Move the left pointer to search for a larger valid font size
26                left = mid + 1
27            else:
28                # Move the right pointer to search for a smaller valid font size
29                right = mid - 1
30      
31        return max_valid_font
32
33# Note: The FontInfo class mentioned in the comments is assumed to be provided and not shown here.
34
1class Solution {
2  
3    // This function finds the maximum font size that can be used to fit `text` in a given
4    // width `w` and height `h`, utilizing the provided `fonts` array and `fontInfo` API.
5    public int maxFont(String text, int width, int height, int[] fonts, FontInfo fontInfo) {
6        int left = 0;
7        int right = fonts.length - 1;
8
9        // Perform a binary search to find the largest valid font size.
10        while (left < right) {
11            // Calculate the middle index, leaning to the right in case of even number of elements.
12            int middle = (left + right + 1) / 2;
13            // Check if the current font size can fit the text.
14            if (canFitText(text, fonts[middle], width, height, fontInfo)) {
15                // If the text fits, move the lower bound of the search up.
16                left = middle;
17            } else {
18                // If the text doesn't fit, decrease the upper bound.
19                right = middle - 1;
20            }
21        }
22
23        // After exiting the loop, check if the font at the left index fits.
24        return canFitText(text, fonts[left], width, height, fontInfo) ? fonts[left] : -1;
25    }
26
27    // This helper function checks if `text` can fit within given `width` and `height`
28    // constraints with the specified font size, using the `fontInfo` API.
29    private boolean canFitText(String text, int fontSize, int width, int height, FontInfo fontInfo) {
30        // Check the height of the font first; if it's too tall, return false.
31        if (fontInfo.getHeight(fontSize) > height) {
32            return false;
33        }
34
35        // Sum the width of each character in the text with the current font size.
36        int totalWidth = 0;
37        for (char character : text.toCharArray()) {
38            totalWidth += fontInfo.getWidth(fontSize, character);
39            // If the total width exceeds the allowed width, return false.
40            if (totalWidth > width) {
41                return false;
42            }
43        }
44
45        // If the loop completes without returning, the text fits within the width.
46        return true;
47    }
48}
49
1/**
2 * // This is the FontInfo's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class FontInfo {
5 *   public:
6 *     // Returns the width of character ch when using fontSize.
7 *     int getWidth(int fontSize, char ch);
8 *
9 *     // Returns the height of any character when using fontSize.
10 *     int getHeight(int fontSize)
11 * };
12 */
13class Solution {
14public:
15    // Function to find the maximum font size that can be used to fit text into given dimensions (w by h).
16    // The fonts vector contains all possible font sizes in ascending order.
17    int maxFont(string text, int width, int height, vector<int>& fonts, FontInfo fontInfo) {
18        // Lambda to check if a given fontSize can be used for the text within the specified dimensions.
19        auto canUseFontSize = [&](int fontSize) {
20            // If the font height exceeds the allowed height, this font size is not viable.
21            if (fontInfo.getHeight(fontSize) > height) return false;
22          
23            // Check if the total width of characters exceeds the allowed width.
24            int totalWidth = 0;
25            for (char c : text) {
26                totalWidth += fontInfo.getWidth(fontSize, c);
27                // As soon as we exceed width, return false.
28                if (totalWidth > width) return false;
29            }
30            // The fontSize is viable since the characters fit within the width.
31            return true;
32        };
33
34        // Binary search initialization - indices for the range of fonts array.
35        int left = 0, right = fonts.size() - 1;
36
37        // Modified binary search to find the biggest viable font size.
38        while (left < right) {
39            // Choose the mid font size. Use right + 1 to prevent infinite loop in case of two elements.
40            // Shift right by 1 is equivalent to integer division by 2.
41            int mid = (left + right + 1) / 2;
42
43            // If mid font size is viable, move the left boundary to mid.
44            if (canUseFontSize(fonts[mid])) {
45                left = mid;
46            } else {
47                // Otherwise, eliminate the mid size and all greater sizes.
48                right = mid - 1;
49            }
50        }
51
52        // After narrowing down, check if the left boundary font size is viable.
53        // If it is, return its size, otherwise return -1 indicating no font size fits.
54        return canUseFontSize(fonts[left]) ? fonts[left] : -1;
55    }
56};
57
1// Define the interface for FontInfo which outlines the available methods.
2interface FontInfo {
3    getWidth(fontSize: number, ch: string): number;
4    getHeight(fontSize: number): number;
5}
6
7/**
8 * Finds the maximum font size from the list of available font sizes that can be used to fit the given text
9 * within the specified width (w) and height (h) constraints.
10 * 
11 * @param {string} text The text that needs to be fit into the specified width and height.
12 * @param {number} w The maximum allowed width.
13 * @param {number} h The maximum allowed height.
14 * @param {number[]} fonts An array of font sizes available.
15 * @param {FontInfo} fontInfo An object that provides the width and height of a character for a given font size.
16 * @return {number} The maximum font size that can be used to fit the text, or -1 if no font size fits.
17 */
18const maxFont = (text: string, w: number, h: number, fonts: number[], fontInfo: FontInfo): number => {
19    // A helper function to check whether a given font size can be used to fit the text within the constraints.
20    const canFitTextWithFontSize = (size: number): boolean => {
21        if (fontInfo.getHeight(size) > h) {
22            return false; // The height of the font exceeds the max height allowed.
23        }
24        let widthUsed: number = 0;
25        for (const char of text) {
26            widthUsed += fontInfo.getWidth(size, char); // Sum up the width of each character in the text.
27        }
28        return widthUsed <= w; // Return true only if the total width is within the constraint.
29    };
30
31    // Perform a binary search to find the maximal feasible font size from the sorted array of font sizes.
32    let left: number = 0;
33    let right: number = fonts.length - 1;
34
35    // Iterate until the search range is exhausted.
36    while (left < right) {
37        // Calculate the middle index. (right + left + 1) ensures that the mid value leans towards the right side.
38        const mid: number = left + Math.floor((right - left + 1) / 2);
39        // Use the helper function to check if the guessed font size can fit the text.
40        if (canFitTextWithFontSize(fonts[mid])) {
41            left = mid; // If it fits, it could be our new minimum feasible font size; search the right side.
42        } else {
43            right = mid - 1; // If it doesn't fit, search the left side.
44        }
45    }
46  
47    // After binary search, either we have found a feasible font size or none of them are feasible.
48    // We perform a final check for the font size at index 'left'.
49    return canFitTextWithFontSize(fonts[left]) ? fonts[left] : -1;
50};
51
52// Export the maxFont function if it needs to be used in other modules.
53export { maxFont };
54
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity

The time complexity of this binary search algorithm within a bounded list of font sizes needs to be analyzed based on two main operations:

  1. The binary search itself.
  2. The check function which is called at each step of the binary search.

Performing binary search on the sorted list of font sizes has a time complexity of O(log n), where n is the number of font sizes in the list fonts.

The check function gets called once for every step of the binary search. Inside the check function, there's a sum operation that iterates through every character c in the string text.

The time taken to get the width and height for a given fontSize is not specified, so we assume it to be O(1) for each call to fontInfo.getWidth and fontInfo.getHeight.

The total number of characters in text is denoted as m. Therefore, the complexity for checking all characters in the text at any font size is O(m).

For every binary search step, the check function is invoked once which would result in the time complexity of O(m) for each step of the binary search. Therefore, the combined time complexity for the binary search and the check function is O(m * log n).

Space Complexity

The space complexity of the algorithm is the additional space required outside of the inputs. The algorithm uses a constant amount of space for variables such as left, right, mid, and ans. Hence, the space complexity is O(1).

We are not considering the space taken up by the input text, font list, or the FontInfo object, as these are not part of the algorithm's own space requirements.

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

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫