Arrays

An array is one of the fundamental data structures available and most widely used by developers today to solve general problems. You can think of an array as a collection of variables of a certain data type stored contiguously in memory. The values of an array can be accessed through an index (commonly represented by the variables i, j, and k), and the ith value of an array is denoted as Array[i].

This article is not to be confused with associative arrays, which is a fancy way of calling the key-value-pair data structure. We will discuss it separately.

  • int array[10] = { 10, -4, 5, 0, 3, 2, 88, 67, -100, 7};

Given an array of integers above, we say that the first element is 10, the 3rd is 5 and the last is 7. This can be denoted as array[0], array[2], and array[9] respectively in most programming languages. So if we have another integer X and want to assign the 5th element of the array to X, this will be expressed as:

  • X = array[4]

Assigning a value to an array works in a similar way. Let's say we want to override or assign zero (0) to the 7th element. We express it as:

  • array[6] = 0

Important Note: some Programming languages start referencing index at 1.

It is the responsibility of the programmer to assign a meaningful value to an array element before using it. Neglecting this procedure may cause your program to crash or to output unexpected results. Some compilers like C++ are intelligent enough to detect such problems during compile time.

Advantages and Disadvantages:

The major disadvantage of an array is that it consumes a fixed number of memory locations even before actually using any of its elements. It is necessary to know the maximum number of elements so you don't go beyond the limit. The problem with this is you could have used the allocated memory to other resources. But preallocating just enough memory is not too bad. Hardware is getting cheaper and larger in capacity, although that doesn't give you a license to waste resources.

The shortage of preallocating memory resources is compensated for its speed. Arrays can be accessed at the same speed, regardless of whether you're accessing the first element, the middle, or the last. This random access property of an array makes it the best candidate for algorithms requiring speed, such as a Hash Table.

  • for (i = 0; i < MAX; i++) array[i] = i;

Since an array is contiguous, all the compiler has to know is to know the address of the first location and add the index that you want access to. This is true for all elements of the array, hence speed is not changed at any given point.

When to Use an Array?

The general idea is when there is a need to store a number of data of the same type. 

Storage / Caching / Memoization

Storage / Caching / Memoization is the most common use of array as you need to store all data or pre-computed values as a reference to the next procedure.

A practical example is to cache all the values of sine and cosine for each degree from 0 to 359. The values can then be repeatedly used without invoking the sin and cos functions making your program more efficient.

    long double sine[360], cosine[360];

    for (int i = 0; i < 360; i++)
    {
        sine[i] = sin(i * PI / 180);
        cosine[i] = cos(i * PI / 180);
    }

To Represent Other Data Structures

Representing Queues, Stacks, and Trees as Array optimizes your code due to the reduction of push, pop, insert, add and remove operations. This is on the assumption that you're given the constraint of the requirements. Below is an example of counting the number of right and down routes in a 20 x 20 Lattice Grid, implemented using a regular Stack first, and then as an Array Stack (Interested in the Lattice Path Problem? See the full article and program starting from this link here).

Implemented as Regular Stack:

long long countRouteBruteForce(void)
{
    std::stack <Coord>s;
    Coord c;
    long long count = 0;

    s.push({ 0, 0 });

    do
    {
        c = s.top(); s.pop();

        if (c.x == MAX_SIDES && c.y == MAX_SIDES)
        {
            count++;
            std::cout << c.combo << " (" << count << ")" << "\n";
        }
        else
        {
            // Right
            if (c.x < MAX_SIDES) 
                s.push({ c.x + 1, c.y });
            
            // Down 
            if (c.y < MAX_SIDES) 
                s.push({ c.x, c.y + 1 });
        }
    } while (!s.empty());

    return count;
}

Implemented as an Array Stack:

long long countRouteBruteForceArray(void)
{
    Coord s[21], c;
    long long stackIdx = 0;
    long long count = 0;

    s[stackIdx++] = { 0, 0 };

    do
    {
        c = s[--stackIdx];

        if (c.x == MAX_SIDES && c.y == MAX_SIDES)
            count++;

        else
        {
            // Right
            if (c.x < MAX_SIDES) 
                s[stackIdx++] = { c.x + 1, c.y };

            // Down 
            if (c.y < MAX_SIDES) 
                s[stackIdx++] = { c.x, c.y + 1 };    
        }
    } while (stackIdx > 0);

    return count;
}

Array Dimensions

Arrays can have one or more dimensions depending on the program design and/or convenience of the programmer. A simple example would be a multiplication table, as it needs to be represented in a two (2) - dimensional array. We represent the array depending on what is convenient and what is appropriate to the solution. Representing it differently will make it cumbersome for the programmer to implement the solution.

Converting Multi-Dimensional Arrays to Single Dimensions

It is important to realize that computer memory is designed and accessed as a single contiguous resource at the lowest level of processing. Mapping out a multi-dimensional array to a single-dimensional representation gives you an idea of how handling such data structure works.

One can convert a multi-dimensional array[ N ][ M ], with M as max value for columns, and N as max values for rows, as one single array representation by multiplying j by M and adding the index i, where j is the index to N, and i is the index to M. You refer to the value of array[ j ][ i ] as array[ j * M + i ] in a single-dimensional array representation with size M * N.

The same thing could be done for 3, 4 .... and other higher dimensions. To test your understanding of the matter, try to represent a cubic array[O][N][M] as a single-dimensional array, with indices k, j, and i corresponding to O, N, and M respectively.

Array Exercises

The following are simple exercises to help you better grasp the concept of Array and better understand how it works.

  1. Find all the Prime Numbers between 2 to N using the Sieve of Erasthosthenes. 

    In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

    It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with a constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime

  2. Cache the values of sine and cosine functions from 0 to 360 degrees at a finer increment of 0.25 degrees. Use the values of the array to rotate an object (say a square) from a certain reference point.
     
  3. Write a regular stack-based solution for a parenthesis checker. Given a string, check if all open parentheses have matching close parentheses or vice versa. Convert your program to an array-stack-based solution afterward.