Basic Operations

Reading arr[999] from a million-element array is instant. So is reading arr[0]. But inserting a value at arr[0] is one of the slowest things you can do to an array. Same array, same one-element operation — why is one free and the other expensive?

The answer is the whole personality of the array, and it’s written in the operation costs below. Every data structure is defined by what it makes cheap and what it makes painful:

Operation	Time	Space	Notes
Access by index	O(1)	O(1)	Direct calculation using address formula
Search (unsorted)	O(n)	O(1)	Must check every element
Search (sorted)	O(log n)	O(1)	Binary search
Insert at end	O(1)	O(1)	O(n) if array needs resizing
Insert at position	O(n)	O(1)	Must shift elements right
Delete at end	O(1)	O(1)	Just decrement size
Delete at position	O(n)	O(1)	Must shift elements left
Find min/max	O(n)	O(1)	Must scan entire array

Predict first

To insert a value at index 0 of a 1,000-element array, how many existing elements have to move?

Access by index is O(1) but search (unsorted) is O(n). What explains the difference?

Approach 1: Using Static Arrays

Insert an Element

ALGORITHM

Step 1: [INITIALIZATION] SET lower_bound = 0
Step 2: SET upper_bound = size - 1
Step 3: SET i = upper_bound
Step 4: Repeat Steps 5 to 6 while i >= lower_bound
Step 5:     SET A[i + 1] = A[i]
Step 6:     SET i = i - 1
[END OF LOOP]
Step 7: SET A[insertPosition] = element
Step 8: SET size = size + 1
Step 9: EXIT

CODE

void insertElement(int arr[], int &size, int element, int position)
{
    if (size >= MAX_SIZE)
    {
        cout << "Array is full. Cannot insert element." << endl;
        return;
    }
 
    if (position < 0 || position > size)
    {
        cout << "Invalid position. Cannot insert element." << endl;
        return;
    }
 
    for (int i = size - 1; i >= position; i--)
        arr[i + 1] = arr[i];
 
    arr[position] = element;
    size++;
}

Delete an Element

ALGORITHM

Step 1: [INITIALIZATION] SET lower_bound = 0
Step 2: SET upper_bound = size - 1
Step 3: SET i = position
Step 4: Repeat Steps 5 to 6 while i < upper_bound
Step 5:     SET A[i] = A[i + 1]
Step 6:     SET i = i + 1
[END OF LOOP]
Step 7: SET size = size - 1
Step 8: EXIT

CODE

void deleteElement(int arr[], int &size, int position)
{
    if (size <= 0)
    {
        cout << "Array is empty. Cannot delete element." << endl;
        return;
    }
 
    if (position < 0 || position >= size)
    {
        cout << "Invalid position. Cannot delete element." << endl;
        return;
    }
 
    for (int i = position; i < size - 1; i++)
    {
        arr[i] = arr[i + 1];
    }
 
    size--;
}

Find an Element

ALGORITHM

Step 1: [INITIALIZATION] SET index = -1
Step 2: SET lower_bound = 0
Step 3: SET upper_bound = size - 1
Step 4: SET i = lower_bound
Step 5: Repeat Steps 6 to 7 while i <= upper_bound
Step 6:     If A[i] equals element, SET index = i and EXIT LOOP
Step 7:     SET i = i + 1
[END OF LOOP]
Step 8: RETURN index
Step 9: EXIT

CODE

int findElement(int arr[], int size, int element)
{
    for (int i = 0; i < size; i++)
    {
        if (arr[i] == element)
        {
            return i;
        }
    }
    return -1; // Element not found
}

Find Minimum Element

ALGORITHM

Step 1: [INITIALIZATION] SET min = A[0]
Step 2: SET lower_bound = 1
Step 3: SET upper_bound = size - 1
Step 4: SET i = lower_bound
Step 5: Repeat Steps 6 to 7 while i <= upper_bound
Step 6:     If A[i] < min, SET min = A[i]
Step 7:     SET i = i + 1
[END OF LOOP]
Step 8: RETURN min
Step 9: EXIT

CODE

int findMin(int arr[], int size)
{
    int min = arr[0];
    for (int i = 1; i < size; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    return min;
}

Find Maximum Element

ALGORITHM

Step 1: [INITIALIZATION] SET max = A[0]
Step 2: SET lower_bound = 1
Step 3: SET upper_bound = size - 1
Step 4: SET i = lower_bound
Step 5: Repeat Steps 6 to 7 while i <= upper_bound
Step 6:     If A[i] > max, SET max = A[i]
Step 7:     SET i = i + 1
[END OF LOOP]
Step 8: RETURN max
Step 9: EXIT

CODE

int findMax(int arr[], int size)
{
    int max = arr[0];
    for (int i = 1; i < size; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    return max;
}

Find Sum of all Elements

ALGORITHM

Step 1: [INITIALIZATION] SET sum = 0
Step 2: SET lower_bound = 0
Step 3: SET upper_bound = size - 1
Step 4: SET i = lower_bound
Step 5: Repeat Steps 6 to 7 while i <= upper_bound
Step 6:     SET sum = sum + A[i]
Step 7:     SET i = i + 1
[END OF LOOP]
Step 8: RETURN sum
Step 9: EXIT

CODE

int sumArray(int arr[], int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum;
}

Print the Array

ALGORITHM

Step 1: [INITIALIZATION] SET I = lower_bound
Step 2: Repeat Steps 3 to 4 while I <= upper_bound
Step 3: Print A[I]
Step 4: SET I = I + 1
[END OF LOOP]
Step 5: EXIT

CODE

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Main Function

arrays.cpp

#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
 
int main()
{
    int arr[MAX_SIZE];
    int size = 0;
 
    cout << "Enter the initial size of the array (up to " << MAX_SIZE << "): ";
    cin >> size;
 
    cout << "Enter " << size << " elements: ";
    for (int i = 0; i < size; i++)
        cin >> arr[i];
 
    cout << "Array elements: ";
    printArray(arr, size);
 
    int elementToFind;
    cout << "Enter an element to find: ";
    cin >> elementToFind;
    int position = findElement(arr, size, elementToFind);
    if (position != -1)
        cout << "Element " << elementToFind << " found at position " << position << endl;
    else
        cout << "Element " << elementToFind << " not found in the array." << endl;
 
    int elementToInsert, insertPosition;
    cout << "Enter an element to insert: ";
    cin >> elementToInsert;
    cout << "Enter the position to insert: ";
    cin >> insertPosition;
    insertElement(arr, size, elementToInsert, insertPosition);
    cout << "Array elements after insertion: ";
    printArray(arr, size);
 
    int deletePosition;
    cout << "Enter the position to delete: ";
    cin >> deletePosition;
    deleteElement(arr, size, deletePosition);
    cout << "Array elements after deletion: ";
    printArray(arr, size);
 
    int max = findMax(arr, size);
    cout << "Maximum element: " << max << endl;
 
    int min = findMin(arr, size);
    cout << "Minimum element: " << min << endl;
 
    int sum = sumArray(arr, size);
    cout << "Sum of array elements: " << sum << endl;
 
    return 0;
}

Approach 2: Using Dynamic Vector

Insert an Element

CODE

void insertElement(vector<int>& vec, int element, int position) {
    if (position < 0 || position > vec.size()) {
        cout << "Invalid position. Cannot insert element." << endl;
        return;
    }
    vec.insert(vec.begin() + position, element);
}

Delete an Element

CODE

void deleteElement(vector<int>& vec, int position) {
    if (position < 0 || position >= vec.size()) {
        cout << "Invalid position. Cannot delete element." << endl;
        return;
    }
    vec.erase(vec.begin() + position);
}

Find an Element

CODE

int findElement(const vector<int>& vec, int element) {
    for (size_t i = 0; i < vec.size(); i++) {
        if (vec[i] == element) {
            return i;
        }
    }
    return -1; // Element not found
}

Find Minimum Element

CODE

int findMin(const vector<int>& vec) {
    int min = numeric_limits<int>::max();
    for (int num : vec) {
        if (num < min) {
            min = num;
        }
    }
    return min;
}

Find Maximum Element

CODE

int findMax(const vector<int>& vec) {
    int max = numeric_limits<int>::min();
    for (int num : vec) {
        if (num > max) {
            max = num;
        }
    }
    return max;
}

Find Sum of all Elements

CODE

int findSum(const vector<int>& vec) {
    int sum = 0;
    for (int num : vec) {
        sum += num;
    }
    return sum;
}

Print the Array

CODE

void printVector(const vector<int>& vec) {
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
}

Main Function

vectors.cpp

#include <iostream>
#include <vector>
#include <limits>
 
int main() {
    vector<int> vec;
 
    cout << "Enter the initial size of the vector: ";
    int size;
    cin >> size;
 
    cout << "Enter " << size << " elements: ";
    for (int i = 0; i < size; i++) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
 
    cout << "Vector elements: ";
    printVector(vec);
 
    int elementToFind;
    cout << "Enter an element to find: ";
    cin >> elementToFind;
    int position = findElement(vec, elementToFind);
    if (position != -1) {
        cout << "Element " << elementToFind << " found at position " << position << endl;
    } else {
        cout << "Element " << elementToFind << " not found in the vector." << endl;
    }
 
    int elementToInsert, insertPosition;
    cout << "Enter an element to insert: ";
    cin >> elementToInsert;
    cout << "Enter the position to insert: ";
    cin >> insertPosition;
    insertElement(vec, elementToInsert, insertPosition);
    cout << "Vector elements after insertion: ";
    printVector(vec);
 
    int deletePosition;
    cout << "Enter the position to delete: ";
    cin >> deletePosition;
    deleteElement(vec, deletePosition);
    cout << "Vector elements after deletion: ";
    printVector(vec);
 
    cout << "Minimum: " << findMin(vec) << endl;
    cout << "Maximum: " << findMax(vec) << endl;
    cout << "Sum: " << findSum(vec) << endl;
    return 0;
}

Python List Operations

Python lists are dynamic arrays, so operations are simpler and more Pythonic.

Insert an Element

def insert_element(arr, element, position):
    """Insert element at given position."""
    if position < 0 or position > len(arr):
        print("Invalid position.")
        return
    arr.insert(position, element)
 
# Example
arr = [10, 20, 30, 40, 50]
insert_element(arr, 25, 2)
print(arr)  # [10, 20, 25, 30, 40, 50]
 
# Even simpler: just use .insert() directly
arr.insert(0, 5)   # Insert at beginning
arr.append(60)     # Insert at end -- O(1) amortized

Delete an Element

def delete_element(arr, position):
    """Delete element at given position."""
    if position < 0 or position >= len(arr):
        print("Invalid position.")
        return
    arr.pop(position)
 
# Example
arr = [10, 20, 30, 40, 50]
delete_element(arr, 2)
print(arr)  # [10, 20, 40, 50]
 
# Other ways to delete
arr.remove(40)      # Remove first occurrence of value 40
del arr[0]          # Delete by index
last = arr.pop()    # Remove and return last element

Find an Element

def find_element(arr, element):
    """Return index of element, or -1 if not found."""
    for i in range(len(arr)):
        if arr[i] == element:
            return i
    return -1
 
# Pythonic way: use 'in' keyword and .index()
arr = [10, 20, 30, 40, 50]
if 30 in arr:
    idx = arr.index(30)  # 2
    print(f"Found at index {idx}")

Find Minimum and Maximum

def find_min(arr):
    """Find minimum element."""
    minimum = arr[0]
    for num in arr[1:]:
        if num < minimum:
            minimum = num
    return minimum
 
def find_max(arr):
    """Find maximum element."""
    maximum = arr[0]
    for num in arr[1:]:
        if num > maximum:
            maximum = num
    return maximum
 
# Pythonic way: use built-in functions
arr = [10, 20, 30, 40, 50]
print(min(arr))  # 10
print(max(arr))  # 50

Find Sum of All Elements

def find_sum(arr):
    """Calculate sum of all elements."""
    total = 0
    for num in arr:
        total += num
    return total
 
# Pythonic way: use built-in sum()
arr = [10, 20, 30, 40, 50]
print(sum(arr))  # 150

Print the Array

def print_array(arr):
    """Print all elements."""
    for element in arr:
        print(element, end=" ")
    print()
 
# Pythonic ways
arr = [10, 20, 30, 40, 50]
print(arr)                    # [10, 20, 30, 40, 50]
print(*arr)                   # 10 20 30 40 50
print(" ".join(map(str, arr)))  # 10 20 30 40 50

Complete Example

arrays.py

def main():
    arr = []
 
    size = int(input("Enter the initial size: "))
    print(f"Enter {size} elements: ", end="")
    arr = list(map(int, input().split()))
 
    print(f"Array elements: {arr}")
 
    element = int(input("Enter element to find: "))
    if element in arr:
        print(f"Found at index {arr.index(element)}")
    else:
        print("Not found")
 
    element = int(input("Enter element to insert: "))
    position = int(input("Enter position: "))
    arr.insert(position, element)
    print(f"After insertion: {arr}")
 
    position = int(input("Enter position to delete: "))
    arr.pop(position)
    print(f"After deletion: {arr}")
 
    print(f"Min: {min(arr)}")
    print(f"Max: {max(arr)}")
    print(f"Sum: {sum(arr)}")
 
if __name__ == "__main__":
    main()

Useful Python List Methods

Here’s a quick reference for the most commonly used list methods:

arr = [3, 1, 4, 1, 5, 9, 2, 6]
 
arr.sort()              # Sort in-place: [1, 1, 2, 3, 4, 5, 6, 9]
arr.sort(reverse=True)  # Descending: [9, 6, 5, 4, 3, 2, 1, 1]
sorted_arr = sorted(arr)  # Returns new sorted list
 
arr.reverse()           # Reverse in-place
arr[::-1]               # Returns reversed copy (slicing)
 
arr.count(1)            # Count occurrences of 1
len(arr)                # Length of array
 
# Slicing -- powerful and frequently tested
arr[1:4]    # Elements from index 1 to 3
arr[:3]     # First 3 elements
arr[-2:]    # Last 2 elements
arr[::2]    # Every other element

Rebuild the insert from memory

You saw the code above. Now recall the one line that does the real work. To insert at pos, you walk from the end backward, copying each element one slot right — fill in the shift:

python · fill in the blanks0/1 hints

def insert_at(arr, pos, x):
  arr.append(None)                      # grow by one slot
  for i in range(len(arr) - 1, pos, -1):
      # ??? the shift that opens a hole at pos
  arr[pos] = x                          # drop the new value into the hole
  return arr

Why walk backward (from the end toward pos)? If you copied front-to-back you’d overwrite values before moving them. Going right-to-left, each slot you write into has already been vacated. That’s the same shifting that makes the operation O(n).

Quick Check

What is the time complexity of inserting an element at the beginning of an array of size n?

You need a structure where you frequently insert/remove at the FRONT. Is a plain array a good fit?

This builds on memory representation — the contiguous layout is exactly what makes indexing O(1) and shifting O(n). Next: array algorithms, where these primitives combine into the techniques (two pointers, prefix sums, sliding window) the rest of the course leans on.

Declaration & Initialization Algorithms

Finished this page?