1618. Maximum Font to Fit a Sentence in a Screen
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 characterch
whenfontSize
is used.getHeight(fontSize)
: which provides the height of any character whenfontSize
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 givenfontSize
can be used to fit the text within the dimensions of the screen (w
andh
). - 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()
returnstrue
, 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()
returnsfalse
, 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.
Solution Approach
The provided solution in Python implements the binary search strategy to identify the maximum usable font size as follows:
-
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 heighth
of the screen. - Whether the total width of
text
at the specifiedfontSize
can fit within the widthw
of the screen by summing the widths of all characters intext
withgetWidth(fontSize, c)
.
- Whether the height of the text using the specified
-
The binary search algorithm is used by initializing two pointers:
left
andright
.left
starts at 0, andright
starts at the last index of thefonts
array. -
The main loop of the binary search continues until
left
andright
converge. In each iteration of the loop, a variablemid
is calculated to find the middle index of the current search range (left
andright
). We calculatemid
using the expression(left + right + 1) >> 1
, which is a bit manipulation technique to calculate the average ofleft
andright
and shift one bit to the right, effectively dividing by 2. -
The
check(fonts[mid])
function call tests if the font size indicated by themid
index along withtext
will fit both width and height constraints on the screen. Two scenarios are possible:- If
true
, it means the text fits the screen withfonts[mid]
, so the search continues in the right half (includingmid
) to see if a larger font size could also fit. - If
false
, the text does not fit withfonts[mid]
, and hence all larger font sizes will not fit either, so the search is confined to the left half, excludingmid
.
- If
-
Upon completion of the loop, if the
check
function returnstrue
forfonts[left]
, that meansfonts[left]
is the largest font size that the text can be displayed with on the screen. Ifcheck
fails forfonts[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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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)
returnsfontSize * 1.2
units for eachch
.getHeight(fontSize)
returnsfontSize
units.
Let's walk through the steps of the binary search strategy using this example:
-
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. -
Our binary search starts with setting
left
to 0 andright
to the last index of thefonts
array, which is 5 in this case. -
We enter a loop that will continue until
left
andright
converge. Initially,left = 0
andright = 5
. -
Calculate
mid
. Let's begin with the first iteration:mid = (0 + 5 + 1) >> 1
evaluates to3
, sofontSize = fonts[3]
is 16.
-
We call
check(16)
to see if we can use a font size of16
units. The height at this size is16
units, which does not exceed our screen height of20
units. The width would be the sum of each character's width usinggetWidth(16, ch)
, which is16 * 1.2 * len("LeetCode")
. If this sum is less than or equal to100
units,check(16)
returnstrue
. -
Depending on the result, we adjust our
left
andright
:- If
check(16)
istrue
, it means we can potentially use an even larger font size, so we setleft = mid
. - If
check(16)
isfalse
, then we need to try smaller font sizes, and we setright = mid - 1
.
- If
-
We then repeat this process until
left
andright
converge on the largest font size that can be used without exceeding the screen dimensions. -
Eventually, suppose
left
converges on index2
, withcheck(fonts[2])
returningtrue
andcheck(fonts[3])
returningfalse
. This would indicate that14
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
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:
- The binary search itself.
- 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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!