Rotate an n by n matrix 90 degrees clockwise, in place.

Transpose the matrix (swap element (r, c) with (c, r) for c > r), then reverse every row. Each element is touched a fixed number of times, so time is O(n²) for n × n elements. It works in place, so extra memory is O(1).

Check whether a string is a palindrome, ignoring case and anything that is not a letter or digit.

Use two indexes, one at each end. Skip characters that are not letters or digits, compare the two characters ignoring case, and move both indexes inwards. If any pair differs, it is not a palindrome. Time is O(n) and extra memory is O(1), because nothing is copied.

Given an array of numbers, return a new array where each item is the product of all the other items, without using division.

First pass: result[i] holds the product of everything to the left of i. Second pass, from the right: keep a running product of everything to the right and multiply it into result[i]. Time is O(n) and extra memory is O(1) beyond the output array.

Check whether two strings are anagrams of each other.

If the lengths differ, return false. Otherwise count each letter of the first string in an array of 26 counts (for lower-case English), subtract for the second string, and check that every count is zero. Time is O(n) and memory is O(1), because 26 is a constant. Sorting both strings also works in O(n log n).

Arrays and Strings

Items stored side by side so you can jump to any position. Learn what is fast, what is slow, and how 2D arrays and strings fit in.

beginner25 minAsked oftenArraysStringsMatrix2d arrayDynamic array

Last reviewed 24 Oct 2026 · by TheLearningLoop Team

Read first: Data Structures & Algorithms: The Big Picture (blog post)

Progress is saved on this device. Create a free account to keep it everywhere.

On this page ▾

On this page

Key takeaways

An array stores items side by side, so reading any position takes one step: O(1).
Inserting or deleting in the middle moves every later item, so it costs O(n).
Strings are arrays of characters. In most languages they cannot be changed in place, so build them with a builder.

When to use an array

Use an array (or a string) when you need:

Access by position: "the 5th item", "the last item", "item i". It takes one step however long the array is.
To loop over everything in order, which is also the fastest way a computer can read data, because the items sit side by side in memory.
A collection that mostly grows and shrinks at the end, such as a list of results or a stack of undo steps.
A compact collection with no extra memory per item.
Text: a string is an array of characters, so reading, slicing and scanning use the same ideas.

Use something else when:

You look items up by a key, not a position: use a hash map.
You add or remove at the front or middle all the time: use a linked list or a deque (double-ended queue).
You need items kept in sorted order while they change: use a balanced tree.
You only ask "is this in the set?": use a hash set.

Do not build arrays by hand. Every language has a growable array (see the real-world section). Writing one yourself is for learning and interviews.

How an array works

An array is a row of items stored side by side in memory, each in a numbered slot called an index, starting at 0.

An array's items are contiguous, so the address of item i is the start of the array plus i times the size of one item.

That sum is why reading any position takes one step. The cost is that the items must stay side by side, so putting one in the middle means shifting everything after it.

Two ideas to keep in mind:

Fixed size or growable. A plain array has a fixed length. A dynamic array (Python list, Java ArrayList, C++ vector, Go slice, Rust Vec) reserves spare room, called its capacity. When it fills up it allocates a bigger array, usually a multiple of the old size, and copies everything across.
Strings are arrays of characters. In Java, Python, JavaScript, Go and C# a string cannot be changed in place: "changing" it builds a new string. In C++ and Rust you can edit a string.

A 2D array (a grid or matrix) is an array of rows, where each row is an array. Item (row, column) is grid[row][column]. An image, a spreadsheet and a chess board are all 2D arrays.

Try it

Start with 7 3 9 4. Try the operations and watch the items moved counter.

Array

Step 1 of 1 · Press Space to play, arrow keys to step

Start from:

Start: an array holding 4 items with room for 4. Use the buttons above to try an operation.

length:: 4
capacity:: 4
items moved:: 0
comparisons:: 0

length = items stored. capacity = slots reserved. items moved counts every item copied or shifted.

Speed

Things to try:

Append 5 to the full array. It has to grow: the array doubles from 4 slots to 8 and copies 4 items. Then append 6: no copy, no moves.
Insert 0 at index 0. All 4 items shift right, so 4 moves. Insert at the end instead and nothing moves.
Read index 2, then Search 4. Reading by position is one step. Searching by value checks items one by one, here 4 comparisons.
Use the Letters start (H E L L O) and delete index 1 to see how a string loses a character.

Array operations: read, search, insert and delete

Read by index. Jump straight to the slot. One step. This is the array's superpower.

Search by value. Without any order to rely on, check each item from the start until you find it, or reach the end. If the array is sorted, binary search is much faster (see the Sorting and Binary Search lesson).

Append. Put the item in the next free slot. If the array is full, allocate a bigger one and copy. Because the growth is a multiple (for example doubling), the average cost per append is O(1). This is called amortised O(1).

Insert in the middle. Move every item from that index onwards one place right, then place the new item. Cost grows with how many items sit after it.

Delete from the middle. Remove the item, then move every later item one place left to close the gap.

Strings. Because most strings are immutable, s = s + "x" in a loop copies the whole string each time, which is O(n²) overall. Collect the pieces in a list or a string builder and join them once at the end.

Interview fact. Reading by index is O(1), but insert and delete in the middle are O(n). A question that seems to ask for "insert" is often really asking whether you notice that shifting cost.

Array time complexity

Operation	Normal case	Worst case
Read or write by index	O(1)	O(1)
Search by value (unsorted)	O(n)	O(n)
Append to a dynamic array	O(1) amortised	O(n) when it must grow
Insert at index	O(n)	O(n)
Delete at index	O(n)	O(n)
Memory	O(n)	O(n)

The expensive cases come from shifting items or copying the whole array. Inserting or deleting at the end avoids shifting, and growing by a multiple keeps the copying rare.

Arrays vs other data structures

The right choice depends on what you do most. n is the number of items.

What you need	Array	Linked list	Hash map	Sorted array
Read item at position `i`	O(1)	O(n)	Not position-based	O(1)
Find a value	O(n)	O(n)	O(1) average	O(log n)
Add at the end	O(1) amortised	O(1) with a tail pointer	O(1) average	O(n) to keep order
Insert in the middle	O(n)	O(1) once you hold the node	Not position-based	O(n)
Delete from the middle	O(n)	O(1) once you hold the node	O(1) average by key	O(n)
Walk everything in order	O(n), fastest in practice	O(n), slower	No order	O(n), fastest in practice
Memory	O(n), compact	O(n) plus a pointer per item	O(n) plus spare slots	O(n), compact

The bold cells show where each one wins. Arrays win on position and on scanning, because their items sit together in memory and the processor reads them quickly. They lose when you insert or delete away from the end.

How to explain arrays in an interview

Say what an array is: "items side by side, so index i is one step."
Give the costs in one breath: "read O(1), search O(n), insert and delete in the middle O(n), append O(1) amortised."
Mention amortised growth: "it doubles when full, so the copy cost is spread across many appends."
For strings, ask whether they are mutable in the language, and say you would use a builder for repeated concatenation.
For a matrix, say the grid is rows × columns, so a full pass is O(rows × columns).

Where you meet arrays in real systems

You use arrays all day without noticing. Here are three drawn out, the first with code you can run, then more examples.

Example 1: Images are 2D arrays

A photo is a grid of pixels, and a grid is a 2D array: image[row][column] is one pixel. Turning a photo 90 degrees, as your phone does when you rotate it, means moving every pixel to a new position. The code below rotates a square image clockwise, in place, by swapping pixels across the diagonal and then reversing each row. Open the example below to see the picture and the code.

Code: rotate an image 90 degrees clockwiseTime O(n²)Memory O(1)

Pixel 1 starts at the top left and ends at the top right. Every pixel moves, so the work grows with the number of pixels: n × n.

def rotate_clockwise(image):
    """Rotate a square image 90 degrees clockwise, in place.

    An image is a 2D array: image[row][column] is one pixel. Rotating is
    "transpose, then reverse each row".

    Time:   O(n^2). Every one of the n x n pixels is touched a fixed number of times.
    Memory: O(1) extra. Pixels are swapped inside the same array, no copy is made.
    """
    n = len(image)
    for r in range(n):                      # 1. transpose: swap across the diagonal
        for c in range(r + 1, n):
            image[r][c], image[c][r] = image[c][r], image[r][c]
    for row in image:                       # 2. reverse every row
        row.reverse()

Each version rotates the same 3 by 3 image and printed [[7, 4, 1], [8, 5, 2], [9, 6, 3]]. All five were compiled and run, and none of them uses a package.

Example 2: Text editors and inserting in the middle

A text document is an array of characters. Typing a letter in the middle means every character after the cursor must shift right by one. For a short line that is trivial. For a very large file it is not, which is why many editors use structures built to avoid it, such as a gap buffer (an array with a movable empty gap at the cursor) or a piece table.

Typing L between E and L pushes the last two letters one place right. The cost grows with how much text sits after the cursor.

Example 3: Ring buffers for streams and logs

A ring buffer (circular buffer) is a fixed-size array used as a loop: new items overwrite the oldest ones, and two indexes, "write" and "read", chase each other round the array. It never needs to grow or shift, so audio pipelines, network drivers and log collectors use it to hold the most recent data.

Slots 4 and 5 hold the oldest items. New items 7 and 8 wrapped round to slots 0 and 1. The next write overwrites slot 2, the oldest.

More real-world scenarios

4. Spreadsheets, game boards and maps

A spreadsheet, a chess board, a Sudoku grid and a tile map in a game are all 2D arrays. Finding the cell to the left or above is simple index arithmetic, which is why grids are the first choice for these.

5. Audio and sensor samples

Digital audio is a long array of numbers, each one a measurement of the sound wave at one instant. Sensors on phones and devices produce arrays of readings the same way. Playing, filtering or averaging them means scanning the array in order.

6. Network packets and byte buffers

A network packet or a file read from disk arrives as an array of bytes. Parsers walk through it by index, reading a header at fixed positions and then the payload that follows.

7. Searching text

Searching a log for an error, a document for a word, or DNA for a sequence is a string problem. The simplest search compares the pattern at each position in turn, and faster algorithms improve on that idea.

8. Compilers and parsers

A compiler or a JSON parser reads source text one character at a time, grouping characters into tokens such as numbers, names and brackets. That scan is a loop over a string.

9. Growable lists in every language

When you append to a Python list, a Java ArrayList or a C++ vector, you are using a dynamic array. They all reserve spare room and grow when full, though the growth factor differs between languages and implementations.

10. Matrices and tensors in data science

Libraries for numbers and machine learning, such as NumPy, store data in multi-dimensional arrays in one block of memory. Adding two of them, or multiplying them, loops over that block, which is fast because it is contiguous.

Language standard libraries

Every mainstream language gives you a fixed array, a growable list and a string type.

Language	Structure or class	What it is under the hood	Notes
Java	`int[]`, `ArrayList<T>`, `String`, `StringBuilder`	Fixed array, dynamic array, immutable string, mutable builder	Use `StringBuilder` to build text in a loop.
C++	`std::array`, `std::vector`, `std::string`	Fixed array, dynamic array, mutable string	`std::string` can be edited in place.
C#	`T[]`, `List<T>`, `string`, `StringBuilder`	Fixed array, dynamic array, immutable string, mutable builder	Same pattern as Java.
Rust	`[T; N]`, `Vec<T>`, `String`	Fixed array, dynamic array, growable UTF-8 string	`String` is mutable. `&str` is a read-only view of one.
Python	`list`, `str`, `array.array`	Dynamic array of references, immutable string, compact typed array	Use `"".join(parts)` to build a string. The `array` module stores plain numbers compactly.
Go	Arrays, slices, `string`, `strings.Builder`	A slice is a view onto an array with a length and a capacity	Strings are immutable. Use `strings.Builder` for loops.
JavaScript	`Array`, `String`	Resizable array, immutable string	Join an array of parts to build a string.
Kotlin	`Array<T>`, `MutableList<T>`, `String`, `StringBuilder`	Same as Java	`ArrayList` is the usual `MutableList`.

The pattern: a fixed array, a growable list, and a text type that is either immutable with a separate builder, or mutable.

The takeaway

Whenever a system needs fast access by position and fast scanning of data in order, look for an array. When it needs to find things by key or insert in the middle often, it usually uses a hash map or a linked structure instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Rotate an n by n matrix 90 degrees clockwise, in place.
medium
2.
Check whether a string is a palindrome, ignoring case and anything that is not a letter or digit.
easy
3.
Given an array of numbers, return a new array where each item is the product of all the other items, without using division.
medium
4.
Check whether two strings are anagrams of each other.
easy

Hash Tables