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 ***@***.***> 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!