6 Arrays and Collections

The Array Model and Safe Indexing

An array stores an ordered sequence of elements under one variable name. Each element is accessed through an index. In many languages, arrays have a fixed length after creation and contain values of one declared type.

For an array of length $n$, valid indexes range from $0$ through $n-1$. For example, the values $[82, 95, 71, 88, 90]$ have length $5$, while the largest valid index is $4$. Length and the last valid index are therefore different quantities:

Reading an element uses its index. The value at index $0$ is the first element, and the value at index $2$ is the third element. Replacing the value at index $2$ changes that element but does not change the array's length. Direct indexed access is usually $O(1)$ because the program can calculate the element's location from its index.

A frequent mistake is confusing a human-readable position with a zero-based index. Position $1$ corresponds to index $0$, position $2$ to index $1$, and position $3$ to index $2$. Accessing an index below $0$ or at least as large as the array's length causes an error in many languages.

Takeaway: Track both the array's length and its zero-based index range, and remember that updating a value does not add or remove an element.

Traversals and One-Pass Algorithms

Traversal means visiting elements, usually from left to right. Use an indexed loop when the algorithm needs positions, updates, or comparisons with neighboring elements. Use a value-oriented loop when it only needs to process each value.

A traversal of an array with $n$ elements visits approximately $n$ elements, so its running time is $O(n)$. Adding $5$ to every value in $[82, 95, 75, 88, 90]$ produces $[87, 100, 80, 93, 95]$. The loop must stop at index $n-1$, not at index $n$.

Many one-pass algorithms maintain a small amount of state:

• A sum uses an accumulator that begins at $0$ and adds each value.

• An average divides the sum by the number of elements after deciding how an empty array should be handled.

• A minimum or maximum should begin with the first element rather than an arbitrary value such as $0$.

• A counter records how many values satisfy a condition, such as $\text{score} \ge 70$.

For example, the values $[72, 88, 61, 95]$ contain $3$ scores greater than or equal to $70$. For an empty array, an average may be reported as undefined or assigned a deliberate special result; dividing by zero should not happen accidentally.

Takeaway: Choose the loop form based on whether positions matter, and explicitly define the state and empty-input behavior before traversing.

Searching Ordered and Unordered Data

Searching asks whether a target exists and, often, which index contains it. A Linear search checks elements from left to right. It works on unsorted arrays: searching $[14, 7, 22, 9]$ for $22$ returns index $2$, while searching for $11$ can return $-1$ to indicate that no valid index was found. Its best-case time is $O(1)$, and its worst-case time is $O(n)$.

When duplicate values are possible, a search that stops at the first match is not enough to find every occurrence. Examining the complete array can return all matching indexes. For $[4, 2, 4, 7, 4]$, finding every occurrence of $4$ returns $[0, 2, 4]$.

A Binary search is appropriate only when the array is sorted according to the same ordering used by the search. The process is:

1. Establish lower and upper boundaries.

2. Examine the middle index.

3. Return the index if the middle value equals the target.

4. Search the left half if the target is smaller.

5. Search the right half if the target is larger.

6. Stop when the boundaries cross.

Each unsuccessful comparison discards about half of the remaining range, giving binary search a time complexity of $O(\log n)$. Sorting may make repeated searches faster, but sorting itself has a cost, so it is worthwhile only when the benefits of ordered data justify that cost.

Takeaway: Use linear search for general unsorted data; use binary search only after establishing the required sorted order.

Transformations, Duplicates, and Efficiency

Arrays support many useful transformations. To reverse an array in place, keep a left index at $0$ and a right index at $n-1$, swap the values at those indexes, and move both indexes toward the center. Reversing $[1, 2, 3, 4]$ produces $[4, 3, 2, 1]$. The algorithm takes $O(n)$ time and uses $O(1)$ extra space.

Duplicate detection illustrates a trade-off. Comparing every pair with nested loops can take $O(n^2)$ time. Alternatively, a set can record values already seen: if a value is already in the set, a duplicate has been found. This approach usually takes approximately $O(n)$ time but uses additional memory.

Sorting rearranges values into an order such as $[7, 2, 9, 4] \rightarrow [2, 4, 7, 9]$. Be careful with library behavior: some sorting operations modify the original array, while others return a separate sorted result. The algorithm must know which behavior applies before it relies on the original data remaining unchanged.

Time complexity is only one part of the analysis. Also track extra space, whether the original array is modified, and whether the input must already satisfy a condition such as sorted order.

Takeaway: Compare algorithms by both their running time and their memory use, and identify whether an operation mutates the original collection.

Choosing Between Arrays and Collections

A collection is a broader category than an array. Lists preserve order and usually support positional access, while sets emphasize membership and uniqueness, maps associate keys with values, and queues organize processing order. A Dynamic list is useful when elements are frequently added or removed or when the final size is unknown.

Choose an array when:

• The number of elements is known or changes rarely.

• Fast indexed access is important.

• Values have a consistent type.

• Predictable storage and performance are useful.

Choose a dynamic list or another collection when:

• The size must grow or shrink.

• Insertion and removal operations are central to the program.

• Built-in collection operations make the intended behavior clearer.

Lists often preserve indexed access, but inserting or removing an element in the middle may require later elements to shift. Before selecting a structure, clarify the input type, possible duplicates, empty-input rules, required output, and whether the original data may be modified.

A reliable problem-solving checklist is:

1. Identify the valid index range and boundary conditions.

2. Decide whether the result is a value, index, Boolean, new collection, or modification.

3. Select a single loop, nested loops, or two-pointer strategy.

4. Track counters, accumulators, best-so-far values, or previously seen values.

5. Test empty, one-element, duplicate, sorted, reverse-sorted, and missing-target cases.

6. Estimate running time and additional memory.

Takeaway: Match the data structure and algorithm to the operations the program performs most often, then test boundary cases deliberately.