Multidimensional arrays

2D

The arrays that we have just learned had only one dimension. We represented them as a single row of values, accessed by index. An array with two dimensions can be represented as a table. Elements are accessed with two indices. The first – for the rows and the second for the columns.



They are:
 - independent by size – you can have as many as you need.
 - start from 0 and reach the number of items -1.

Depending on the programming language they are:
 - separated by a comma: [first, second]; This is what we will use in the tutorial.
 - ..or in separate brackets: [first][second].

Here is one example: numbers[3, 4] is a 2D array, named “numbers”. It has 3 rows and 4 columns.

numbers[3, 4]
1 4 -3 0
6 7 -18 -10
0 1 -2 -1

To access the value on the second row and third column we need to write numbers[1,2]. In the example below it has value 18. Iterating through all elements is done with two nested loops.

Example: Initialize all elements of numbers[3. 4] with 0.

Initialize two dimension array

In this case “i” indexes the rows and “j” - the columns. Start with the first row (i = 0). Check if the current row is within the table (i < 3). Then do the same for “j”. At this moment (i = 0, j = 0) numbers[0, 0] takes the value 0. Then increment the column and set the second item of the first row to 0. When the entire row is set to 0 (j < 4 returns false), i++ goes to the next row. This will repeat until all values are set to 0.

The next example goes through a 2D string array and counts the occurrences of the string “programming”.

Count string occurrence in two dimensional array

Sometimes you need to work only with a given row or column. Then you fix the corresponding index to constant value.
For example: people[100, 4] keeps data about 100 people. The columns keep the following information: name, gender, hairColor, eyeColor. Find how many people have blue eyes.

No nested loops are necessary for this task. Instead, the column index is fixed to the last column.

Square matrices

When the dimensions of a 2D array are equal(N = M), we call it a square matrix. It is an interesting case and it is often used in calculations. It also has some additional characteristics that we will look into: main diagonal, secondary diagonal, elements above the diagonal and elements under the diagonal.

Let's start with a 4x4 matrix. All elements in a square matrix that have equal indices (i = j) form the main diagonal (see the table below – note that in this example inside the table are written the indices, not the values).

matrix[4, 4]
0, 0
1, 1
2, 2
3, 3

All elements with index sum equal to N – 1 (i + j = N – 1) form the secondary diagonal.

matrix[4, 4]
0, 3
1, 2
2, 1
3, 0

Example: Output the values of all elements of the main diagonal in a square matrix ( matrix[N, N]).

Main diagonal in a matrix - output values

Did you noticed how we use the same variable for both rows and columns? This is the easiest and most effective way to work if you manipulate only the main diagonal items.

Try to find out on your own what is common for all elements under the main diagonal before you continue to read under the table.

matrix[4, 4]
...
1, 0
2, 0 2, 1
3, 0 3, 1 3, 2

Did you figure it out? Under the main diagonal the row index is always greater than the column.

Example: find the biggest number under the main diagonal in matrix[5, 5]

Elements under the main diagonal in a matrix - find the biggest element

In order to find the biggest value in array we need to compare the items. But what to compare the first value to? Compare with 0? Suppose that all numbers are negative. Then we will end up having 0 as the greatest value and this is not correct. For such cases most of the programming languages provide some constant values, such as minValue, maxValue and others.

MinValue is the smallest value for a give data type. You should already know how to follow the rest of the algorithm.

Matrices and chess tasks

A chess board is made of 64 squares (8x8). Its board is easily represented by a two dimensional array. If we have the coordinates of two pieces we can find if they attack each other. For such tasks the input data are integer variables, containing the position of those pieces.

Example: Check if a white rook can take a black bishop. The coordinates are in the variables Rr, Rc, Br, Bc(RookRow, RookColumn, BishopRow, BishopColumn).

Chess rules state that the rook can attack by straight line – either horizontal or vertical. If it attacks the bishop, then they are on the same row or column. Let's make one example to see how it looks like on the chess board:

Matrices and chess tasks - A rook and a bishop
Matrices and chess tasks - Rook attacks

So it is that easy :-). In the example that answer in “No”.

Now, let's see how to check if the bishop attacks the rook. The bishop can move by diagonal. How can we determine if the rook is on the same diagonal? We need to find something that is common for all elements in the diagonals. First, the diagonals are two types – in the direction of the main and in the direction of the secondary. Take a paper, draft a 8x8 two dimension array and fill the indices for one or two diagonals in the direction of the main. Try to find the mathematical relationship before you read the next rows.

Diagonals with the direction of the main diagonal.
The difference between the row and column indices is constant for a given diagonal in that direction. For instance, the main has a constant difference of 0 (0-0 = 0, 1-1=0...(N-1)-(N-1)=0).
 - Subtract the indices of the rook
 - Subtract the indices of the bishop
 - Compare the two results. If they are equal, then the two pieces are on the same diagonal and the bishop attacks the rook.

Now, find the common between the elements, located in a diagonal in the direction of the secondary before you continue...

The sum of the row and column index is constant for any diagonal in the direction of the secondary.
 - Sum the indices of the rook.
 - Sum the indices of the bishop
 - Compare the two results. If they are equal, then the two pieces are on the same diagonal and the bishop attacks the rook.

Combining the above, let's see if the bishop attacks the rook:

bishop attacks rook flow chart

Again – the algorithm is simpler than the explanation. In the example above the bishop attacks the rook. Their indices satisfy the first condition.

Homework

For a given two dimension array:

  1. Output the values of all elements
  2. Find the sum of all values in the third column
  3. Find the smallest number above the main diagonal in square matrix(NxN).
  4. Given are the coordinates of a white queen and a black queen. Check if they can attack each other.
    Helper: the queen can move and attack both by straight line(like a rook) and by diagonal(like a bishop).

Previous: Arrays

Next: Programming questions

Tutorial Contents:

1)Learn Computer Programming
2)Software Development Process
3)Flow Chart
4)Flow Chart Symbols
5)Data Type
6)What is a variable
7)Math Operators
8)Logical Operators
9)Loops

10)Nested Loops
11)Arrays
12)Multidimensional arrays
13)Programming Questions

   Search this site: