Scale Engineer

Find the Width of Columns of a Grid

Easy
#2399Time: 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.2 companies
Data structures
ArrayMatrix
Companies
AtlassianSamsung

Prompt

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

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 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.

Walkthrough

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.
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.

Solutions

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

Video 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.

← Previous

Previous problem

Next →

Next problem