Find the Width of Columns of a Grid
EasyPrompt
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 is3since-10is of length3.
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] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. We iterate through each column of the grid. For each column, we find the maximum width by examining every integer in that column. The width of an integer is determined by converting it to a string and getting the length of that string.
Algorithm
- Initialize an answer array
ansof sizen(number of columns). - Iterate through each column
jfrom0ton-1. - Inside the column loop, initialize
maxWidth = 0. - Iterate through each row
ifrom0tom-1. - Convert the number
grid[i][j]to a string. - Update
maxWidth = max(maxWidth, length of the string). - After iterating through all rows, set
ans[j] = maxWidth. - Return
ans.
Walkthrough
The algorithm proceeds as follows:
- We initialize an answer array
answith the same size as the number of columns in the grid. - We then iterate through each column index
jfrom0ton-1. - For each column
j, we need to find the maximum width. We initialize a variablemaxWidthto 0. - We then start an inner loop to iterate through each row index
ifrom0tom-1, effectively traversing all elements in the current columnj. - Inside the inner loop, for the element
grid[i][j], we convert it to a string usingString.valueOf(). - The length of this string gives us the
currentWidth. - We update
maxWidthby taking the maximum of the currentmaxWidthandcurrentWidth. - After the inner loop finishes,
maxWidthholds the maximum width for columnj, which we then store inans[j]. - Finally, after iterating through all columns, we return the
ansarray.
class Solution { public int[] findColumnWidth(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] ans = new int[n]; for (int j = 0; j < n; j++) { int maxWidth = 0; for (int i = 0; i < m; i++) { String s = String.valueOf(grid[i][j]); maxWidth = Math.max(maxWidth, s.length()); } ans[j] = maxWidth; } return ans; }}Complexity
Time
O(m * n * D), where `m` is the number of rows, `n` is the number of columns, and `D` is the maximum number of digits of any number in the grid. Since the numbers are bounded by `[-10^9, 10^9]`, `D` is at most 11. Thus, the complexity is effectively O(m * n).
Space
O(n + D). We need O(n) space for the output array. Additionally, in each step of the inner loop, a temporary string of length up to `D` is created, requiring O(D) space. This simplifies to O(n) as `D` is a small constant.
Trade-offs
Pros
Very simple and intuitive to implement.
The code is highly readable and directly follows the problem's definition of width.
Cons
Creating a new string object for every element in the grid can be inefficient. This involves memory allocation and can increase pressure on the garbage collector, potentially slowing down the execution for very large grids.
To improve efficiency, this approach avoids the overhead of string conversion. Instead of creating string objects, we calculate the length of each integer using mathematical operations. The core logic of iterating through the grid remains the same, but the method for finding the width of an individual number is replaced with a more performant, arithmetic-based helper function.
Algorithm
- Initialize an answer array
ansof sizen. - Iterate through each column
jfrom0ton-1. - Inside the column loop, initialize
maxWidth = 0. - Iterate through each row
ifrom0tom-1. - Calculate the width of
grid[i][j]mathematically:- If the number is negative, add 1 for the sign and use its absolute value.
- Count the digits of the absolute value by repeatedly dividing by 10.
- Update
maxWidth = max(maxWidth, calculated width). - After iterating through all rows, set
ans[j] = maxWidth. - Return
ans.
Walkthrough
The overall structure of iterating through the grid column by column is identical to the first approach. The optimization lies in how we calculate the width of each integer num.
We can create a helper function, getLength(int num), that computes the width arithmetically:
- Handle the base case: if
numis0, its length is1. - Handle negative numbers: if
numis negative, we account for the '-' sign by starting the length count at1. We then proceed with the absolute value ofnum. - Count the digits: For a positive number, we can count its digits by repeatedly dividing it by 10 in a loop until it becomes 0. In each iteration, we increment a length counter.
A more optimized version of the getLength function can use a series of if-else conditions to determine the number of digits based on the number's range (e.g., if (num < 100), if (num < 1000), etc.). This avoids loops and can be faster.
The main function then calls this getLength helper for each grid element to find the maxWidth for each column.
class Solution { public int[] findColumnWidth(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] ans = new int[n]; for (int j = 0; j < n; j++) { int maxWidth = 0; for (int i = 0; i < m; i++) { maxWidth = Math.max(maxWidth, getLength(grid[i][j])); } ans[j] = maxWidth; } return ans; } private int getLength(int n) { if (n == 0) { return 1; } int length = 0; if (n < 0) { length = 1; n = -n; } long temp = n; while (temp > 0) { length++; temp /= 10; } return length; }}Complexity
Time
O(m * n * D), where `D` is the maximum number of digits. The mathematical calculation of length takes time proportional to the number of digits. As `D` is a small constant (at most 11), the complexity is effectively O(m * n). This approach is generally faster than string conversion due to lower constant factors.
Space
O(n). We need O(n) space for the output array. This approach uses only a few variables for calculation, resulting in O(1) auxiliary space per element. Thus, the total space is dominated by the output array.
Trade-offs
Pros
More efficient as it avoids the overhead of string object creation and garbage collection.
Relies on fast, primitive arithmetic operations.
Cons
The code for calculating the length is slightly more complex than a simple
String.valueOf().length()call.Need to be careful with edge cases like
0and negative numbers (and potentiallyInteger.MIN_VALUE, though not an issue with the given constraints).
Solutions
Solution
class Solution {public int[] findColumnWidth(int[][] grid) { int n = grid[0].length; int[] ans = new int[n]; for (var row : grid) { for (int j = 0; j < n; ++j) { int w = String.valueOf(row[j]).length(); ans[j] = Math.max(ans[j], w); } } return ans; }}class Solution {public: vector<int> findColumnWidth(vector<vector<int>> &grid) { int n = grid[0].size(); vector<int> ans(n); for (auto &row : grid) { for (int j = 0; j < n; ++j) { int w = to_string(row[j]).size(); ans[j] = max(ans[j], w); } } return ans; }};class Solution: def findColumnWidth(self, grid: List[List[int]]) -> List[int]: ans = [0] * len(grid[0]) for row in grid: for j, x in enumerate(row): w = len(str(x)) ans[j] = max(ans[j], w) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.