29. Excel Sheet Column Title

Description: Given an integer $columnNumber$, return its corresponding column title as it appears in an Excel sheet. (e.g., 1 -> 'A', 2 -> 'B', ..., 26 -> 'Z', 27 -> 'AA', 28 -> 'AB').

Approach: This is a base-26 conversion problem, but with a twist: 'A' is 1, not 0. This means it's a 1-indexed system. The standard base conversion algorithm for a 0-indexed system (like decimal to binary) would be to take $n \pmod{base}$ and $n = n // base$. For a 1-indexed system, the trick is to first decrement $columnNumber$ by 1. Then, repeat: 1. Get the remainder $r = (columnNumber - 1) \pmod{26}$. 2. Convert $r$ to a character ('A' + $r$). 3. Update $columnNumber = (columnNumber - 1) // 26$. Prepend the characters to build the result string.

def convertToTitle(columnNumber):
    result = []
    while columnNumber > 0:
        columnNumber -= 1 # Adjust for 1-indexed system (A=1, not A=0)
        remainder = columnNumber % 26
        result.append(chr(ord('A') + remainder))
        columnNumber //= 26
        
    return "".join(result[::-1]) # Reverse to get the correct order

30. Widest Vertical Area Between Two Points Containing No Points

Description: Given $n$ points on a 2D plane, find the widest vertical area between two points such that no points are inside the area. A vertical area is defined by two vertical lines, $x=a$ and $x=b$ with $a < b$. The width is $b-a$.

Approach: The vertical area is defined by x-coordinates. The y-coordinates do not matter. To maximize the width, we need to find the maximum difference between consecutive sorted x-coordinates. So, extract all x-coordinates, sort them, and find the maximum difference between adjacent elements.

def maxWidthOfVerticalArea(points):
    x_coordinates = sorted([p[0] for p in points])
    
    max_width = 0
    for i in range(1, len(x_coordinates)):
        max_width = max(max_width, x_coordinates[i] - x_coordinates[i-1])
        
    return max_width

31. Roman to Integer

Description: Given a Roman numeral string $s$, convert it to an integer. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is IV, five is V, etc. (subtractive rule for 4, 9, 40, 90, 400, 900).

Approach: Create a mapping for Roman characters to integer values. Iterate through the string from left to right. If a character's value is less than the next character's value (e.g., 'I' before 'V'), subtract its value. Otherwise, add its value.

def romanToInt(s):
    roman_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }
    
    total = 0
    n = len(s)
    
    for i in range(n):
        current_val = roman_map[s[i]]
        # Check for subtractive cases
        if i + 1 < n and current_val < roman_map[s[i+1]]:
            total -= current_val
        else:
            total += current_val
            
    return total

32. Shift 2D Grid

Description: Given an $m \times n$ 2D grid of integers and an integer $k$. You need to shift the grid $k$ times. In one shift operation: 1. $grid[i][j]$ moves to $grid[i][j+1]$. 2. $grid[i][n-1]$ moves to $grid[i+1][0]$. 3. $grid[m-1][n-1]$ moves to $grid[0][0]$. Return the 2D grid after shifting it $k$ times.

Approach: The shifts effectively treat the 2D grid as a 1D array. Convert the 2D grid into a 1D list, perform the conceptual shift on the 1D list by $k$ positions (using modulo operator to handle $k$ larger than the total number of elements), and then convert it back to a 2D grid.

def shiftGrid(grid, k):
    rows, cols = len(grid), len(grid[0])
    total_elements = rows * cols
    
    # Flatten the grid into a 1D list
    flat_grid = []
    for r in range(rows):
        for c in range(cols):