Arrays and Basic Operations

Chapter 2: Arrays and Basic Operations

Introduction

Arrays are the most fundamental data structure in programming. They store collections of elements in contiguous memory locations, providing fast access by index. Understanding arrays deeply—how they're laid out in memory, their performance characteristics, and common operations—forms the foundation for all other data structures.

Why This Matters

Arrays appear everywhere in programming:

  • Storing lists of data (students, products, scores)
  • Implementing other data structures (stacks, queues, hash tables)
  • Processing images (2D arrays of pixels)
  • Building matrices for scientific computing
  • Managing buffers in system programming

Mastering array operations and their complexity is essential because:

  • They're the building block for most algorithms
  • Understanding memory layout helps you write cache-friendly code
  • Many interview questions test array manipulation skills
  • Performance differences between operations can be huge

How to Study This Chapter

  1. Visualize memory layout - Draw arrays as boxes in memory
  2. Trace operations step by step - Follow pointer arithmetic
  3. Implement in all three languages - See language differences
  4. Measure performance - Time operations with different array sizes
  5. Practice variations - Modify examples to solve related problems

What is an Array?

An array is a collection of elements of the same type stored in contiguous memory locations. Each element can be accessed directly using an index.

Memory Layout

Array: [10, 20, 30, 40, 50]

Memory visualization:
Index:     0    1    2    3    4
         +----+----+----+----+----+
Value:   | 10 | 20 | 30 | 40 | 50 |
         +----+----+----+----+----+
Address: 1000 1004 1008 1012 1016  (assuming 4-byte integers)

Key Properties:

  • Elements stored consecutively in memory
  • Constant-time access: arr[i] is instant
  • Fixed size in C (dynamic in C++ vector, Java ArrayList)
  • Index starts at 0 in C, C++, Java

Array Access Formula

element_address = base_address + (index × element_size)

Example: arr[3] in an int array starting at 1000:

address = 1000 + (3 × 4) = 1012

This is why array access is O(1)—it's a simple calculation.

Creating Arrays

C - Static Arrays

#include <stdio.h>

int main() {
    // Declaration and initialization
    int arr[5] = {10, 20, 30, 40, 50};

    // Partial initialization (rest are 0)
    int arr2[5] = {1, 2};  // {1, 2, 0, 0, 0}

    // Let compiler determine size
    int arr3[] = {5, 10, 15, 20};  // Size is 4

    // Print array
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

C - Dynamic Arrays

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 5;

    // Allocate array dynamically
    int *arr = (int*)malloc(n * sizeof(int));

    if (arr == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }

    // Initialize
    for (int i = 0; i < n; i++) {
        arr[i] = i * 10;
    }

    // Print
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Free memory
    free(arr);

    return 0;
}

C++ - Static and Dynamic Arrays

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Static array (C-style)
    int arr1[5] = {10, 20, 30, 40, 50};

    // Dynamic array using vector (recommended)
    vector<int> arr2 = {10, 20, 30, 40, 50};

    // Vector with size and default value
    vector<int> arr3(5, 0);  // 5 elements, all 0

    // Add elements dynamically
    vector<int> arr4;
    arr4.push_back(10);
    arr4.push_back(20);
    arr4.push_back(30);

    // Print using range-based for loop
    for (int val : arr2) {
        cout << val << " ";
    }
    cout << endl;

    // Print with index
    for (size_t i = 0; i < arr2.size(); i++) {
        cout << arr2[i] << " ";
    }
    cout << endl;

    return 0;
}

Java - Arrays and ArrayList

import java.util.ArrayList;
import java.util.Arrays;

public class ArrayDemo {
    public static void main(String[] args) {
        // Static array
        int[] arr1 = {10, 20, 30, 40, 50};

        // Array with specified size
        int[] arr2 = new int[5];
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = i * 10;
        }

        // ArrayList (dynamic)
        ArrayList<Integer> arr3 = new ArrayList<>();
        arr3.add(10);
        arr3.add(20);
        arr3.add(30);

        // Print array
        System.out.println(Arrays.toString(arr1));

        // Print ArrayList
        System.out.println(arr3);

        // Enhanced for loop
        for (int val : arr1) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

Basic Array Operations

1. Traversal - O(n)

Visit every element once.

C Example:

#include <stdio.h>

void traverseArray(int arr[], int size) {
    printf("Array elements: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {5, 10, 15, 20, 25};
    traverseArray(arr, 5);
    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
using namespace std;

void traverseArray(const vector<int>& arr) {
    cout << "Array elements: ";
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {5, 10, 15, 20, 25};
    traverseArray(arr);
    return 0;
}

Java Example:

public class Traversal {
    public static void traverseArray(int[] arr) {
        System.out.print("Array elements: ");
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 10, 15, 20, 25};
        traverseArray(arr);
    }
}

Complexity: O(n) time, O(1) space

2. Access by Index - O(1)

Directly access any element.

C Example:

int getElement(int arr[], int index) {
    return arr[index];
}

void setElement(int arr[], int index, int value) {
    arr[index] = value;
}

C++ Example:

int getElement(const vector<int>& arr, int index) {
    return arr[index];  // or arr.at(index) for bounds checking
}

void setElement(vector<int>& arr, int index, int value) {
    arr[index] = value;
}

Java Example:

public static int getElement(int[] arr, int index) {
    return arr[index];
}

public static void setElement(int[] arr, int index, int value) {
    arr[index] = value;
}

Complexity: O(1) time, O(1) space

3. Search - O(n) for unsorted, O(log n) for sorted

Linear Search (Unsorted Array):

C Example:

#include <stdio.h>

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // Found at index i
        }
    }
    return -1;  // Not found
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int target = 12;
    int result = linearSearch(arr, 5, target);

    if (result != -1) {
        printf("Found at index %d\n", result);
    } else {
        printf("Not found\n");
    }

    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int linearSearch(const vector<int>& arr, int target) {
    for (size_t i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    int result = linearSearch(arr, 12);

    if (result != -1) {
        cout << "Found at index " << result << endl;
    } else {
        cout << "Not found" << endl;
    }

    return 0;
}

Java Example:

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        int result = linearSearch(arr, 12);

        if (result != -1) {
            System.out.println("Found at index " + result);
        } else {
            System.out.println("Not found");
        }
    }
}

Complexity: O(n) time, O(1) space

4. Insertion

At the End - O(1) for dynamic arrays with capacity

C Example (Dynamic Array):

#include <stdio.h>
#include <stdlib.h>

int* insertAtEnd(int *arr, int *size, int *capacity, int value) {
    if (*size == *capacity) {
        // Resize array
        *capacity *= 2;
        arr = (int*)realloc(arr, (*capacity) * sizeof(int));
    }
    arr[*size] = value;
    (*size)++;
    return arr;
}

int main() {
    int capacity = 4;
    int size = 3;
    int *arr = (int*)malloc(capacity * sizeof(int));
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;

    arr = insertAtEnd(arr, &size, &capacity, 40);
    arr = insertAtEnd(arr, &size, &capacity, 50);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    free(arr);
    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {10, 20, 30};

    arr.push_back(40);  // O(1) amortized
    arr.push_back(50);

    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Java Example:

import java.util.ArrayList;

public class InsertAtEnd {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(10);
        arr.add(20);
        arr.add(30);
        arr.add(40);  // O(1) amortized

        System.out.println(arr);
    }
}

At the Beginning - O(n) - Must shift all elements

C Example:

#include <stdio.h>

void insertAtBeginning(int arr[], int *size, int value) {
    // Shift all elements to the right
    for (int i = *size; i > 0; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = value;
    (*size)++;
}

int main() {
    int arr[10] = {20, 30, 40};
    int size = 3;

    insertAtBeginning(arr, &size, 10);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  // Output: 10 20 30 40

    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {20, 30, 40};

    arr.insert(arr.begin(), 10);  // O(n)

    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;  // Output: 10 20 30 40

    return 0;
}

Java Example:

import java.util.ArrayList;

public class InsertAtBeginning {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(20);
        arr.add(30);
        arr.add(40);

        arr.add(0, 10);  // O(n)

        System.out.println(arr);  // [10, 20, 30, 40]
    }
}

Complexity: O(n) time, O(1) space

At Specific Position - O(n)

C Example:

#include <stdio.h>

void insertAtPosition(int arr[], int *size, int pos, int value) {
    // Shift elements from pos to end
    for (int i = *size; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = value;
    (*size)++;
}

int main() {
    int arr[10] = {10, 20, 40, 50};
    int size = 4;

    insertAtPosition(arr, &size, 2, 30);  // Insert 30 at index 2

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  // Output: 10 20 30 40 50

    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {10, 20, 40, 50};

    arr.insert(arr.begin() + 2, 30);  // Insert at index 2

    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;  // Output: 10 20 30 40 50

    return 0;
}

Java Example:

import java.util.ArrayList;

public class InsertAtPosition {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(10);
        arr.add(20);
        arr.add(40);
        arr.add(50);

        arr.add(2, 30);  // Insert at index 2

        System.out.println(arr);  // [10, 20, 30, 40, 50]
    }
}

Complexity: O(n) time, O(1) space

5. Deletion

Delete from End - O(1)

C Example:

void deleteFromEnd(int arr[], int *size) {
    if (*size > 0) {
        (*size)--;
    }
}

C++ Example:

vector<int> arr = {10, 20, 30};
arr.pop_back();  // O(1)

Java Example:

ArrayList<Integer> arr = new ArrayList<>();
arr.remove(arr.size() - 1);  // O(1)

Delete from Beginning - O(n)

C Example:

#include <stdio.h>

void deleteFromBeginning(int arr[], int *size) {
    if (*size > 0) {
        for (int i = 0; i < *size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        (*size)--;
    }
}

int main() {
    int arr[] = {10, 20, 30, 40};
    int size = 4;

    deleteFromBeginning(arr, &size);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  // Output: 20 30 40

    return 0;
}

C++ Example:

vector<int> arr = {10, 20, 30, 40};
arr.erase(arr.begin());  // O(n)

Java Example:

ArrayList<Integer> arr = new ArrayList<>();
arr.remove(0);  // O(n)

Complexity: O(n) time

Delete at Position - O(n)

C Example:

void deleteAtPosition(int arr[], int *size, int pos) {
    if (pos >= 0 && pos < *size) {
        for (int i = pos; i < *size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        (*size)--;
    }
}

6. Reverse Array - O(n)

C Example:

#include <stdio.h>

void reverseArray(int arr[], int size) {
    int left = 0;
    int right = size - 1;

    while (left < right) {
        // Swap
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        left++;
        right--;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = 5;

    reverseArray(arr, size);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  // Output: 5 4 3 2 1

    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};

    reverse(arr.begin(), arr.end());  // STL function

    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;  // Output: 5 4 3 2 1

    return 0;
}

Java Example:

import java.util.Collections;
import java.util.ArrayList;
import java.util.Arrays;

public class ReverseArray {
    public static void reverseArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        reverseArray(arr);
        System.out.println(Arrays.toString(arr));  // [5, 4, 3, 2, 1]
    }
}

Complexity: O(n) time, O(1) space

7. Find Maximum/Minimum - O(n)

C Example:

#include <stdio.h>

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;
}

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;
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    printf("Max: %d\n", findMax(arr, 6));
    printf("Min: %d\n", findMin(arr, 6));
    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {12, 35, 1, 10, 34, 1};

    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());

    cout << "Max: " << maxVal << endl;
    cout << "Min: " << minVal << endl;

    return 0;
}

Java Example:

import java.util.Arrays;

public class FindMinMax {
    public static void main(String[] args) {
        int[] arr = {12, 35, 1, 10, 34, 1};

        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();

        System.out.println("Max: " + max);
        System.out.println("Min: " + min);
    }
}

Multi-Dimensional Arrays

2D Arrays (Matrices)

C Example:

#include <stdio.h>

int main() {
    int matrix[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };

    // Print matrix
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%3d ", matrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

C++ Example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };

    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Java Example:

public class Matrix {
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}
        };

        for (int[] row : matrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}

Memory Layout of 2D Arrays

In C (row-major order):

int matrix[2][3] = {{1,2,3}, {4,5,6}};

Memory: [1][2][3][4][5][6]
        └─ row 0 ─┘└─ row 1 ─┘

Common Array Patterns

Two Pointers Technique

Remove Duplicates from Sorted Array:

#include <stdio.h>

int removeDuplicates(int arr[], int size) {
    if (size == 0) return 0;

    int writeIndex = 1;

    for (int i = 1; i < size; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[writeIndex] = arr[i];
            writeIndex++;
        }
    }

    return writeIndex;  // New size
}

int main() {
    int arr[] = {1, 1, 2, 2, 3, 4, 4, 5};
    int size = 8;

    int newSize = removeDuplicates(arr, size);

    for (int i = 0; i < newSize; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  // Output: 1 2 3 4 5

    return 0;
}

Sliding Window

Find Maximum Sum Subarray of Size K:

#include <stdio.h>

int maxSumSubarray(int arr[], int size, int k) {
    if (size < k) return -1;

    // Compute sum of first window
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    // Slide window
    for (int i = k; i < size; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }

    return maxSum;
}

int main() {
    int arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20};
    int k = 4;
    printf("Max sum: %d\n", maxSumSubarray(arr, 9, k));
    return 0;
}

Complexity Summary

OperationTime ComplexitySpace Complexity
Access by indexO(1)O(1)
Search (unsorted)O(n)O(1)
Search (sorted)O(log n)O(1)
Insert at endO(1) amortizedO(1)
Insert at beginningO(n)O(1)
Insert at positionO(n)O(1)
Delete from endO(1)O(1)
Delete from beginningO(n)O(1)
Delete from positionO(n)O(1)
TraverseO(n)O(1)
ReverseO(n)O(1)
Find min/maxO(n)O(1)

Common Mistakes

  1. Off-by-one errors - Accessing arr[size] instead of arr[size-1]
  2. Buffer overflow - Writing beyond array bounds in C
  3. Not checking bounds - Causes crashes or security vulnerabilities
  4. Memory leaks in C - Forgetting to free() dynamic arrays
  5. Inefficient insertion/deletion - Not realizing O(n) cost
  6. Wrong initial value - Starting max search with 0 instead of arr[0]
  7. Integer overflow - Sum of large numbers exceeds int range
  8. Modifying array during iteration - Can skip elements

Debugging Tips

  1. Print arrays - Visualize state at each step
  2. Check bounds - Verify index is within [0, size-1]
  3. Use debuggers - Step through with gdb, Visual Studio, IntelliJ
  4. Test edge cases - Empty array, single element, all same values
  5. Valgrind for C - Detect memory errors
  6. AddressSanitizer - Compiler flag for memory safety
  7. Draw diagrams - Sketch array state on paper
  8. Start simple - Test with small arrays first

Mini Exercises

  1. Write a function to find the second largest element in an array
  2. Rotate an array to the right by k positions
  3. Check if an array is sorted
  4. Merge two sorted arrays into one sorted array
  5. Find all pairs that sum to a target value
  6. Remove all occurrences of a value from an array
  7. Move all zeros to the end while maintaining order
  8. Find the missing number in an array of 1 to n
  9. Implement array rotation using reversal algorithm
  10. Find the intersection of two arrays

Review Questions

  1. Why is array access O(1)? Explain the formula.
  2. What's the difference between static and dynamic arrays?
  3. Why is inserting at the beginning of an array O(n)?
  4. How does memory layout affect cache performance?
  5. When should you use an array vs. a linked list?

Reference Checklist

By the end of this chapter, you should be able to:

  • Create arrays in C, C++, and Java
  • Understand array memory layout
  • Implement traversal, search, insert, delete operations
  • Analyze time and space complexity of array operations
  • Use two-pointer and sliding window techniques
  • Work with multi-dimensional arrays
  • Recognize common array pitfalls
  • Choose appropriate array type for the problem

Next Steps

Now that you understand arrays and basic operations, Chapter 3 explores searching algorithms in depth. You'll learn linear search, binary search, interpolation search, and when to use each approach for maximum efficiency.

Key Takeaway: Arrays are simple but powerful. Their contiguous memory layout enables O(1) access but makes insertion/deletion expensive. Understanding these tradeoffs is crucial for choosing the right data structure for your problem.

PreviousNext Chapter