Ace the Basics of Arrays: A Step-By-Step Guide
Tags: arrays, dsa, python
Published: 2023-02-26 09:48:42

## Array Introduction
An array is a contiguous block of memory, and the simplest data structure known so far. It is usually used to represent sequences.
**Example**:
Given an array A[i], A[i] denotes the (i + 1)th object stored in the array.
With your typical use of arrays, the **Time complexity** for retrieving and updating data from an array takes O(1) time.

## Array Actions
Here, we will look at the **Time complexities** of inserting and deleting an element of an array, and hopefully, the explanation will be clear enough for anyone to understand.
Also in the future, other aspects of arrays, like modifying/changing an element in an array will be covered. But for now, we will stick to the basics.

### Insertion of An Element In An Array
Insertion of new data/element into a full array can be handled by resizing i.e. allocating a new array with additional memory, and copying over the entries from the original array increases the worst-case time of insertion.
But, if the new array has a constant factor larger than the original array, the average **Time complexity** for insertion is constant O(1), since resizing is infrequent.

### Deletion of An Element In An Array
Deletion of an element from an array involves moving all successive elements one over to the left to fill the space left from the deleted/removed element in the array.
The **Time complexity** to delete/remove an element at index _i_ from an array of length _n_ is O(n - i). The same applies when one is inserting a new element into the array using the same principle.
_Examples_:
If we have an array/list of elements {1, 2, 3, 4, 5, 6, 7} and we want to remove the element at index 3, to the uninitiated and those who are familiar with languages like COBOL, FORTRAN or AWK (not THAT awk), the value they'd be expecting to get cut off is 3, but if we followed the example given at the intro, the value getting removed is 4. This is because we are following the principle that 4 in the array (we'll call it A) A[4] is the (i + 1)th object stored in the array, where `i` is the index of the array.
You might have a solid argument if the language(s) you use that follows this principle, but I'm not gonna indulge you on that, take it to the stack overflow overzealous wizards!

## Problem(s)
This problem statement gives us an insight of working with arrays (or lists if you are using Python), but for the sake of avoiding confusion on my part, arrays/lists are arrays, unless stated otherwise.
For the question, they'd be structured in an unordered list. Sure looks weird for some leetcode warriors out there, but for us normies, it should make it easier to understand each requirement, whiteboard and explain the complex parts where necessary, which leads to you thinking up a good solution or ask the interviewer the right question(s) for hints that could lead to a potential answer.

### Problem 01
**The question**:
- You are given an array of integers
- You have to reorder the entries so that even entries appears first
- You are required to solve this without adding additional space

If the last option was not an option, we'd simply do the following:
- split the array into two sub-arrays called `left` and `right`
- write a `for` loop that traverses the array, with a parameter, most likely `i`
	- inside the `for` loop, we write a conditional to check if the elements (or numbers if you must) is a modulus of 2, i.e. the remainder is 0
	- if it is, we add the number to the array (how? append the even number to the `left` sub-array)
	- if it is not a modulus of 2, i.e., there is a remainder of 1+, append to the `right` sub array
- return the values of the two sub-arrays combined.

The **Time complexity** may be O(n), in which congratulations are in order, but the instructions does not want you to allocate any space to the array.

If you were to follow the instructions to get the **Space complexity** to be O(1), a third sub-array is needed. The third sub-array will be the original array you are sorting. So, from a point in your original thought process:

- the third sub-array (lets call it `original`) is iterated
- from the point where you check for even and odd values, swap the values from `original` to `left` or `right` sub-arrays. This expands the two sub-arrays, and shrinks the `original` array. No additional space created for the new arrays, just a swap of sorts happening.
`arrayBasic01.py`
```Python
#!/usr/bin/env python3
"""O(n) space array i.e. allocated space to the array"""
def even_left(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        if arr[left] % 2 == 0:
            left += 1
        else:
            arr[left], arr[right] = arr[right], arr[left]
            right -= 1
    return arr
```

`000-testArray.py`
```Python
#!/usr/bin/env python3
from arrayBasic01 import even_left

arr = [1, 2, 3, 4, 5, 6, 7, 8]

print(even_left(arr))
```

The code above will output `[8, 2, 6, 4, 5, 7, 3, 1]`.
**Note**: If you got OCD (feel free to modify) or think this is wrong, stop depending 100% on chatGPT. Its solutions resulted in this output despite it trying to force its 'correct' answer on me (its output was [2, 4, 6, 8, 1, 5, 7, 9] if you're wondering).

#### What's Going On
What made the **Space complexity** to be O(1) (chatGPT adamantly says it is impossible despite giving me an answer with O(1) space), is there is a variable that holds the indices (indexes), and a temporary variable for performing swaps.
For **Time complexity** analysis, since a constant amount of processes is done per entry to the sub-arrays, it is O(n), where `n` is the length of the array.

To close this entry, I'll drop some tips I read up;

1. Be comfortable writing code that utilizes subarrays
2. When operating an array, do not forget that indexes starts from 0
3. When operating 2D arrays, use **parallel logic** for rows and columns
4. Don't worry about order of an array, i.e. they must be equal, or see the note of the problem statement above

For more Array problems, approach and solutions, I'm building a repo of sorts for that, will contain leetcode questions and solutions (basically interview questions). Anyways, till next time.