# Find the Width of Columns of a Grid
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-width-of-columns-of-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/find-the-width-of-columns-of-a-grid
**Data structures:** Array, Matrix
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
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 `
* `-109 <= grid[r][c] <= 109`

# Approaches
## Brute Force using String Conversion
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.
**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.
**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.
### Explanation
The algorithm proceeds as follows:
1.  We initialize an answer array `ans` with the same size as the number of columns in the grid.
2.  We then iterate through each column index `j` from `0` to `n-1`.
3.  For each column `j`, we need to find the maximum width. We initialize a variable `maxWidth` to 0.
4.  We then start an inner loop to iterate through each row index `i` from `0` to `m-1`, effectively traversing all elements in the current column `j`.
5.  Inside the inner loop, for the element `grid[i][j]`, we convert it to a string using `String.valueOf()`.
6.  The length of this string gives us the `currentWidth`.
7.  We update `maxWidth` by taking the maximum of the current `maxWidth` and `currentWidth`.
8.  After the inner loop finishes, `maxWidth` holds the maximum width for column `j`, which we then store in `ans[j]`.
9.  Finally, after iterating through all columns, we return the `ans` array.

```java
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;
    }
}
```
### Algorithm
- Initialize an answer array `ans` of size `n` (number of columns).
- Iterate through each column `j` from `0` to `n-1`.
- Inside the column loop, initialize `maxWidth = 0`.
- Iterate through each row `i` from `0` to `m-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`.

## Optimized Approach using Mathematical Calculation
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.
**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.
**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 `0` and negative numbers (and potentially `Integer.MIN_VALUE`, though not an issue with the given constraints).
### Explanation
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:
1.  Handle the base case: if `num` is `0`, its length is `1`.
2.  Handle negative numbers: if `num` is negative, we account for the '-' sign by starting the length count at `1`. We then proceed with the absolute value of `num`.
3.  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.

```java
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;
    }
}
```
### Algorithm
- Initialize an answer array `ans` of size `n`.
- Iterate through each column `j` from `0` to `n-1`.
- Inside the column loop, initialize `maxWidth = 0`.
- Iterate through each row `i` from `0` to `m-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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```