Array indexing Row and Column major order

You just need to remember 2 formula's then you can easily solve any type of problems related to this. I found out from a source while i was preparing for gate. It also helped me solve interview questions asked at iit delhi.

Column Major -> (n₁ + N₁(n₂ + N₂(n₃ + …..)))

     Row Major -> (n_d + N_d(n_d-1 + N_d-1(n_d-2 + …..)))

You can solve any dimension (1D, 2D, 3D,...) problem using the above formula.

................................

Lets solve a 2D array problem now.

Q. A is an array [1...10, 1....15] or [1...10][1...15] of elements. The

 starting location is 100. The location of an element A[i,j] or A[i][j]

 using row major order is? 

or, lets see the same question in a different tone...

Q. Let A be an array.

int A[][] = new int[10][15];

starting location of array is 100. Index starts from A[1][1].

The location of element A[i][j] using row major order is?

Answer:

Look at the formula for row major order:

(n_d + N_d(n_d-1 + N_d-1(n_d-2 + …..)))

here as only 2 dimensions are there (2D array) our formula reduces to

(n₂ + N₂(n₁))

Total number of elements present in 2nd dimension. 

N2 = 15 -1 + 1 = 15

Here we don't need N1 as in formula N1 doesn't exist.

Still if you like to calculate, N1= 10 -1 +1 = 10

A[i][j] location is asked so n1=i, n2=j

Don't forget to subtract 1 from n1 and n2 as our starting index is

 from A[1][1] not A[0][0]. 

Putting the above values in formula we have,

((j-1) + 15(i-1))

= 15i + j -16

Assuming size of int to be 1 Byte.

base address given = 100

Location of A[i][j] = base address + size*(value we calculated)

= 100 + 1(15i + j -16)

= 15i + j + 84

.................................

Lets solve a 3D array problem now.

Q. A is an array [2...6, 2....8, 2....10] of elements. The starting location

 is 500. The location of an element A[5,5,5] using column major order 

is?

or, lets see the same question in a different tone...

Q. Let A be an array.

int A[][][] = new int[6][8][10];

starting location of array is 500. Index starts from A[2][2][2].

The location of element A[5][5][5] using column major order is?

Answer:

See the column major order formula.

(n₁ + N₁(n₂ + N₂(n₃ + …..)))

Now just calculate the total number of elements present in each 

dimension, i.e. N1, N2 and N3 as 3 dimension array is considered.

N_{1  = 6 - 2 +1 = 5}

N2  _{= 8 - 2 +1 = 7}

N3  _{= 10 - 2 +1 = 9}

Location of element A[5][5][5] is asked so n1=5, n2=5 and n3=5.

Don't forget to subtract 2 from n1, n2 and n3 because our starting

 location is from A[2][2][2] not A[0][0][0].

Putting the above things in formula.

((5-2) + 5((5-2) + 7(5-2))

= 123

Let size of int be 1Byte.

Exact location address of A[5,5,5] = base address + size*(value we

 just calculated)

= 500 + 1*(123)

= 623