Skip to main content

Arrays

Arrays are one of the simplest and most efficient data structures. Their biggest advantage is that you can read and write elements in constant O(1) time, because all elements are stored in a contiguous block of memory and accessed using a numerical index.

However, arrays are less flexible when it comes to modifying their contents. Inserting or removing elements can require shifting items or reallocating memory, leading to O(n) time complexity. Similarly, searching for a value may require scanning the entire array in the worst case.

Despite these trade-offs, arrays form the foundation for many other data structures and appear everywhere in interview problems.

array

Types

1D arrays

The simplest array is a one-dimensional array, essentially a list of elements accessed by a single index. These are useful for linear data such as scores, prices, or IDs.

2D arrays

At a higher level, arrays can be used to store references to other types - even other arrays. 2D arrays are a common array-of-arrays pattern that can be used to store tabulated data, like a location on a grid, or the price per unit of goods at different volumes. These 2D arrays are indexed by two subscripts, one for the row and another for the column.

When calculating the size of a 2D array, simply multiply the number of elements by the size of each element.

Static vs. dynamic arrays

In many statically typed programming languages (Java, C, C++), arrays are fixed size once declared. If more capacity is needed, a new larger array must be allocated and elements copied over. Modern languages, however, support dynamic arrays (e.g., Python lists, Java ArrayList), which automatically resize themselves when they run out of space. Dynamic arrays achieve better amortized performance, since resizing happens infrequently, typically doubling the array size when full.

dynamic array

Common array patterns

Common array operations

1. Append an item to the end

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

2. Insert an element at a specific index

arr = [10, 20, 30, 40] arr.insert(2, 25) # insert 25 at index 2 print(arr) # [10, 20, 25, 30, 40]

3. Update an element

arr = [10, 20, 30] arr[1] = 99 # update index 1 print(arr) # [10, 99, 30]

4. Traverse an array

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

Arrays TC SC

Calculating memory usage

To calculate the memory footprint of an array, simply multiply the size of the array with the size of the data type.

Question: What is the memory usage of an array that contains one thousand 32-bit integers?

Answer: 1,000 * 32 bits = 1,000 * 4 bytes = 4 Kb

Question: What is the memory usage of an array that contains one hundred 10-character strings?

Answer: 100 * 10 chars = 100 * 10 * 1 byte = 1 Kb

Common edge cases & pitfalls in arrays

When working with arrays, certain edge cases and mistakes frequently lead to incorrect results or runtime errors. Robust solutions should always account for:

  1. Off-by-one errors: Loop limits are easy to get wrong. For example, for (i = 0; i <= n; i++) attempts to access arr[n], which is out of range. Use i < n instead.

  2. Index out of bounds: Arrays in most languages are indexed from 0 to n-1. Accessing an invalid index, especially in empty or single element arrays causes errors. Always validate array length before accessing elements.

  3. Sorted vs. unsorted input: Some algorithms, like binary search, only work correctly on sorted arrays. Linear search works on both, but takes O(n) time. Always check whether sorted order is required.

  4. Duplicate elements: Algorithms involving frequency, counting, or removal must correctly handle cases like [1,2,3] (all unique) and [5,5,5] (all duplicates). Failing to account for this can produce wrong counts, infinite loops, or missing elements.

Quiz

  1. Find out the issue with this code: for (i = 0; i <= n; i++) for an array of size n?

a) It misses the first element

b) It processes the last element twice

c) It causes array index out of bounds

d) It skips alternate elements

  1. What is the time complexity of accessing any element in an array by its index?

a) O(log n)

b) O(n)

c) O(1)

d) O(n²)

  1. What happens when you insert an element in the middle of an array of size n?

a) It takes O(1) time because arrays are contiguous

b) It requires shifting elements and takes O(n) time

c) It deletes the last element automatically

d) It reverses the array order

Practice problems

Next Lesson