Arrays

Arrays show up in interviews more than almost any other data structure because they are the default way problems represent input: a list of numbers, characters, or objects in a specific order. It stores elements in a fixed order and supports direct access by index, which makes it suitable for tasks like scanning sequences, computing subarray results, tracking frequencies, and performing in-place updates.

In technical interviews at FAANG companies, arrays are tested heavily, not because implementing them is difficult, but because many problems depend on precise control over indices, boundaries, and time complexity. Solutions often fail due to off-by-one errors, incorrect window limits, or inefficient approaches that do not meet the constraints.

What is an array?

An array is a linear data structure that stores elements in a fixed sequence (one after another) and lets you access any element directly using its index (position). If arr is an array, then:

• arr[i] means “the element stored at index i.”
• Indexing is usually 0-based, meaning the first element is at index 0, the second at 1, and so on.

In most languages, especially low-level ones like C/C++, arrays are stored contiguously, meaning all elements are next to each other in a single continuous block. This enables O(1) direct access by index. Some high-level languages, like JavaScript and Python, have more flexible implementations that may not guarantee true contiguous storage, but they still preserve the same logical access patterns.

Intuition behind an array

Arrays work well because they represent data as an ordered sequence, where each element is directly accessible by index. This makes them ideal when your solution depends on scanning in order, comparing neighbors, or computing results over contiguous ranges.

You typically reach for an array-based approach when you need to:

• Process elements left to right (or right to left),
• Access or update specific positions quickly,
• Compare adjacent elements like arr[i-1] and arr[i+1],
• Compute results over subarrays (contiguous ranges).

Key characteristics of arrays

So far, we have defined what arrays are and the kinds of problems where they naturally show up.

An array enforces a strict positional discipline: each element lives at a specific index, and the data structure is optimized around fast access to that index. This is why arrays work well for scanning and in-place updates. The trade-off is that the array must preserve an ordered layout, so insertions and deletions in the middle typically require shifting elements.

The defining characteristics of an array are:

• Direct indexing (O(1)) access: Any element can be read or updated immediately using its index (e.g., arr[i]), without traversing earlier elements.
• Ordered, contiguous layout: Elements are stored in a single sequence, making the structure predictable and supporting efficient sequential processing.
• Linear-time traversal (O(n)): Visiting the full array requires touching each element once, which is the basis of most array solutions in interviews.
• O(n) mid-array insert/delete: Inserting or deleting away from the end usually shifts subsequent elements to maintain order, making these operations linear in the worst case.

These constraints are exactly what make arrays reliable in interviews: you get predictable O(1) positional access and a clear cost model for scans and modifications, which helps you reason about correctness and complexity.

Static and dynamic arrays

So far, we have treated arrays as if they have a single, uniform behavior: you create them, access elements by index, and iterate through them. In reality, arrays come in two fundamental varieties that differ in how they handle size: static arrays and dynamic arrays. Understanding this distinction matters in interviews because it affects how you reason about space complexity, reallocation costs, and whether operations like append are truly O(1).

Static arrays

A static array has a fixed size that is determined at creation time and cannot change afterward. Once you allocate a static array of size n, you get exactly n slots, no more and no less. If you need to store more elements, you must allocate a new, larger array and copy the old elements over manually.

In languages like C, C++, and Java, traditional arrays are static:

int arr[10];  // C/C++: fixed size of 10
int[] arr = new int[10];  // Java: fixed size of 10

Static arrays are straightforward: you know the size up front, memory is allocated once, and there is no hidden overhead. The trade-off is rigidity. If you underestimate the size, you run out of space. If you overestimate, you waste memory.

Key properties of static arrays

Some of the key properties of static arrays are listed below:

• Fixed size at creation.
• No automatic resizing.
• Minimal memory overhead (just the elements themselves).
• Predictable performance: O(1) access, O(n) traversal, no hidden reallocation.

Dynamic arrays

A dynamic array (also called a resizable array or growable array) automatically grows when you try to add more elements than it currently has space for. Internally, it starts with some initial capacity, and when that capacity is exceeded, it allocates a larger block of memory, copies the old elements over, and continues.

Languages like Python, Java, and C++ provide built-in dynamic arrays:

arr = []  # Python list: dynamic array
ArrayList<Integer> arr = new ArrayList<>();  // Java: dynamic array
std::vector<int> arr;  // C++: dynamic array

Dynamic arrays give you flexibility: you can keep appending elements without worrying about the size. The cost is occasional reallocation. When the array runs out of space, it typically doubles its capacity, copies everything over, and discards the old block.

Key properties of dynamic arrays:

• Size grows automatically as needed.
• Most appends are O(1), but occasional resizing costs O(n).
• Slight memory overhead (extra capacity beyond current size).
• Same O(1) access and O(n) traversal as static arrays.

Here’s a table showing which languages have static arrays, dynamic arrays, or both:

When does this matter in interviews?

In most interview problems, the distinction between static and dynamic arrays is not central to the solution. You are typically given an input array (static in concept) and asked to process it, and if you need extra space, you allocate it once based on the input size.

However, the distinction becomes relevant when:

• You are building up a result incrementally: If you are appending elements as you go (e.g., collecting valid results in a filtered list), a dynamic array makes the code simpler and gives you fast O(1) appends on average.
• You are analyzing space complexity: If the problem asks for O(1) extra space, you cannot use a dynamic array that grows with input size. You must work in-place or use a fixed-size auxiliary structure.
• You are reasoning about worst-case vs. average cost: Knowing that a dynamic array occasionally triggers O(n) reallocations helps you correctly analyze time complexity in scenarios where appends occur within loops.

Basic Array operations

Arrays expose a small and well-defined set of operations. While each operation is simple on its own, together they enable most array-based interview solutions: scanning, searching, in-place modification, and range-based computations.

We will walk through each operation individually, starting with its purpose, followed by a code example and a small illustration.

Access (Read an element)

The access operation retrieves the element at a specific index. Conceptually, this represents “jumping” directly to a position in the array.

arr = [10, 20, 30, 40]
value = arr[2]   # 30

Example: In this array:[10, 20, 30, 40], arr[1] returns 20.

Update (Write an element)

The update operation replaces the value at an index with a new value. This represents modifying data in place without changing the structure of the array.

arr = [10, 20, 30, 40]
arr[1] = 99 # Replaces the value at index 2
[10, 99, 30, 40]

Example: Updating index 1 changes the second element, but the array length stays the same.

Traverse (Iterate through the array)

Traversal visits elements in order, typically left-to-right. This represents processing the full sequence, one element at a time.

arr = [10, 20, 30, 40]
for value in arr:
    print(value)

The above code prints 10, 20, 30, 40 in order.

1 / 4

Insert (Add an element)

Insertion adds a new element and increases the array length. The cost depends on where you insert.

Insert at end (append)

For dynamic arrays, you can append an element to the end of the array. For static arrays, it is possible if space is available.

arr = [10, 20, 30]
arr.append(40)

Example: If you append 40 to this array:[10, 20, 30], the array becomes:[10, 20, 30, 40].

Conceptually, this is the simplest insertion because it does not require rearranging existing elements.

Insert in the middle/beginning (requires shifting)

To insert at index k, elements from k onward shift one position to the right to create space.

arr = [10, 20, 30, 40]
arr.insert(1, 99)   # arr is now [10, 99, 20, 30, 40]

Example: In this array: [10, 20, 30, 40], if we insert 99 at index (1), 20, 30, 40 shift right by one position, and the array becomes: [10, 99, 20, 30, 40].

Delete (Remove an element)

Deletion removes an element and decreases the array length. Like insertion, the cost depends on where you delete.

Delete from the end

For dynamic arrays, removing the last element is immediate and does not require shifting. For static arrays, you can conceptually “delete” by reducing the logical size.

arr = [10, 20, 30, 40]
arr.pop()
# arr is now [10, 20]

In this array: [10, 20, 30, 40], if we pop an element from the array, the array becomes: [10, 20, 30].

Delete from the middle/front (requires shifting)

To delete an element at index k, elements after k shift left to close the gap.

arr = [10, 20, 30, 40]
arr.pop(1)
# arr is now [10, 30, 40]

Example: In this array: [10, 20, 30, 40], if we pop an element from index(1), 30, 40 shift left by one position to close the gap.

Complexity analysis

Understanding the cost of array operations helps evaluate their impact when used inside larger algorithms.

Time complexity

Array performance depends on whether an operation works at a known index or requires scanning or shifting elements. Operations that work directly on an index are constant time, while operations that change the array’s structure often require moving multiple elements.

• Access (read) by index: O(1): Retrieving arr[i] is a direct lookup at a known memory location and does not require traversal.
• Update (write) by index: O(1): Assigning arr[i] = x modifies a single element at a known index without affecting other elements.
• Traversal (iterate): O(n): Visiting every element requires one step per element, touching all n positions in the array.
• Insert at end: O(1) on average: Appending an element places it at the end with no shifting required. Dynamic arrays occasionally trigger O(n) resizing when they run out of capacity.
• Insert/delete in middle or front: O(n): To preserve order and keep the array contiguous, all elements after the operation point must shift left or right.

These characteristics make arrays especially effective for problems built around scanning, indexing, and in-place updates, while mid-array insertions and deletions remain the primary performance bottleneck.

Space complexity

• O(n), where n is the number of elements stored in the array.

An array stores its elements directly, so the memory required grows linearly with the number of elements. If an algorithm creates additional arrays (for example, a copy of the input or an auxiliary prefix array), that extra storage must be counted separately as additional space.