2639. Find the Width of Columns of a Grid

EasyArrayMatrix
Leetcode Link

Problem Description

In this problem, we are given a two-dimensional grid of integers, which represents a matrix with m rows and n columns. The task is to calculate the width of each column in this matrix. The width of a column is defined as the length of the longest number in that particular column. It's important to note that the length of a number includes all its digits and, additionally, the negative sign if the number is negative. For example, the number -123 would have a length of 4. The goal is to return an array that contains the width of each column in the grid.

Intuition

The intuition behind the solution is quite straightforward. We iterate through each cell of the matrix and convert each number to a string to calculate its length. If the number is negative, the string representation will include a minus sign, which will increase the length by one as expected.

During the iteration, we keep track of the maximum width seen so far for each column. We do this by maintaining an array ans where each index corresponds to a column of the grid, and the value at each index indicates the maximum width encountered in that column up to the current point in the iteration. Initially, all values in ans are set to 0.

For each number in the grid, we compute its length (including the negative sign if it's negative) and compare it with the current maximum width stored in ans for that particular column. If it's larger, we update the value in ans with the new maximum width. Once we have iterated through all the numbers in the grid, the ans array will contain the maximum width of each column, which we then return.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer techniques do you use to check if a string is a palindrome?

Solution Approach

The solution to this problem uses a simple algorithm that iterates through each element of the matrix and applies basic string manipulation and comparison operations. The data structure used to keep track of the maximum width of each column is a list which is as long as the number of columns in the grid. This list is initialized with zeros, since initially, we do not have any width measured.

Here is an explanation of the steps in the algorithm using the provided Python code:

  1. Initialize a list ans which has the same number of elements as there are columns in the grid (len(grid[0])). Each element of ans is set to 0.

  2. Loop through each row of the grid using a for loop with row as the iterator variable. During each iteration of this loop, you are looking at one row of numbers from the matrix.

  3. Inside the row loop, another nested for loop goes through each number x in the row, with j tracking the current column index. So, x is the current number, and j is the index of the column x is in.

  4. Convert the number x to a string using str(x) and calculate the width w, which is the length of this string. According to the rule, if x is negative, the length of the string will correctly include the negative sign.

  5. Update the maximum width for the current column. Compare the width w with the current stored value in ans[j]. If w is larger, replace ans[j] with w.

  6. Repeat steps 2 to 5 for all rows and columns in the grid. By the end of these loops, the ans list will have the maximum width for each column.

  7. Return the ans list, which now contains the calculated width of each column within the matrix.

The simplicity of this algorithm makes it quite efficient; it has a time complexity of O(m*n) where m is the number of rows and n is the number of columns in the grid, because each element of the grid is visited exactly once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's use the solution approach to walk through a small example. Suppose we are given the following matrix:

1[
2  [12, -1],
3  [134, 53],
4  [-9, 6]
5]

This matrix has 3 rows and 2 columns (m=3, n=2). Let's follow the steps to find the width of each column.

  1. Initialize an array ans with the same number of elements as columns in the grid: ans = [0, 0].

  2. Start with the first row [12, -1]. Loop through the elements:

    • Consider the first element 12, which, converted to string, has a width 2. Compare it with ans[0] which is 0. Since 2 is greater than 0, update ans[0] to 2.
    • Move to the second element -1, with a string width of 2 as well. Compare it with ans[1] which is 0. Update ans[1] to 2.

  3. Move to the second row [134, 53] and repeat:

    • The element 134 has a width 3. Compare it with ans[0] which is 2. Update ans[0] to 3.
    • Then, consider 53, which has a width of 2, but ans[1] is already 2, so it remains unchanged.

  4. Finally, for the third row [-9, 6]:

    • -9 has a width 2. ans[0] is 3, so it remains unchanged.
    • 6 has a width of 1. ans[1] is 2, so no change.

  5. After completing the iterations, ans now contains the maximum width for each column, which is [3, 2].

  6. The algorithm returns the array [3, 2]. This is the final output, indicating that the first column has a maximum width of 3 digits and the second column has a maximum width of 2 digits.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
5        # Initialize a list to store maximum width for each column
6        max_widths = [0] * len(grid[0])
7      
8        # Iterate over each row in the grid
9        for row in grid:
10            # Iterate over each element in the row
11            for col_index, value in enumerate(row):
12                # Convert the number to a string and get its length (character width)
13                number_width = len(str(value))
14                # Update the max_widths list with the maximum width for this column so far
15                max_widths[col_index] = max(max_widths[col_index], number_width)
16      
17        # Return the list of maximum column widths
18        return max_widths
19
1class Solution {
2  
3    // Method that finds the maximum width needed for each column to fit the numbers 
4    // when printed in a table format.
5    public int[] findColumnWidth(int[][] grid) {
6        // Number of columns in the grid, which is the length of the first row.
7        int numColumns = grid[0].length;
8      
9        // Array to store the maximum width required for each column.
10        int[] maxWidths = new int[numColumns];
11      
12        // Loop through each row in the grid.
13        for (int[] row : grid) {
14            // Iterate over each column in the current row.
15            for (int colIndex = 0; colIndex < numColumns; ++colIndex) {
16                // Calculate the number of digits of the current cell's value.
17                int width = String.valueOf(row[colIndex]).length();
18                // Update the maximum width for the current column, if necessary.
19                maxWidths[colIndex] = Math.max(maxWidths[colIndex], width);
20            }
21        }
22        // Return the array containing the maximum widths for each column.
23        return maxWidths;
24    }
25}
26
1#include <vector>
2#include <algorithm>
3#include <string>
4using namespace std;
5
6class Solution {
7public:
8    // Function to determine the maximum width required for each column of a 2D grid.
9    // The width is based on the number of digits in the numbers present in the column.
10    vector<int> findColumnWidth(vector<vector<int>>& grid) {
11        // Assuming grid is non-empty, get the number of columns from the first row.
12        int numColumns = grid[0].size();
13        // Initialize a vector to store the maximum width for each column.
14        vector<int> columnWidths(numColumns, 0);
15      
16        // Iterate over each row in the grid.
17        for (const auto& row : grid) {
18            // Iterate over each value in the row.
19            for (int columnIndex = 0; columnIndex < numColumns; ++columnIndex) {
20                // Get the number of digits in the current value.
21                int width = to_string(row[columnIndex]).size();
22                // Update the maximum width for the column if the current value requires more space.
23                columnWidths[columnIndex] = max(columnWidths[columnIndex], width);
24            }
25        }
26      
27        // Return the vector of maximum column widths.
28        return columnWidths;
29    }
30};
31
1// Determines the maximum width needed for each column to display the numbers.
2// It considers the number of digits (including any negative sign) of the largest number in each column.
3// @param {number[][]} grid - The 2D array of numbers representing the grid.
4// @return {number[]} An array of widths where each element represents the width required for the corresponding column.
5function findColumnWidth(grid: number[][]): number[] {
6    // Determine the number of columns based on the first row's length.
7    const columnCount = grid[0].length;
8
9    // Initialize an array to store the maximum widths with initial value 0 for each column.
10    const columnWidths: number[] = new Array(columnCount).fill(0);
11  
12    // Iterate through each row of the grid.
13    for (const row of grid) {
14        // Iterate through each column in the row.
15        for (let columnIndex = 0; columnIndex < columnCount; ++columnIndex) {
16            // Calculate the width of the current entry (number of characters it contains).
17            const entryWidth: number = String(row[columnIndex]).length;
18
19            // Update the maximum width for the current column if necessary.
20            columnWidths[columnIndex] = Math.max(columnWidths[columnIndex], entryWidth);
21        }
22    }
23
24    // Return the array of maximum column widths.
25    return columnWidths;
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

Time Complexity

The time complexity of the function findColumnWidth depends on the number of rows (R) and the number of columns (C) in the input grid. The outer loop iterates over each row, while the inner loop iterates over each column. The conversion of the integer x to a string has a time complexity proportional to the number of digits in x, which is bounded by a constant in this context since the values in grid are integers and are likely to have a bounded size in a practical scenario. Therefore, the time complexity is O(R * C).

Space Complexity

The space complexity includes the space taken by the answer list, which is initialized with a length equal to the number of columns C. No other significant space is used, therefore the space complexity is O(C).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫