Array

Posted by Abhishek on December 14, 2019

Fundamentals

Arrays are built into most programming languages and we use them to SORT a list of items sequentially. Since Arrays are a type of Linear Data Structures, they store data in the memory sequentially.

For example, if we have a set of 5 integers [10, 20, 30, 40, 50], they would be allocated in the memory as shown below. The reason why memory address advances by 4 is because an integer takes 4 bytes of memory.

Because Array elements are arranged sequentially in memory, accessing it by INDEX is super fast

Thus, the Runtime Complexity of Accessing a Data Element in An Array by Index is O(1).

Why O(1)? It’s because you are telling the system to get you the value stored in a memory address (Example: Get me the value in 104 memory address. System returns 20). The system doesn’t have to do complex calculations or iterations to figure out this. It’s super-efficient.​

Strength of Arrays

• If you have a use-case where you have to STORE items & RETRIEVE items by INDEX, Arrays are the most optimal choice.

Weakness of Arrays

• Arrays are static in nature
  • You need to explicitly specify the size of an array when allocating it
  • The allocated size cannot be changed later
  • So, we need to know ahead of time how many items we are going to store in an array
  • If you don’t know, you have to make a guess
  • If you guess a large size, you are wasting memory
  • If you guess too small, you will not have space to put the data. Thus, you will have to resize the array by creating a new one with the desired size and copy all data from the old array to resized array. This process is time-consuming and takes O(n) for resize & copying data.
• In cases where you don’t know the size of items to store, it’s better not to choose Arrays. Linked Lists can be a better choice for this use-case.

Runtime Complexity of Arrays

• Retrieving an item by INDEX – O(1)
  • Justification: System simply returns the value from the memory location
• Inserting an item – O(n)
  • Justification: In the worst case, you might be inserting an item into an array when the array is full. So, you will need to allocate a new array of larger size, iterate over all n items and copy all the n items from the old array to resized array. Thus O(n)
• Deleting an item – O(n)
  • Justification: In the worst case, you delete an item present at the start of an array. Here, the first item has to be deleted and you have to shift all other items one step back. Due to the shifting of all other items, the deletion takes O(n).

Basic Program of an Array

// Declaration of an array
int[] numbers = new int[3];
// Inserting an item into an array
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
// Printing an array
foreach (var item in numbers)
{
  Console.WriteLine(item);
}

Coding Exercise – Array

• Create a class “Array” that can take an initial length during initialization
• Implement “print” method that prints only the items present in the array
• Implement “insert” method that takes an integer and inserts to the Array object
• The “insert” method should resize the array object in case of items more than the initialized length is inserted.
• Implement “removeAt” method that takes an index and removes it from the array. Note that items removed should shift items in the array accordingly.
• Implement “indexOf” method that takes an integer and return its index. Calling indexOf method with a non-existing value should return -1.
• Do not use any existing/imported data structures. Only work on int[] and its capabilities.

Note: Ensure to evaluate the runtime complexity of the methods that you write. Make sure that your implementations match the runtime complexity of basic int[].

Once the Array class is constructed, we should be able to write something like this in the main method.

Array numbers = new Array(3);
numbers.insert(10);
numbers.insert(20);
numbers.insert(30);
numbers.insert(40); //should not fail. Instead resize
numbers.removeAt(3); //remove & shift items
Console.WriteLine("====Printing Array====");
numbers.print();
Console.WriteLine(numbers.indexOf(10)); //return 0 because this is the first index
Console.WriteLine(numbers.indexOf(100)); //returns -1

Push yourself a bit more on Coding Exercise

1. Extend the Array class and add a new method named “max” to return the largest number. The Array elements may or may not be sorted.
2. Extend the Array class and add a method named “intersect” to return the common items in this array and another array.
3. Extend the Array class and add a method named “reverse” to reverse the array. For example, if the array includes [1, 2, 3, 4], after reversing and printing it, we should see [4, 3, 2, 1].
4. Extend the Array class and add a new method named “indexAt” that takes an item and index and inserts that item at the given index.

public class Array
{
    private int[] items;
    private int count; public Array(int length)
    {
        items = new int[length];
    }
    public void print()
    {
        for (int i = 0; i < count; i++)
        {
            Console.WriteLine(items[i]);
        }
    }
    public void insert(int newNumber)
    {
        if (items.Length == count)
        {
            int[] newItems = new int[count * 2];
            for (int i = 0; i < count; i++)
            {
                newItems[i] = items[i];
            }
            items = newItems;
        }
        items[count++] = newNumber;
    }
    public void removeAt(int index)
    {
        if (index < 0 || index >= count)
            throw new ArgumentException();
        for (int i = index; i < count - 1; i++)
        {
            items[i] = items[i + 1];
        }
        count--;
    }
    public int indexOf(int item)
    {
        for (int i = 0; i < count; i++)
        {
            if (items[i] == item)
            {
                return i;
            }
        }
        return -1;
    }
    public int max()
    {
        if (count <= 0)
        {
            throw new Exception("No items in the array");
        }
        else if (count == 1)
        {
            return items[0];
        }
        else
        {
            int largest = items[0];
            for (int i = 0; i < count - 1; i++)
            {
                if (items[i + 1] > largest) largest = items[i + 1];
            }
            return largest;
        }
    }
    public int valueAt(int index)
    {
        return items[index];
    }
    public bool contains(int value)
    {
        for (int i = 0; i < count; i++)
        {
            if (items[i] == value)
            {
                return true;
            }
        }
        return false;
    }
    public Array intersect(Array newArray)
    {
        int intersectArraySize = this.count > newArray.count ? this.count : newArray.count;
        Array intersectedArray = new Array(intersectArraySize);
        for (int i = 0; i < this.count; i++)
        {
            for (int j = 0; j < newArray.count; j++)
            {
                if (items[i] == newArray.valueAt(j) &amp; amp; &amp; !intersectedArray.contains(items[i]))
                   {
            intersectedArray.insert(items[i]);
        }
        return intersectedArray;
    }
    public Array reverse()
    {
        Array reverseArray = new Array(count);
        for (int i = count - 1; i >= 0; i--)
        {
            reverseArray.insert(items[i]);
        }
        return reverseArray;
    }
    public void insertAt(int item, int index)
    {
        if (items.Length == count)
        {
            int[] newItems = new int[count * 2]; for (int i = 0; i < count; i++)
            {
                newItems[i] = items[i];
            }
            items = newItems;
        }
        for (int i = count; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = item; count++;
    }
}