2639. Find the Width of Columns of a Grid
Description
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 is3
since-10
is 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.length
n == grid[i].length
1 <= m, n <= 100
-109 <= grid[r][c] <= 109
Solutions
Solution 1: Simulation
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.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|