Ace the Basics of Arrays: A Step-By-Step Guide

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

#!/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

#!/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.