3. Arrays

Introduction

Arrays are the simplest and most widely used data structure in computer science. They store a fixed‑size sequence of elements of the same type in contiguous memory locations, enabling constant‑time access to any element via its index. This chapter covers how arrays are laid out in memory, their strengths and weaknesses, essential operations, powerful algorithmic tricks built on top of arrays, and practical projects that reinforce the concepts.

Memory Representation

When an array arr of n elements is allocated, the compiler reserves a single block of memory large enough to hold all elements. The address of the i‑th element is computed as:

address(arr[i]) = base_address + i × element_size

where base_address is the starting address of the array and element_size is the size (in bytes) of each element (e.g., 4 bytes for a 32‑bit integer). Because elements are stored sequentially, the CPU can fetch arr[i] with a single memory access, giving O(1) random‑access time.

Advantages

• Cache‑friendly: Spatial locality means consecutive elements are likely to be loaded together into CPU cache.
• Simple indexing: Direct arithmetic yields the location of any element.
• Low overhead: No extra pointers or metadata are required per element.
• Predictable performance: Access time is constant and independent of array size.

Limitations

• Fixed size: The length must be known at compile time (or allocation time); resizing requires allocating a new array and copying elements.
• Insertion/deletion cost: Adding or removing an element at position k shifts all subsequent elements, costing O(n‑k).
• Potential waste: If the array is not fully utilized, allocated memory remains unused.
• Homogeneous elements: All items must share the same data type.

Real‑Life Examples

• Scoreboard in a video game – each slot holds a player’s score.
• Pixel values in a raster image – a 2D array of color intensities.
• Coefficients of a polynomial – a₀ + a₁x + a₂x² + … stored as [a₀, a₁, a₂, …].
• Lookup tables for trigonometric functions – pre‑computed sine/cosine values.

Applications of Arrays

• Building other data structures: heaps, hash tables (as backing storage), stacks, queues.
• Implementing lookup tables for fast retrieval (e.g., ASCII to binary).
• Serving as buffers for streaming data (network packets, audio samples).
• Underlying storage for dynamic arrays (e.g., std::vector in C++).

Core Array Operations

Traversal

Visiting each element once:

for (int i = 0; i < n; ++i) { process(arr[i]); }

Time complexity: O(n). Auxiliary space: O(1).

Insertion

• At the end (if space available): Direct assignment arr[n] = value → O(1).
• At index k: Shift elements arr[k … n‑1] one position right, then assign arr[k] = value. Cost: O(n‑k).

Deletion

To remove the element at index k:

for (int i = k; i < n‑1; ++i) arr[i] = arr[i+1]; n--;

Elements arr[k+1 … n‑1] shift left. Time: O(n‑k).

Searching

• Linear scan: Check each element until match → O(n).
• Binary search (requires sorted array): Repeatedly halve the search interval → O(log n).

Updating

Direct assignment:

arr[k] = new_value;

Time: O(1).

Advanced Array Techniques

Prefix Sum (Cumulative Sum)

The prefix sum array prefix stores the sum of elements from the start up to each index:

prefix[i] = Σ_{j=0}^{i} arr[j]

With this, any range sum sum(l, r) (inclusive) can be answered in constant time:

sum(l, r) = prefix[r] - (l>0 ? prefix[l-1] : 0)

Example: arr = [3, 1, 4, 1, 5] → prefix = [3, 4, 8, 9, 14]. To get sum of indices 1‑3: prefix[3] - prefix[0] = 9 - 3 = 6.

Sliding Window

Maintains the aggregate (e.g., sum) of a fixed‑size window while it moves across the array. When the window slides one step right:

window_sum = window_sum - arr[left] + arr[right+1];

This yields O(n) time for problems like “maximum sum subarray of size w”.

Two‑Pointer Technique

Two indices (i starting at the beginning, j at the end) move toward each other based on a condition.

• Pair sum: In a sorted array, increase i if sum too small, decrease j if sum too large.
• Palindrome check: Compare arr[i] and arr[j]; move inward.
• Container with most water: Move the pointer pointing to the shorter line inward.

Each pointer moves at most n steps → overall O(n) time.

Kadane’s Algorithm (Maximum Subarray Sum)

Finds the contiguous subarray with the largest sum in linear time.

max_ending_here = max(arr[i], max_ending_here + arr[i]);
max_so_far = max(max_so_far, max_ending_here);

Initialize both variables to arr[0]. After processing all elements, max_so_far holds the answer.

Example: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → maximum subarray sum = 6 (subarray [4, -1, 2, 1]).

Difference Array

Facilitates efficient range updates. The difference array diff is defined as:

diff[0] = arr[0];
diff[i] = arr[i] - arr[i-1] (for i > 0)

To add value v to every element in range [l, r]:

diff[l] += v;
if (r+1 < n) diff[r+1] -= v;

Reconstruct the updated array by taking the prefix sum of diff.

Example: Starting arr = [0,0,0,0,0], update [1,3] with +5:

• diff = [0,0,0,0,0] → after update diff[1]+=5, diff[4]-=5 → diff = [0,5,0,0,-5].
• Prefix sum of diff yields arr = [0,5,5,5,0].

Practical Projects

Student Result System

Store each student’s marks for multiple subjects in a two‑dimensional array marks[students][subjects]. Operations include:

• Compute total marks per student: sum across the subject dimension.
• Calculate average and assign grades based on predefined thresholds.
• Generate a grade‑distribution histogram using a frequency array.

Prefix sums can accelerate queries like “total marks of students 10‑20 in subject 3”.

Expense Tracker

Maintain a monthly array expenses[30] (or variable length) where each entry is the daily expenditure. Using a sliding window of size 7, compute weekly totals efficiently:

weekly_sum = sum of expenses[0..6];
for (day = 7; day < 30; ++day) {
  weekly_sum = weekly_sum - expenses[day-7] + expenses[day];
  record weekly_sum;
}

This yields O(n) time for all weekly sums.

Attendance System

For each student, keep a Boolean array present[days] where true indicates attendance. A prefix sum over this array gives the number of days present up to any date:

present_prefix[i] = present_prefix[i-1] + (present[i] ? 1 : 0);

To answer “How many days was student X present between day l and day r?” compute present_prefix[r] - present_prefix[l-1] in O(1) time.

Summary

Arrays provide a foundation for efficient data storage and retrieval. Understanding their memory layout enables developers to leverage cache performance, while mastering traversal, insertion, deletion, search, and update operations forms the basis of algorithmic problem‑solving. Advanced techniques such as prefix sums, sliding windows, two‑pointer scans, Kadane’s algorithm, and difference arrays extend the utility of arrays to solve range queries, subarray optimizations, and dynamic updates in linear time. The presented projects illustrate how these concepts translate into real‑world applications, reinforcing both theoretical knowledge and practical implementation skills.