You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.
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.lengthn == grid[i].length1 <= m, n <= 100 -109 <= grid[r][c] <= 109Problem Overview: You are given an m x n integer grid. For each column, compute the display width required to print all values in that column. The width equals the maximum number of characters needed to represent any number in that column (including the minus sign for negative numbers).
Approach 1: Simple Iteration Over Columns (Time: O(m*n), Space: O(n))
The direct approach scans the grid column by column. For each column j, iterate through every row i and convert grid[i][j] into a string using str() or its equivalent. Track the maximum string length seen in that column. Store the result in an output array where ans[j] represents the width of column j. The key observation is that the width of a column depends only on the longest formatted number in that column.
This approach relies on straightforward iteration over the matrix. Each element is visited exactly once, and the cost of computing the string length is constant for typical integer ranges. The solution is simple, readable, and works well for interview settings where clarity matters.
Approach 2: Optimized Column-Wise Pass (Time: O(m*n), Space: O(n))
The optimized variation avoids repeated string allocations. Instead of converting numbers to strings, compute the number of digits mathematically. For each value, take the absolute value and count digits using division or log10. If the number is negative, add one extra character for the minus sign. Compare this computed length with the current maximum width for the column.
This method still performs a single pass across the grid but reduces temporary string creation. When working with very large grids or performance-sensitive environments, avoiding string conversion can slightly reduce overhead. The logic remains column-oriented and uses only a result array to track widths.
The algorithm naturally fits problems involving arrays and matrix traversal. You iterate through columns, compute a property of each element, and keep a running maximum.
Recommended for interviews: The simple iteration approach is usually expected. It clearly shows that you understand column traversal and how formatted length determines width. Mentioning the mathematical digit-count optimization demonstrates deeper awareness of performance tradeoffs, but both approaches have the same asymptotic complexity of O(m*n) time and O(n) extra space.
To solve this problem, iterate over each column and calculate the maximum length of integers in that column. We can achieve this by checking each column element one at a time, converting it to its string representation to determine its length. Iterate through all columns to find the widths.
This code iterates over each column in the grid, calculating the maximum character length of numbers in each column using the snprintf to find the length of the integer as a string. This is done for each row in the column to find the maximum width of that column.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is processed once.
Space Complexity: O(n) for storing the widths of each column.
This approach limits excess computation by leveraging stored intermediate lengths for each integer. It maintains a running list of maximum lengths, updating it with each new integer's length if it exceeds the current maximum for that column.
This strategy in C iterates over the grid, with each column's width evaluated in a memory-efficient manner by optimizing concurrent access to grid elements and by improving cache performance on typical hardware architectures.
Time Complexity: O(m * n), every element is still visited once, but with optimized heading access patterns.
Space Complexity: O(n), being the storage of column width information.
We denote the number of columns in the matrix as n, and create an array ans of length n, where ans[i] represents the width of the i-th column. Initially, ans[i] = 0.
We traverse each row in the matrix. For each element in each row, we calculate its string length w, and update the value of ans[j] to be max(ans[j], w).
After traversing all rows, each element in the array ans is the width of the corresponding column.
The time complexity is O(m times n), and the space complexity is O(log M). Where m and n are the number of rows and columns in the matrix respectively, and M is the absolute value of the maximum element in the matrix.
| Approach | Complexity |
|---|---|
| Simple Iteration Over Columns | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is processed once. |
| Optimized Column-Wise Pass | Time Complexity: O(m * n), every element is still visited once, but with optimized heading access patterns. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iteration Over Columns | O(m*n) | O(n) | Best general solution. Clean and easy to implement using string length. |
| Optimized Column-Wise Pass (Digit Counting) | O(m*n) | O(n) | When avoiding string conversions or optimizing numeric processing. |
6333. Find the Width of Columns of a Grid | Leetcode Biweekly Contest 102 | Solution | JAVA. • Optimization • 405 views views
Watch 8 more video solutions →Practice Find the Width of Columns of a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor