How to find top most element and left most element in any island in a graph?

help
, , ,
1

. . . . . . a A . . . .
. . . . . . A . . . . . .
. . . a A A A . . . .
. . . A . . . A . . . .
. . . A A A A . . . .

How to find top most element and left most element in any island in a graph?
I know how to find an island and its area in a graph, but I’m stuck with this.
Please help!!

In the above example, I want to find the positions of the characters denoted with “a” .

2

you store the data inside a 2d array and iterate through it.

Your Data:

. . . . . a A . . 
. . . . . A . . . 
. . a A A A . . . 
. . A . . . A . . 
. . A A A A . . .

iterate through columns first, then rows. Break if you find an A

01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45

iterate through rows first, then columns. Break if you find an A

01 06 11 16 21 26 31 36 41
02 07 12 17 22 27 32 37 42
03 08 13 18 23 28 33 38 43
04 09 14 19 24 29 34 39 44
05 10 15 20 25 30 35 40 45
1 Like
4

probably but it depends on the constraints. Please link the problem.

5

I have seen this in an Online Assessment. But I remembered the constraints and one example.

Constraints 1 <= N <= 50.

Example:

N = 5

1 1 0 0 0
0 1 1 0 0
1 0 1 0 0
0 0 0 0 0
0 0 0 0 1

For this, the answer will be 4.

6

I have an approach, but I cannot proof it is correct.
Lets pretend a 0 means no square at the given position, a 1 means a 1x1 square at the given position, a 2 means a 2x2 square at the given position and so on. We obviously don’t have any 2’s or higher, but that does not mean we cannot add them ourselves.

So I would start by counting all 1’s, which is our initial cost. Then I try to place a 2x2 square in any position of our grid, and if the resulting cost is at least equal (or lower) to our current cost, I write that number inside a new matrix. And then copy all 1’s that are not covered by 2’s. Then repeat for 3’s, 4’s, …, n’s
Example:

max size: 1x1 - total cost: 16 
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1 1
max size: 2x2 - total cost: 10 
2 0 0 0 0 0 0 2 0
0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0
max size: 3x3 - total cost: 9 
3 0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0
max size: 4x4 - total cost: 9 
4 0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0

Example 2 (worst case for 4x4)

max size: 1x1 - total cost: 16 
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
max size: 2x2 - total cost: 18 
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
max size: 3x3 - total cost: 12 
3 3 0 0
3 3 0 0
0 0 0 0
0 0 0 0
max size: 4x4 - total cost: 4 
4 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Edit 1: I am uncertain about the time complexity. If we brute forced literally everything, we would end up with O(N³ * log N) I think.
Edit 3: I played around with excel, the brute force time complexity is O(N³*log N). In the case of N = 50, it is lower than O(50^3 * ln 50 * 2)

Edit 2: Also note that the total cost can increase if you try a step from i → i+1. This only means the cost will later come down again, because of a heavy overlap.

7

Okay, that sounds interesting. I’ll try this and check for some testcases.

8

I don’t get this when you mean any position. Can you please explain it a bit more!