LeetCode 2639 - Find the Width of Columns of a Grid

The problem gives us a two dimensional integer matrix called grid with m rows and n columns. Our task is to compute the width of every column independently. The width of a column is defined as the maximum string length among all integers appearing in that column.

leetcodeeasyarraymatrix

LeetCode Problem 2639

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional integer matrix called grid with m rows and n columns. Our task is to compute the width of every column independently.

The width of a column is defined as the maximum string length among all integers appearing in that column. The length calculation follows standard integer string formatting rules:

  • Positive numbers use the number of digits directly.
  • Zero has length 1.
  • Negative numbers include the minus sign in their length.

For example:

  • 123 has length 3
  • 0 has length 1
  • -45 has length 3 because the minus sign counts as one character

The output should be an array ans of size n, where:

  • ans[i] represents the maximum width of column i

The constraints are relatively small:

  • 1 <= m, n <= 100
  • Each value is between -10^9 and 10^9

Since the matrix dimensions are at most 100 x 100, the total number of elements is at most 10,000. This means even straightforward traversal approaches are completely feasible.

A few important edge cases stand out immediately:

  • Columns containing negative values, because the minus sign increases the width.
  • Columns containing only single digit numbers.
  • Values like 0, which still have length 1.
  • Mixtures of very small and very large magnitude integers.
  • A grid with only one row or one column.

The problem guarantees the matrix is non-empty, so we never need to handle empty input.

Approaches

Brute Force Approach

The most direct solution is to process each column independently. For every column:

  1. Iterate through all rows.
  2. Convert each integer into a string.
  3. Measure the string length.
  4. Keep track of the maximum length found.

After processing all rows for a column, store the maximum width in the answer array.

This approach works because the width definition depends only on the maximum formatted length in each column. By examining every value in the column, we guarantee we find that maximum.

Even though this is called a brute force approach, it is already efficient enough for the given constraints because the matrix is small.

Optimal Approach

The optimal approach is essentially the same traversal, because every element must be inspected at least once. There is no shortcut that allows us to determine the maximum width of a column without looking at its values.

The key observation is that the problem reduces to:

  • Convert each number to its string representation.
  • Measure the representation length.
  • Track the maximum per column.

Since each cell contributes independently to its column width, a single pass through the matrix is sufficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m × n) O(n) Checks every value and computes widths directly
Optimal O(m × n) O(n) Single traversal, asymptotically optimal because every element must be inspected

Algorithm Walkthrough

  1. Determine the number of columns in the grid.

Since the output requires one width per column, we first compute n = len(grid[0]). 2. Create the result array.

Initialize an array answer of size n filled with zeros. Each position will store the maximum width found for that column so far. 3. Iterate through each column.

For every column index col, we will examine all rows in that column. 4. Iterate through each row in the current column.

Access the value grid[row][col]. 5. Convert the integer to a string.

The easiest and safest way to compute the displayed width is using str(value).

Examples:

  • str(123) becomes "123"
  • str(-45) becomes "-45"
  1. Compute the string length.

Use len(str(value)) to determine how many characters the integer occupies. 7. Update the maximum width for the column.

Compare the current width with the stored maximum and keep the larger value. 8. Store the result.

After processing all rows for a column, the maximum width is finalized in answer[col]. 9. Return the completed answer array.

Why it works

The algorithm works because every value in a column is examined exactly once, and the maximum string length encountered is stored. Since the definition of column width is precisely the maximum integer length in that column, maintaining this running maximum guarantees correctness.

Python Solution

from typing import List

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        rows = len(grid)
        cols = len(grid[0])

        answer = [0] * cols

        for col in range(cols):
            max_width = 0

            for row in range(rows):
                current_width = len(str(grid[row][col]))
                max_width = max(max_width, current_width)

            answer[col] = max_width

        return answer

The implementation begins by determining the number of rows and columns in the matrix. We then initialize the result array with zeros because no widths have been computed yet.

The outer loop iterates through each column. For every column, we maintain a variable called max_width, which tracks the largest integer length encountered so far.

Inside the inner loop, each value in the column is converted to a string using str(). This automatically handles negative signs correctly. The length of that string gives the displayed width of the integer.

The maximum width is continuously updated using max(). After all rows in a column are processed, the final width is stored in the corresponding position of the answer array.

Finally, the completed answer array is returned.

Go Solution

package main

import "strconv"

func findColumnWidth(grid [][]int) []int {
	rows := len(grid)
	cols := len(grid[0])

	answer := make([]int, cols)

	for col := 0; col < cols; col++ {
		maxWidth := 0

		for row := 0; row < rows; row++ {
			currentWidth := len(strconv.Itoa(grid[row][col]))

			if currentWidth > maxWidth {
				maxWidth = currentWidth
			}
		}

		answer[col] = maxWidth
	}

	return answer
}

The Go implementation follows the exact same logic as the Python version. The main difference is that Go does not provide implicit integer to string conversion, so we use strconv.Itoa() to convert integers into strings before measuring their lengths.

The answer is stored in a slice created with make([]int, cols). Since Go slices are initialized with zero values automatically, no extra setup is needed.

There are no overflow concerns because the constraints fit safely within Go's standard integer range.

Worked Examples

Example 1

Input:

grid = [[1], [22], [333]]

The grid has:

  • 3 rows
  • 1 column

Initial state:

Column Current Max Width
0 0

Process column 0:

Row Value String Form Length Updated Max
0 1 "1" 1 1
1 22 "22" 2 2
2 333 "333" 3 3

Final result:

[3]

Example 2

Input:

grid = [[-15,1,3],[15,7,12],[5,6,-2]]

Initial state:

Column Current Max Width
0 0
1 0
2 0

Process column 0:

Row Value String Form Length Updated Max
0 -15 "-15" 3 3
1 15 "15" 2 3
2 5 "5" 1 3

Column 0 result becomes 3.

Process column 1:

Row Value String Form Length Updated Max
0 1 "1" 1 1
1 7 "7" 1 1
2 6 "6" 1 1

Column 1 result becomes 1.

Process column 2:

Row Value String Form Length Updated Max
0 3 "3" 1 1
1 12 "12" 2 2
2 -2 "-2" 2 2

Column 2 result becomes 2.

Final answer:

[3,1,2]

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Every element in the matrix is visited exactly once
Space O(n) The output array stores one width per column

The algorithm performs a complete traversal of the matrix. Since there are m × n elements and each operation inside the loop is constant time, the total running time is O(m × n).

The extra space usage comes only from the answer array, which stores one integer per column.

Test Cases

from typing import List

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        rows = len(grid)
        cols = len(grid[0])

        answer = [0] * cols

        for col in range(cols):
            max_width = 0

            for row in range(rows):
                current_width = len(str(grid[row][col]))
                max_width = max(max_width, current_width)

            answer[col] = max_width

        return answer

solution = Solution()

assert solution.findColumnWidth([[1], [22], [333]]) == [3]  # Single column
assert solution.findColumnWidth([[-15, 1, 3], [15, 7, 12], [5, 6, -2]]) == [3, 1, 2]  # Mixed positive and negative
assert solution.findColumnWidth([[0]]) == [1]  # Single zero
assert solution.findColumnWidth([[-1]]) == [2]  # Negative single digit
assert solution.findColumnWidth([[1000, 2], [30, 40000]]) == [4, 5]  # Different widths per column
assert solution.findColumnWidth([[9, 99, 999]]) == [1, 2, 3]  # Single row
assert solution.findColumnWidth([[-999999999]]) == [10]  # Large negative number
assert solution.findColumnWidth([[1, -20], [300, 4]]) == [3, 3]  # Width updates later in traversal
assert solution.findColumnWidth([[10], [100], [1000], [10000]]) == [5]  # Increasing widths
assert solution.findColumnWidth([[0, 0], [0, 0]]) == [1, 1]  # All zeros
Test Why
[[1], [22], [333]] Validates increasing widths in a single column
[[-15,1,3],[15,7,12],[5,6,-2]] Validates negative numbers and multiple columns
[[0]] Ensures zero is treated as length 1
[[-1]] Ensures minus sign is counted
[[1000,2],[30,40000]] Tests varying widths across columns
[[9,99,999]] Validates single row handling
[[-999999999]] Tests largest negative width
[[1,-20],[300,4]] Ensures later values can update maximum width
[[10],[100],[1000],[10000]] Tests progressive width increases
[[0,0],[0,0]] Validates repeated zero handling

Edge Cases

One important edge case is negative numbers. A naive implementation might count only the digits and forget the minus sign. For example, -15 should have width 3, not 2. Using str(value) automatically includes the minus sign, so the implementation handles this correctly.

Another edge case is the value 0. Some digit counting approaches based on repeated division can incorrectly produce length 0 for zero. String conversion avoids this entirely because str(0) correctly becomes "0" with length 1.

A third important edge case is a grid with only one row or one column. Some matrix algorithms assume multiple rows and columns exist, which can cause indexing mistakes. This implementation uses generic loops over rows and cols, so it works correctly regardless of whether the grid dimensions are 1 x n, m x 1, or larger.

A final edge case involves very large magnitude integers such as -999999999. The algorithm still works correctly because string conversion naturally handles arbitrarily large valid integer values within the problem constraints.