algoadvance

Leetcode 2639. Find the Width of Columns of a Grid

Problem Statement

You are given a 0-indexed m x n integer matrix grid. The width of a column is defined as the maximum length of its integer representations. The task is to return an integer array answer of size n where answer[i] is the width of the i-th column.

For example, if you have a grid:

grid = [
  [1, 22, 333],
  [444, 55, 6],
  [77, 888, 9999]
]

The width of each column would be [3, 3, 4] because:

Clarifying Questions

  1. Input validation: Can the grid contain negative integers?
  2. Complexity constraints: Is there any constraint on the maximum size of the grid m and n?

Strategy

The strategy is to:

  1. Iterate through each column of the grid.
  2. Compute the string length of each integer in the column.
  3. Find the maximum length for each column.
  4. Store these maximum lengths in an array and return it.

Code

Here’s a concise implementation in Java:

import java.util.*;

public class Solution {
    public int[] findColumnWidth(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return new int[0];
        }
        int m = grid.length;
        int n = grid[0].length;
        int[] columnWidths = new int[n];

        for (int j = 0; j < n; j++) {
            int maxWidth = 0;
            for (int i = 0; i < m; i++) {
                int length = String.valueOf(grid[i][j]).length();
                if (length > maxWidth) {
                    maxWidth = length;
                }
            }
            columnWidths[j] = maxWidth;
        }

        return columnWidths;
    }

    // For testing purpose
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {
            {1, 22, 333},
            {444, 55, 6},
            {77, 888, 9999}
        };
        
        System.out.println(Arrays.toString(sol.findColumnWidth(grid)));
    }
}

Time Complexity

The time complexity of the solution is O(m * n), where m is the number of rows and n is the number of columns. This is because we iterate over each element in the grid once to determine the width of each column.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI