Teaching Kids Programming – Find the Width of Columns of a Grid (Zip Function, Matrix Transpose)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.

For example, if grid = [[-10], [3], [12]], the width of the only column is 3 since -10 is of length 3.
Return an integer array ans of size n where ans[i] is the width of the ith column.

The length of an integer x with len digits is equal to len if x is non-negative, and len + 1 otherwise.

Example 1:
Input: grid = [[1],[22],[333]]
Output: [3]
Explanation: In the 0th column, 333 is of length 3.

Example 2:
Input: grid = [[-15,1,3],[15,7,12],[5,6,-2]]
Output: [3,1,2]
Explanation:
In the 0th column, only -15 is of length 3.
In the 1st column, all integers are of length 1.
In the 2nd column, both 12 and -2 are of length 2.

Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-10^9 <= grid[r][c] <= 10^9

Find the Width of Columns of a Grid (Zip Function, Matrix Transpose)

We can approach this problem by iterating through each column of the grid and finding the maximum length of the characters (digits) in that column. We can start by initializing an array widths of length equal to the number of columns in the grid, where each element of the array represents the maximum width of the corresponding column.

We can then iterate through each column of the grid and find the maximum length of the characters in that column. We can update the corresponding element in the widths array if the maximum length of characters in the current column is greater than the current maximum width of that column.

Here’s the pseudo code for the approach we just discussed:

1
2
3
4
5
6
7

widths = [0] * len(grid[0])
 
for col in range(len(grid[0])):
    for row in range(len(grid)):
        widths[col] = max(widths[col], len(grid[row][col]))
 
return widths

widths = [0] * len(grid[0])

for col in range(len(grid[0])):
    for row in range(len(grid)):
        widths[col] = max(widths[col], len(grid[row][col]))

return widths

Complexity Analysis

The time complexity of the above approach is O(mn), where m is the number of rows in the grid and n is the number of columns in the grid. This is because we iterate through each cell of the grid once. The space complexity of the above approach is O(n), where n is the number of columns in the grid. This is because we maintain an array of length n to store the maximum width of each column.

The following is the Python code:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:        
        return [max(len(str(s)) for s in r) for r in zip(*grid)]
 
        rows = len(grid)
        cols = len(grid[0])
        ans = [0] * cols
        for c in range(cols):
            for r in range(rows):
                ans[c] = max(ans[c], len(str(grid[r][c])))
        
        return ans

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:        
        return [max(len(str(s)) for s in r) for r in zip(*grid)]

        rows = len(grid)
        cols = len(grid[0])
        ans = [0] * cols
        for c in range(cols):
            for r in range(rows):
                ans[c] = max(ans[c], len(str(grid[r][c])))
        
        return ans

Transpose Matrix to Get Columns using zip Function

The zip function takes a few parameters and then pack each one by one. We can use zip(*A) to unpack A so that the rows are packed.

Zip(*M) is actually transposing the Matrix M. For example:

1
2

M = [[1,2],[3,4]]
list(zip(*M)) == list(zip([1,2],[3,4])) == [(1,3),(2,4))]

M = [[1,2],[3,4]]
list(zip(*M)) == list(zip([1,2],[3,4])) == [(1,3),(2,4))]

This problem can be solved with a one-liner using list comprehension and the built-in zip function in Python.

zip(*grid) transposes the input grid, so that each tuple produced by zip represents a column in the original grid. max(len(str(s)) for s in r) finds the maximum length of characters in each column. The outer list comprehension […] generates a list of the maximum lengths of characters for each column in the transposed grid.

Here’s the complete one-liner code:

1
2
3

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:        
        return [max(len(str(s)) for s in r) for r in zip(*grid)]

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:        
        return [max(len(str(s)) for s in r) for r in zip(*grid)]

This approach has a time complexity of O(mn), where m is the number of rows and n is the number of columns in the input grid. However, the code is more concise and easier to read compared to the previous approach.

It’s important to note that the str() function is used to handle non-string values in the input grid. If all the values in the input grid are already strings, you can omit the str() function call.

–EOF (The Ultimate Computing & Technology Blog) —