Arrays & Strings

Arrays and strings are the most fundamental linear data structures. Most interview problems and many higher‑level structures (like heaps and hash tables) are built on top of them.

Understanding how arrays and strings work in memory helps you reason about performance and choose the right operations.

What Is an Array?

An array is a contiguous block of memory storing elements of the same type:

• Each element has the same size.
• Indexes map directly to memory offsets: address of a[i] = base + i * sizeof(element).

This gives arrays two key properties:

• O(1) random access by index.
• Efficient sequential scanning (good cache behavior).

But also some limitations:

• Fixed size (unless you build a dynamic array on top).
• Inserting or deleting in the middle is O(n) because you must shift elements.

Common Array Operations and Complexity

Operation	Complexity
Access by index	O(1)
Scan / iterate	O(n)
Insert/delete at end	O(1) amortized (for dynamic arrays)
Insert/delete at front/middle	O(n)
Search unsorted	O(n)
Search sorted (binary search)	O(log n)

In many languages:

• Java: int[], String (backed by a char array).
• Python: list (dynamic array), str (immutable sequence).

What Is a String?

A string is typically an array of characters with:

• A length.
• In low‑level languages, a terminator (e.g. '\0' in C).

Key properties:

• Most languages treat strings as immutable:
  • Operations like concatenation allocate new strings.
  • Repeated concatenation in a loop can become O(n²) unless you use a builder (StringBuilder in Java).
• You still get:
  • O(1) access by index (conceptually, though some encodings like UTF‑8 complicate true constant time).
  • O(n) scans for searching or processing characters.

Arrays & Strings in Interviews

Many patterns are really just structured ways of traversing arrays/strings:

• Two Pointers:
  • Move i, j through a sorted array or string to find pairs, partition, or check palindromes.
• Sliding Window:
  • Maintain a window [left, right) on an array/string and track some aggregate (sum, counts, etc.).
• Prefix Sums:
  • Precompute prefix[i] to answer range sum queries in O(1).

These patterns depend on fast sequential access and simple index arithmetic — exactly what arrays and strings provide.

Example: Sliding Window on an Array (Java)

The following code finds the maximum sum of any subarray of size k using a fixed‑size sliding window:

JavaCopy
int maxSumOfWindowK(int[] nums, int k) {
    int n = nums.length;
    if (n < k) return 0;
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
    int best = windowSum;
    for (int right = k; right < n; right++) {
        windowSum += nums[right];
        windowSum -= nums[right - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

This is a concrete example of combining arrays (indexed access) with the sliding window pattern.

When Arrays & Strings Are the Right Tool

Use arrays/strings when:

• You need indexed access and frequent scans.
• You can keep the data size fixed or mostly append‑only.
• You want the simplest possible structure with minimal overhead.

They are often the best choice for:

• Representation of signals, time series, basic records.
• Dynamic programming tables.
• Intermediate buffers in algorithms.

Higher‑level structures (heaps, hash tables, tries) will appear later, but all of them rely heavily on array‑like storage under the hood.