algoadvance

You are given a 2D grid of strings grid, where each string is a sequence of digits. This grid represents a table of numerical values. You need to find the width of each column, where the width of a column is defined as the maximum length of the string in that column. The result should be returned as a list of integers, representing the widths of the columns from left to right.

Constraints:

1. grid is a list of lists.
2. Each inner list contains strings consisting of digits.
3. The number of rows and columns is at least 1.

Clarifying Questions

1. Q: Are there any non-digit characters in the strings?
   • A: No, each string consists solely of digits.
2. Q: Can we assume that each inner list has the same length?
   • A: Yes, each row has the same number of columns.
3. Q: What should be the output if there is only one row or column?
   • A: The solution should handle such cases, returning the appropriate list of maximum lengths per column.

Strategy

1. Initialize an empty list to store the maximum widths of each column.
2. Iterate through each column index.
3. For each column, find the maximum length of the string considering every row.
4. Store this maximum length in the result list.
5. Return the result list.

Code

Here’s the Python code to solve the problem:

def findColumnWidths(grid):
    if not grid or not grid[0]:
        return []

    num_rows = len(grid)
    num_cols = len(grid[0])
    column_widths = [0] * num_cols
    
    for col in range(num_cols):
        max_width = 0
        for row in range(num_rows):
            max_width = max(max_width, len(grid[row][col]))
        column_widths[col] = max_width
    
    return column_widths

# Example Usage
grid = [
    ["123", "4", "56"],
    ["78", "91011", "12"],
    ["3456", "7", "89"]
]
print(findColumnWidths(grid))  # Output: [4, 5, 3]

Time Complexity

• Time Complexity: The function iterates through each element of the grid exactly once, which makes the time complexity O(m * n), where m is the number of rows and n is the number of columns.
• Space Complexity: O(n) for storing the widths of the columns, where n is the number of columns.

This solution ensures that we efficiently calculate the maximum column width by checking each element in the grid only once, making it optimal for the problem’s constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?