How does the 2d to 1d conversion work

[vnyapathi]

N * (y - 1) + x - 1; Can you explain how this works for 0,0 and a 5by5 grid. Won't it be something like -6.

[alexilyenko]

@vnyapathi what problem are you referring to?

[vnyapathi]

The percolation problem.

Sent from my iPhone

On 28 Jan 2019, at 02:30, Alex Ilyenko notifications@github.com wrote:

@vnyapathi what problem are you referring to?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[alexilyenko]

I'm a bit out of context over here, since I was working on this 4 years ago, but let's see what we can figure out.

Basically, you're referring to the function which transforms two-dimensional array into the one-dimensional one.

So if you have something like that:

[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 16]

it means N = 4 and this array should be transformed into:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Let's move row by row. First row (y = 1, N = 4): 4 (1 - 1) + 1 - 1 = 0 4 (1 - 1) + 2 - 1 = 1 4 (1 - 1) + 3 - 1 = 2 4 (1 - 1) + 4 - 1 = 3

Second row (y = 2, N = 4): 4 (2 - 1) + 1 - 1 = 4 4 (2 - 1) + 2 - 1 = 5 4 (2 - 1) + 3 - 1 = 6 4 (2 - 1) + 4 - 1 = 7

Third row (y = 3, N = 4): 4 (3 - 1) + 1 - 1 = 8 4 (3 - 1) + 2 - 1 = 9 4 (3 - 1) + 3 - 1 = 10 4 (3 - 1) + 4 - 1 = 11

Fourth row (y = 4, N = 4): 4 (4 - 1) + 1 - 1 = 12 4 (4 - 1) + 2 - 1 = 13 4 (4 - 1) + 3 - 1 = 14 4 (4 - 1) + 4 - 1 = 15

I think the confusing part for any Java engineer over here would be that we start counting from 1, and not from 0 in two-dimensional array and doing exactly the opposite in the regular one (starting from 0). And it's not clear for me as well :) I guess that was specified in the task given by Mr. Sedgewick (The Algorithms lecturer), but this should be double-checked.

Without that condition you could use the corrected formula as follows: N * y + x

Hope that helps!