Static Arrays - DSA Notes 📝

Introduction

Welcome to my new series on the BIG topic, Data Structures & Algorithms. Follow along with me as I learn everything about DSA to grind Leetcode!💪
Here, you will find all my notes on the topic. Starting everything off with Arrays. 😀

🎯 Learning Goal

• What are the characteristics of static arrays?
• What does reading, inserting and deleting look like for static arrays?

🧠 Key Concepts (aka My Notes)

Static Arrays

The size of a static array cannot change once declared. Once they are full, you cannot add more items.

Reading

Accessing a certain element in an array is always instant because you have the index number.

⌚ Time complexity is O(1).

O(1) means it's constant time. Even if the size of the data grows, the number of operations stay the same.

Traversing

You can use for/ while loops to go through an array and do a certain operation. (for example, printing everything in an array)

⌚ For an array of size n, the time complexity is O(n).

This means that the number of operations grow linearly with the size of the data.

Deleting

Deleting from End of Array

In statically typed languages (not JS or Python), you can remove element at the end (n-1 index) by the way of soft delete.

• Soft Delete is basically overwriting the value of an element you wanna delete to 0, null or -1.

# The last element is overwritten by 0. Length is decremented.
def deleteEnd (arr, length):
    if length > 0:
        arr[length - 1] = 0
        length -= 1
    return length

⌚ Time complexity is O(1).

Deleting at ith index

• Shift all values one position to the left of the index i
• By shift to left, it means just overwrite the arr[i] with the value from the right

def deleteMiddle (arr, length, i):
    # From i + 1 to length - 1, shift left by one position
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]

⌚ Time complexity is O(n).

This is because the worst case is we have to shift everything in the array of n size to
the left.

Insertion

Inserting at the End of Array

• Insert at the length index.

def insertEnd (arr, length, capacity, value):
    if length < capacity:
        arr[length] = value

⌚ Time complexity is O(1).

Inserting at the ith index

• Shift everything to the right of i
• If it's full, the last element is lost
• Then, insert at the specified index

def insertMiddle(arr, i, value, length):
    # Shift elements to the right to make space for the new element
    if i < length:
        # Index will decrement from the very end up to i
        # value at i will move and we overwrite the old value with our inserted value
        for index in range(length - 1, i - 1,-1):
            arr[index - 1] = arr[index]

        # Insert vale at specified index
        arr[i] = value

⌚ Time complexity is O(n).

⌚ Time Complexity

💪 LeetCode Problems

• 26. Remove Duplicates from Sorted Array (Link)
• 27. Remove Element (Link)