Try out the problem here. This is the problem: Difficulty: Easy Problem You are given a table with n rows and m columns. Each cell is colored with white or black. Considering the shapes created by black cells, what is the maximum border of these shapes? Border of a shape means the maximum number of consecutive black cells in any row or column without any white cell in between. A shape is a set of connected cells. Two cells are connected if they share an edge. Note that no shape has a hole in it. Input format The first line contains t denoting the number of test cases. The first line of each test case contains integers n and m denoting the number of rows and columns of the matrix. Here, '#' represents a black cell and '.' represents a white cell. Each of the next n lines contains m integers. Output format Print the maximum border of the shapes. Based on these examples: Print the maximum border of the shapes. Sample Input 10 2 15 .....####...... .....#......... 7 9 ...###... ...###... ..#...... .####.... ..#...... ...#####. ......... 18 11 .#########. ########... .........#. ####....... .....#####. .....##.... ....#####.. .....####.. ..###...... ......#.... ....#####.. ...####.... ##......... #####...... ....#####.. ....##..... .#######... .#......... 1 15 .....######.... 5 11 ..#####.... .#######... ......#.... ....#####.. ...#####... 8 13 .....######.. ......##..... ########..... ...#......... ............. #######...... ..######..... ####......... 7 5 ..... ..##. ###.. ..##. ..... ..#.. .#... 14 2 .. #. .. #. .. #. .. .. #. .. .. .. #. .. 7 15 .###########... ##############. ...####........ ...##########.. .......#....... .....#########. .#######....... 12 6 #####. ###... #..... ##.... ###... ...... .##... ..##.. ...#.. ..#... #####. ####.. Sample Output 4 5 9 6 7 8 3 1 14 5 I have written this psuedocode to solve the problem: 1. I will track if I observe a number. And when I do, I would read it (let's say) "2 15" to take out the 2 and 15. 2. Then I will start a loop for the number of times I observed as the first number. 3. Then I will count the hashes in the those lines on which I will iterate in step 2. 4. I will maintain a max_border variable to keep track of the maximum number of hashes (in a border) I have seen so far. Would it work? Is it optimized?
Thanks for the detailed examples. I reanalyzed the problem using the sample inputs and outputs, and you’re absolutely right to ask for a recheck.
✅ Problem Clarified (Based on Samples)
You're not being asked to detect connected shapes. You're asked for:
The maximum number of consecutive black cells (
#) in any row or column across the entire matrix.
So, the concept of shapes and connectivity is a red herring — you're not required to group connected components.
✅ Actual Requirement (Based on Examples):
Given a grid of R x C, for each test case:
-
Find the longest sequence of
#in any row or any column. -
That sequence can be anywhere in the grid.
-
You're not restricted to connected components at all.
-
So no DFS/BFS is needed.
✅ Corrected and Optimized Approach
-
Loop through every row:
-
Count max number of consecutive
#s.
-
-
Loop through every column:
-
Count max number of consecutive
#s.
-
-
Take the maximum from both row-wise and column-wise streaks.
✅ Python Code Implementation
✅ Time and Space Complexity
-
Time Complexity:
O(R × C) -
Space Complexity:
O(1)(excluding input)
✅ Summary
| Question | Answer |
|---|---|
| Do we need DFS/BFS? | ❌ No. Shapes are irrelevant. |
| Are cells part of the same shape? | ❌ Not required to check. |
| What matters? | ✅ Longest consecutive #s in row or column |
| Your initial approach? | ✅ Partially valid — just needs column check |
Let me know if you'd like a version in another language (C++/Java).
Can you compare this (my) code with your code:
import re
data = []
t = int(input())
data.append(t)
for i in range(t):
nm = input()
data.append(nm)
# nm is of the form "2 2", "3 4", "7 3", "11 6", "3 12", "12 13" etc.
nm = nm.split()
# Now nm contains a list of string representation of two integers.
"""
# Multiline comment
nm2 = []
for i in nm:
nm2 = int(i)
"""
nm2 = [int(i) for i in nm]
#print(nm2)
for j in range(nm2[0]):
row = input() # This is just dots and hashes
data.append(row)
# Processing the input
# Producing indices of where tables are located in the input data.
# [[2, 4], [5, 12], [13, 31], ...] This is what will be produced
# i would contain [2, 4], then [5, 12], then [13, 31], so on and so forth
input_idx = []
for i in range(len(data)):
if i == 0:
# At the line 0: we are having the number representing count of input. We have to skip the first line only.
continue
if re.match(r'^[0-9]', data[i]):
# If my line starts with a digit
# ^ Starts with
# [0-9] Returns a match for any digit between 0 and 9
idx = []
idx.append(i + 1)
num_rows = data[i].split()[0]
# Range is coming in the form of: num_rows num_cols
# So we spliting on whitespace and extracting the zeroth element
idx.append(i + 1 + int(num_rows))
# i + 1: represents the start. So what would be our end: start + num_rows
input_idx.append(idx)
# ~~~ Processing input ~~~ ends here
for i in input_idx:
# [[2, 4], [5, 12], [13, 31], ...] This is what is coming as input_idx
# i would contain [2, 4], then [5, 12], then [13, 31], so on and so forth
pattern = data[i[0] : i[1]]
num_hashes = []
for j in pattern:
num_hashes.append(j.count('#'))
print(max(num_hashes))
Your code is logically valid and works for the provided problem — it produces correct output. However, let’s compare your code and my earlier version in terms of:
✅ 1. Correctness
| Aspect | Your Code | My Code |
|---|---|---|
Counts # in rows | ✅ Yes | ✅ Yes |
Counts # in columns | ❌ No (Missing) | ✅ Yes |
| Uses max streak | ❌ Only counts total per row | ✅ Counts consecutive #s only |
🔴 Your code outputs the row with the most number of
#, not the longest streak of consecutive#.
✅ My code counts the maximum consecutive#s (which matches the sample output).
✅ 2. Functionality Example
Let’s consider this input row:
-
Your code:
row.count('#') = 5(correct total count) -
Problem asks: What is the longest consecutive
#s? → Here, it’s 3 (###)
So your code would return
5as the max for this row, but the correct border is3.
✅ My code uses a loop to track streaks → correct.
✅ 3. Column Streaks
-
Your code processes only rows.
-
It completely misses column-wise streaks like this:
→ This has a vertical streak of 3 #s, but your code would return 1 for each row.
✅ My code checks columns as well.
✅ 4. Structure / Complexity Comparison
| Aspect | Your Code | My Code |
|---|---|---|
| Code Length | Longer due to custom indexing | Shorter and more direct |
| Readability | Medium (manual tracking of ranges) | Higher (uses functions, less manual parsing) |
| Preprocessing | Manual index tracking | Reads grid row-by-row |
| Regex usage | For identifying numeric lines | Not needed |
| Column support | ❌ Missing | ✅ Present |
| Streak logic | ❌ Missing (uses total counts) | ✅ Tracks streaks |
✅ 5. Time and Space Complexity
Let R = rows, C = columns, T = test cases
Your Code:
-
Time:
O(T × R × C)-
Because for each test case, you count
#s in each row (O(C))
-
-
Space: Stores all input →
O(T × R × C) -
✅ Efficient in row processing
-
❌ Misses column and streak logic
My Code:
-
Time:
O(T × R × C)-
Processes both rows and columns fully
-
-
Space:
O(R × C)per test case -
✅ Slightly more thorough but same order complexity
✅ Summary Table
| Feature | Your Code | My Code |
|---|---|---|
| Row-wise streaks | ❌ (total count) | ✅ |
| Column-wise streaks | ❌ | ✅ |
| Matches problem statement? | ❌ | ✅ |
| Regex usage | ✅ (for parsing) | ❌ |
| Code structure | Manual | Modular |
✅ Final Verdict
-
Your code is clever in parsing input with regex and tracking blocks.
-
However, for the actual problem requirement (finding max consecutive
#s in row or column), it's functionally incomplete. -
My code is more aligned with the intended logic and gives the correct results as per sample outputs.
Would you like me to help you extend your code to support streaks and columns (instead of rewriting from scratch)?
Does this algo sounds complete: 1. I will track if I observe a number. And when I do, I would read it (let's say) "2 15" to take out the 2 and 15. 2. Then I will start a loop for the number of times I observed as the first number. 3. Then I will count the hashes in the those lines on which I will iterate in step 2. 4. I will maintain a max_border variable to keep track of the maximum number of hashes appearing continuously (in a border) I have seen so far. 5. Next, we will iterate through the columns and count the hashes in the same way as we did for the rows. 6. Just one clarity about step 5: we would need to load the entire dots-and-hashes matrix into a 2D array and then iterate through it column-wise to count maximum number of continuously appearing hashes.
Yes — your revised algorithm now sounds complete and correct for solving the "maximum border of black cell shapes" problem as intended. Let's break it down to confirm each step:
✅ Your Algorithm Breakdown
Step 1:
Track when a line like
"2 15"appears, and extract2(rows) and15(columns).
-
✔️ Correct — this lets you know how many lines to read next as the matrix.
Step 2:
Loop for the number of times as the row count.
-
✔️ Correct — this helps read the full grid for the current test case.
Step 3:
Count the hashes (
#) in each of those lines.
-
⚠️ Slight correction: don't just count total
#. -
✅ You should find the maximum streak of consecutive
#s in the row — that's what the problem wants.
Example:
..###.#..# → has total 5 #, but maximum consecutive #s = 3
So you need to process each row using a loop like:
Step 4:
Maintain
max_borderto track the largest such streak.
-
✔️ This is correct — initialize to 0 and update as needed.
Step 5:
Iterate column-wise and repeat the same process as step 3.
-
✔️ This is essential and was missing in your earlier version, so great job adding it.
Step 6:
To iterate column-wise, store the matrix in a 2D array.
-
✔️ Absolutely correct — to access columns, you need all rows first.
Example loop:
✅ Final Verdict
| Criteria | Status |
|---|---|
| Handles rows correctly? | ✅ |
| Handles columns correctly? | ✅ |
| Tracks max consecutive hashes? | ✅ |
| Matrix storage for column scan? | ✅ |
| Matches sample outputs? | ✅ |
| Optimized and simple? | ✅ |
✅ Conclusion
Your updated algorithm is complete and well-reasoned. With careful implementation of row and column streak checks, it will solve the problem correctly and efficiently.
Let me know if you'd like a Python implementation based on this plan!
