Insight Vault

Array

3 min read

An array stores values in a sequence and lets the algorithm access a value by its position. In Python algorithm practice, list is the usual array-like structure.

Arrays are often the first structure used for sorting, searching, dynamic programming, prefix sums, and two-pointer techniques.

Core Idea

The key feature of an array is indexed access. If values is a Python list, values[i] reads the element at index i.

This makes arrays good when the algorithm needs to move through positions, compare neighbors, or store one answer per index.

An array gives the algorithm a stable order. That order may be the original input order, a sorted order, or an order created by the algorithm. Many techniques are really ways of exploiting that order.

Common array operations have different costs in Python:

  • Reading or writing by index is O(1).
  • Appending at the end is O(1) amortized.
  • Searching by scanning is O(n).
  • Inserting or deleting near the front is O(n) because elements shift.

Usage Contract

An array-like Python list is appropriate when positions matter and index access is needed. The input is usually a list such as values = [4, 7, 1], and indexes run from 0 to len(values) - 1.

Reading or writing values[i] assumes i is inside that range. If the algorithm repeatedly inserts or deletes near the front, a Python list may be the wrong structure because many elements must shift.

Python Example

values = [10, 20, 30, 40]
 
first = values[0]
last = values[-1]
values[2] = 35

The list keeps the elements in order. Access by index is constant time.

Traversing by Value and by Index

Use direct iteration when only values matter:

for value in values:
    print(value)

Use indexes when positions matter:

for i in range(len(values)):
    if i > 0:
        print(values[i - 1], values[i])

Many array algorithms need indexes because they compare neighbors, store answers by position, or move pointers.

Typical Patterns

Arrays are the base structure for several important patterns:

  • Prefix sums store cumulative information by index.
  • Two pointers move through positions under a rule.
  • Sliding windows maintain a contiguous range.
  • Dynamic programming often stores one answer per index.
  • Sorting rearranges the array to expose order.

The same Python list can support all of these ideas. The algorithmic meaning comes from how the code uses the positions.

Common Confusions

Python list is dynamic. It can grow and shrink, unlike a fixed-size array in lower-level languages. For most algorithm problems, it still plays the role of an array.

Another common mistake is confusing index and value. The index is the position. The value is what is stored at that position.

Slicing creates a new list:

middle = values[1:3]

That may be convenient, but it uses extra time and memory proportional to the slice length.

When To Use It

Use an array-like list when order matters, when positions matter, or when the algorithm needs efficient access to i, i - 1, or i + 1.

If the algorithm mostly needs membership checks and order does not matter, a set may be better. If it needs key-value lookup, a dictionary may be better.

The Main Point

An array is best when indexed position matters. It gives fast access by index, but inserting or deleting in the middle can be expensive because elements shift.

Backlinks

Graph

Depth 1