Arrays, Dynamic Arrays, Strings, and Matrices

Introduction

Arrays are among the most important data structures in programming. They store elements in an indexed sequence and provide a foundation for lists, strings, tables, images, numerical computation, and many algorithms. Java and Python both provide array-like structures, but their design philosophies differ. Java offers fixed-length arrays and the resizable ArrayList class, while Python’s built-in list is a dynamic array implemented in a highly optimized runtime.

This chapter develops the practical and analytical skills required to select, implement, and use these structures. Particular attention is given to indexing cost, memory locality, resizing, strings, multidimensional arrays, sparse matrices, prefix sums, sliding windows, and two-pointer techniques.

Learning Objectives

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

• explain the representation and performance characteristics of arrays;
• create and manipulate Java arrays, Java ArrayList objects, and Python lists;
• distinguish fixed-size arrays from dynamic arrays;
• analyse indexing, insertion, deletion, traversal, and resizing costs;
• process strings using common algorithms and language facilities;
• represent and traverse multidimensional and sparse matrices;
• apply prefix sums, sliding windows, and two-pointer techniques;
• choose an appropriate representation for a practical programming problem.

1. The Array Abstraction

An array is an ordered collection of elements whose positions are identified by integer indices. In most programming languages, indexing begins at zero. If an array contains n elements, its valid indices are 0 through n − 1.

For a one-dimensional array A, the element at index i is written as A[i]. A conventional array stores elements in adjacent memory locations. If each element occupies s bytes and the first element begins at address b, the address of A[i] is:

Here, i must satisfy 0 ≤ i < n; s is constant for a fixed element type; and the formula assumes a contiguous representation. Because the address can be calculated directly, indexing takes constant time, written O(1).

1.1 Core operations

The notation O(n) describes an upper-bound growth rate as input size n increases. It does not mean that every operation takes exactly n steps.

1.2 Locality and cache behaviour

Contiguous arrays have strong spatial locality: when one element is accessed, nearby elements are likely to be loaded into the processor cache. Sequential traversal is therefore often faster than traversing a collection of scattered objects, even when both operations have the same asymptotic complexity.

Locality matters in numerical algorithms, image processing, database systems, and machine learning. A program that repeatedly scans an array in memory order will usually perform better than one that jumps unpredictably between locations. This is a practical performance consideration, not a replacement for complexity analysis.

2. Java Arrays

Java arrays have a fixed length established when the array is created. They store values of a declared type and perform bounds checking at runtime.

int[] scores = new int[5];
scores[0] = 72;
scores[1] = 85;

for (int score : scores) {
    System.out.println(score);
}

An array can also be initialized directly:

int[] values = {4, 8, 15, 16, 23, 42};
System.out.println(values.length);

The length field is fixed and is not a method. Accessing values[values.length] is invalid because the final valid index is values.length - 1.

Java arrays of primitive types, such as int[], store primitive values directly. Arrays of reference types, such as String[], store references to objects. This distinction affects memory usage and locality.

Example: finding a maximum

public static int maximum(int[] data) {
    if (data.length == 0) {
        throw new IllegalArgumentException("Array must not be empty");
    }

    int best = data[0];
    for (int i = 1; i < data.length; i++) {
        if (data[i] > best) {
            best = data[i];
        }
    }
    return best;
}

The algorithm visits each element once, so its time complexity is O(n) and its additional space complexity is O(1). The empty-array condition must be handled because no maximum exists for an empty collection under this method’s definition.

3. Dynamic Arrays: Java ArrayList and Python list

A dynamic array maintains a logical sequence while using an internal array whose capacity may exceed the current number of elements. When the internal array becomes full, a larger array is allocated and elements are copied.

3.1 Java ArrayList

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<>();
names.add("Amina");
names.add("Jon");
names.add(1, "Mei");
String first = names.get(0);
names.set(0, "Amira");
names.remove(1);

ArrayList uses object references and therefore cannot directly store primitive types. Wrapper classes are used instead, for example ArrayList<Integer>. Java automatically performs boxing and unboxing in many expressions, but this may create objects and incur overhead.

Important methods include:

• add(x) — append an element;
• add(index, x) — insert and shift later elements;
• get(index) — retrieve an element;
• set(index, x) — replace an element;
• remove(index) — delete and shift later elements;
• size() — return the logical number of elements;
• contains(x) — perform a linear search.

Appending is amortized O(1). A single append can be O(n) when resizing occurs, but over a long sequence of appends the average cost per append is constant, assuming capacity grows geometrically.

3.2 Python lists

Python’s list is a dynamic array.

values = [4, 8, 15]
values.append(16)
values.insert(1, 99)
first = values[0]
values[2] = 100
removed = values.pop()

Common operations have the following typical costs:

Python lists store references to objects. Consequently, a list of integers does not have precisely the same memory representation as a low-level contiguous array of machine integers. For large numerical data, libraries such as NumPy provide specialized homogeneous arrays, although such libraries are outside the core language.

3.3 Resizing and amortized analysis

Suppose a dynamic array has capacity c and grows to approximately g × c, where g > 1, whenever it becomes full. A resize copies the existing elements. Although copying costs O(n) for that particular operation, geometric growth ensures that resizing does not occur on every append.

For n appends starting from an empty structure, the total number of copied elements is proportional to n, so the total work is O(n). The amortized cost per append is therefore O(1). This analysis assumes geometric growth and does not include unusual allocator or memory-pressure effects.

A programmer can often improve performance by reserving an appropriate initial capacity when the approximate data size is known:

ArrayList<Integer> readings = new ArrayList<>(10_000);

Capacity and logical size are different. Capacity describes allocated storage; size describes the number of elements currently present.

4. Strings and Text Processing

A string is a sequence of characters or, more precisely in modern software, a sequence of encoded code units representing text. Text processing requires care because a visible character may occupy multiple code units in encodings such as UTF-8 or UTF-16.

Java strings

Java String objects are immutable. Operations such as concatenation conceptually create a new string.

String language = "Java";
String message = language + " is widely used.";
int length = message.length();
char ch = message.charAt(0);
String part = message.substring(0, 4);

For repeated construction, use StringBuilder:

StringBuilder builder = new StringBuilder();
for (int i = 1; i <= 5; i++) {
    builder.append(i).append(' ');
}
String result = builder.toString();

Comparing strings should normally use .equals(), not ==. The latter compares references rather than textual contents.

Python strings

Python strings are immutable sequences.

text = "data structures"
print(text[0])
print(text[0:4])
words = text.split()
result = "-".join(words)

Repeated concatenation in a loop can create unnecessary intermediate strings. Building a list of pieces and using join is often clearer and more efficient:

pieces = []
for number in range(1, 6):
    pieces.append(str(number))
result = " ".join(pieces)

String algorithms

A naive substring search checks a pattern at each possible starting position. If the text has length n and the pattern has length m, its worst-case time can be O(nm). More advanced algorithms, such as Knuth–Morris–Pratt, preprocess the pattern and achieve O(n + m) time under their standard model.

A palindrome test compares symmetric positions. It takes O(n) time and O(1) extra space when performed with two indices rather than constructing a reversed copy.

def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1
    return True

The definition of “palindrome” must be specified in real applications: case sensitivity, spaces, punctuation, accents, and Unicode normalization can all affect the result.

5. Multidimensional Arrays and Matrices

A matrix is a rectangular arrangement of values with rows and columns. An r × c matrix contains r rows and c columns, hence r × c positions.

Java rectangular arrays

int[][] matrix = new int[3][4];
matrix[1][2] = 7;

for (int row = 0; row < matrix.length; row++) {
    for (int column = 0; column < matrix[row].length; column++) {
        System.out.print(matrix[row][column] + " ");
    }
    System.out.println();
}

Java’s two-dimensional arrays are arrays of arrays. Rows may therefore have different lengths:

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

This flexibility is useful but means that matrix[row].length, not always one global column count, should be used for safe traversal.

Python nested lists

matrix = [[0 for _ in range(4)] for _ in range(3)]
matrix[1][2] = 7

The nested-list construction above is safe. The expression [[0] 4] 3 creates three references to the same inner list, so changing one row changes all rows.

Matrix traversal takes O(rc) time because every one of the r × c entries is visited. A conventional matrix requires O(rc) storage, excluding object overhead.

Matrix multiplication

For matrices A of dimension r × k and B of dimension k × c, the product C = AB has dimension r × c and is defined by:

The standard algorithm performs r × c × k multiplications and additions, giving time complexity O(rck). Matrix multiplication is defined only when the number of columns in A equals the number of rows in B.

6. Sparse Matrices

A sparse matrix contains mostly zero or default values. Storing every position wastes memory when only a small number of entries are nonzero. A coordinate representation stores triples such as (row, column, value).

For example, the matrix

0 0 5
0 0 0
7 0 0

can be represented as:

(0, 2, 5)
(2, 0, 7)

A dictionary representation is convenient in Python:

sparse = {(0, 2): 5, (2, 0): 7}
value = sparse.get((1, 1), 0)

A Java implementation might use a map from a coordinate object to a numeric value. Sparse representations save space when the number of stored entries k is much smaller than r × c. However, direct access, iteration order, arithmetic, and memory overhead must be considered. A sparse representation is not automatically faster: if most entries are nonzero, a dense array is usually simpler and more efficient.

7. Prefix Sums

A prefix sum array supports efficient range-sum queries. Given values a[0] through a[n − 1], define p[0] = 0 and:

The sum from index l through r, inclusive, is:

The indices must satisfy 0 ≤ l ≤ r < n. Construction takes O(n) time and each range query takes O(1) time, at the cost of O(n) additional storage.

Worked example

For a = [3, 1, 4, 2], the prefix array is p = [0, 3, 4, 8, 10]. The sum from index 1 to 3 is:

p[4] − p[1] = 10 − 3 = 7

The method is particularly useful when many static range queries are required. If values change frequently, a simple prefix array must be rebuilt; other structures, such as a Fenwick tree, may then be more suitable.

A two-dimensional prefix sum extends the same principle to rectangular regions. If P[i][j] stores the sum of the rectangle from the origin to, but excluding, row i and column j, then:

The subtraction prevents the upper-left region from being counted twice.

8. Sliding Windows

A sliding window maintains a contiguous interval while moving through a sequence. It avoids recomputing information that overlaps between consecutive intervals.

For a fixed window length k, the sum of the first window is calculated once. Each subsequent window subtracts the element leaving and adds the element entering:

This produces O(n) time rather than O(nk) for recalculating every window independently.

def maximum_window_sum(values, k):
    if k <= 0 or k > len(values):
        raise ValueError("Invalid window size")

    current = sum(values[:k])
    best = current
    for right in range(k, len(values)):
        current += values[right] - values[right - k]
        best = max(best, current)
    return best

For variable-size windows, two boundaries move according to a condition. For example, when all values are nonnegative, the smallest subarray with sum at least target can be found in linear time by expanding the right boundary and shrinking the left boundary while the condition remains true. The nonnegative assumption is important; negative values can invalidate this technique because expanding a window may decrease its sum.

9. Two-Pointer Techniques

Two pointers are indices that move through a sequence according to a structured rule. They are useful for sorted arrays, partitioning, palindrome checks, and pair-sum problems.

Pair sum in a sorted array

Given a sorted array and target T, place one pointer at each end. If the sum is too small, move the left pointer right; if it is too large, move the right pointer left.

def has_pair_with_sum(values, target):
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

This algorithm is O(n) after sorting. If the input is not sorted, sorting costs typically O(n log n), so the total complexity is usually O(n log n). A hash-set method can provide expected O(n) time without sorting, but uses additional storage and has different ordering implications.

The correctness depends on sorted order. Without that property, moving a pointer based on the current sum does not safely eliminate candidates.

10. Applied Case: Sensor-Reading Analysis

Background

Consider an illustrative monitoring system that records hourly temperatures from a manufacturing line. The engineering team needs to answer three questions: the average temperature over selected intervals, whether any three-hour period exceeds a safety threshold, and whether two readings differ by a specified amount.

Problem analysis

The readings are received in chronological order and are not frequently modified. Thousands of interval queries may be issued after collection. A simple loop for every interval would repeat work and could become slow.

Approach and solution

1. Store the readings in a Java int[] or Python list when the number of readings is known or modest.
2. Build a prefix-sum array for repeated interval sums.
3. Use a fixed-size sliding window of length three to find the maximum three-hour total.
4. If readings are sorted for a separate analysis, use two pointers for a pair-difference query; otherwise use a set when original order must be preserved.
5. Validate indices, missing readings, units, and integer overflow. For measurements that may exceed integer limits, use a wider numeric type.

For readings [18, 21, 24, 20, 19], the three-hour sums are:

• 18 + 21 + 24 = 63;
• 21 + 24 + 20 = 65;
• 24 + 20 + 19 = 63.

The maximum is 65. A sliding window computes this in linear time after reading the data, rather than recomputing each sum from three values.

Outcome and learning points

The selected structures match the workload: arrays provide efficient sequential access, prefix sums support repeated static range queries, and sliding windows exploit overlap. The case also demonstrates that the “best” structure depends on update frequency, ordering requirements, memory constraints, and the required queries—not merely on the data type.

11. Challenges, Limitations, and Best Practices

• Check array bounds and validate input sizes.
• Distinguish logical size from allocated capacity.
• Avoid repeated front insertion or deletion in dynamic arrays when a queue or deque is more appropriate.
• Prefer sequential access when locality matters.
• Use immutable strings for safe values, but builders or joining techniques for repeated construction.
• Define text rules explicitly for Unicode, case, punctuation, and normalization.
• Use sparse storage only when sparsity is substantial and access patterns justify it.
• Document whether matrix indices are zero-based or one-based.
• Consider integer overflow in prefix sums and matrix calculations.
• State assumptions behind sliding-window and two-pointer algorithms.
• Benchmark representative workloads rather than relying only on theoretical complexity.

Modern runtimes optimize allocation and memory access, but these optimizations do not remove the need for sound representation choices. In data-intensive and AI-related systems, arrays often hold feature vectors, images, token identifiers, and model parameters. Correct indexing, predictable memory use, and validation are essential because an unnoticed off-by-one error can corrupt an entire computation.

Chapter Summary

Arrays provide constant-time indexed access through contiguous addressing, but insertion and deletion near the beginning are linear because elements must shift. Java arrays have fixed length. Java ArrayList and Python lists are dynamic arrays that grow by allocating larger storage and copying elements; their append operation is amortized constant time.

Strings are immutable in both Java and Python, which supports safe sharing but makes repeated modification costly unless builders or joining techniques are used. Multidimensional arrays represent matrices, while sparse representations save space when most entries are zero. Prefix sums convert repeated static range queries into constant-time queries after linear preprocessing. Sliding windows exploit overlap between contiguous intervals, and two-pointer methods exploit ordering or boundary structure. Effective data-structure selection depends on access patterns, update frequency, locality, memory, and algorithmic assumptions.

Key Terms

Array: A fixed-size indexed sequence of elements.

Index: The integer position used to access an element.

Contiguous storage: Adjacent memory locations used for sequential elements.

Locality: The performance benefit of accessing nearby memory locations.

Dynamic array: An array-like structure that grows when capacity is exhausted.

Capacity: Allocated storage available in a dynamic array.

Amortized analysis: Analysis of average cost over a sequence of operations.

ArrayList: Java’s standard resizable array implementation.

Python list: A built-in dynamic array of object references.

String: An immutable sequence used to represent text.

Matrix: A rectangular arrangement of values indexed by rows and columns.

Jagged array: An array whose rows may have different lengths.

Sparse matrix: A matrix containing mostly zero or default entries.

Prefix sum: A cumulative-sum structure supporting efficient range queries.

Sliding window: A moving contiguous interval maintained during a scan.

Two-pointer technique: An algorithm using two moving indices.

Time complexity: The growth of computational work as input size increases.

Space complexity: The growth of additional memory required by an algorithm.

Review Questions

Short Answer Questions

1. Why does indexed access in a conventional array take O(1) time?
2. What is the difference between the size and capacity of a dynamic array?
3. Why is appending to an ArrayList or Python list amortized O(1)?
4. State the prefix-sum formula for the sum from index l through r.
5. Why must a pair-sum two-pointer algorithm normally use a sorted array?

Long Answer Questions

1. Compare Java arrays, Java ArrayList, and Python lists in representation, flexibility, and performance.
2. Explain how cache locality affects sequential and random array access.
3. Describe dense and sparse matrix representations and identify suitable use cases for each.
4. Explain string immutability in Java and Python and discuss efficient repeated string construction.
5. Derive the time and space complexity of standard matrix multiplication.

Analytical / Application Questions

1. Design an algorithm for answering 100,000 static range-sum queries on an array of 1,000,000 values. Justify the data structure and complexity.
2. A stream contains nonnegative transaction amounts. Design a sliding-window algorithm to find the shortest consecutive period whose total is at least a target value. State why nonnegativity matters.
3. A matrix has 10,000,000 positions but only 25,000 nonzero values. Recommend a representation and analyse its likely benefits and limitations.

Multiple Choice Questions with Answers

Question 1

Which operation is typically O(1) in a conventional array?

A. Inserting at index 0

B. Deleting at index 0

C. Reading by index

D. Searching an unsorted array

Correct Answer: C. Reading by index

Question 2

What is the usual amortized complexity of appending to a geometrically growing dynamic array?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: A. O(1)

Question 3

Which Java structure has a fixed length after creation?

A. ArrayList

B. Array

C. StringBuilder

D. HashSet

Correct Answer: B. Array

Question 4

For prefix sums p[0] = 0 and p[i + 1] = p[i] + a[i], what is the sum from l through r?

A. p[r] − p[l]

B. p[r + 1] − p[l]

C. p[r] + p[l]

D. p[l + 1] − p[r]

Correct Answer: B. p[r + 1] − p[l]

Question 5

Which representation is most appropriate when a matrix is overwhelmingly zero?

A. Dense two-dimensional array

B. Coordinate or dictionary representation

C. A string containing every value

D. A sorted scalar variable

Correct Answer: B. Coordinate or dictionary representation

Question 6

What is the standard time complexity of multiplying an r × k matrix by a k × c matrix?

A. O(r + k + c)

B. O(rc)

C. O(rkc)

D. O(log(rkc))

Correct Answer: C. O(rkc)

Question 7

Why is StringBuilder useful in Java?

A. It makes arrays fixed-length

B. It supports efficient repeated string construction

C. It automatically sorts characters

D. It converts strings into matrices

Correct Answer: B. It supports efficient repeated string construction

Question 8

A fixed-size sliding-window sum updates by which operation?

A. Multiply the old sum by the window size

B. Subtract the outgoing value and add the incoming value

C. Sort every window

D. Rebuild the entire array necessarily

Correct Answer: B. Subtract the outgoing value and add the incoming value

Question 9

The two-pointer pair-sum method described in the chapter requires which important property?

A. The values must be strings

B. The array must be sorted

C. The array must contain only zeros

D. The array must be two-dimensional

Correct Answer: B. The array must be sorted

Question 10

What is the typical time complexity of traversing every entry of an r × c matrix?

A. O(r + c)

B. O(r − c)

C. O(rc)

D. O(1)

Correct Answer: C. O(rc)