Leetcode 1618 Maximum Font to Fit a Sentence in a Screen

Problem statement

https://leetcode.com/problems/maximum-font-to-fit-a-sentence-in-a-screen/

Solution

The idea is just to use simple binary search. Here I added two border cases to fonts: zero and infinite, actually fontInfo will neve be taken with this values, because they are on the border.

Complexity

Time complexity is O(N*log M), where N is size of text and M is size of fonts. Space comlexity is O(M), because I used dummy variables. Space can be done in O(1) as well, if we rewrite binary steps a bit.

Code

class Solution:
    def maxFont(self, text, w, h, fonts, fontInfo):
        fonts = [0] + fonts + [float("inf")]
        beg, end = 0, len(fonts) - 1
        
        while beg + 1 < end:
            mid = (beg + end)//2
            total_w = sum(fontInfo.getWidth(fonts[mid], c) for c in text)
            total_h = fontInfo.getHeight(fonts[mid])
            if total_w <= w and total_h <= h:
                beg = mid
            else:
                end = mid
                
        return fonts[beg] if beg > 0 else -1