Discussion about Maximum Border (Problem from HackerEarth)

To See All Articles About Technology: Index of Lessons in Technology

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

1. Loop through every row:

   • Count max number of consecutive #s.

2. Loop through every column:

   • Count max number of consecutive #s.

3. Take the maximum from both row-wise and column-wise streaks.

---

✅ Python Code Implementation

python
def max_border(grid, R, C):
    max_streak = 0

    # Check row-wise
    for row in grid:
        count = 0
        for cell in row:
            if cell == '#':
                count += 1
                max_streak = max(max_streak, count)
            else:
                count = 0

    # Check column-wise
    for col in range(C):
        count = 0
        for row in range(R):
            if grid[row][col] == '#':
                count += 1
                max_streak = max(max_streak, count)
            else:
                count = 0

    return max_streak

# Driver code
T = int(input())
for _ in range(T):
    R, C = map(int, input().split())
    grid = [input().strip() for _ in range(R)]
    print(max_border(grid, R, C))

---

✅ 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:

txt
.#.###.##.

• 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 5 as the max for this row, but the correct border is 3.

✅ 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:

text
#..#
#..#
#..#

→ 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 extract 2 (rows) and 15 (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:

python
max_row_streak = 0
count = 0
for cell in row:
    if cell == '#':
        count += 1
        max_row_streak = max(max_row_streak, count)
    else:
        count = 0

---

Step 4:

Maintain max_border to 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:

python
for col in range(num_cols):
    count = 0
    for row in range(num_rows):
        if matrix[row][col] == '#':
            count += 1
            max_border = max(max_border, count)
        else:
            count = 0

---

✅ 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!

Tags: Technology,Algorithms,