Array Traversal and Operations with Time Complexity

Traversal is the loop everything else is built from, and complexity is the vocabulary interviewers grade you in. This lesson pins down both: how to walk an array in four languages, and what each operation actually costs and why.

8 min read 3 sections 5 practice problems

01Declaring and traversing

Two loop styles matter. An index loop when you need i — comparing neighbours, moving two pointers, writing back into the array. A for-each loop when you only need the values, because it removes a whole class of off-by-one bugs.

Java

int[] nums = {42, 17, 99, 8, 63};

// Index loop - you control i, needed for two-pointer work
for (int i = 0; i < nums.length; i++) {
    System.out.println(i + " -> " + nums[i]);
}

// Enhanced for - cleaner when the index does not matter
for (int value : nums) {
    System.out.println(value);
}

Python

nums = [42, 17, 99, 8, 63]

# Index loop
for i in range(len(nums)):
    print(i, "->", nums[i])

# Value loop, with the index when you need both
for i, value in enumerate(nums):
    print(i, "->", value)

C++

vector<int> nums = {42, 17, 99, 8, 63};

for (int i = 0; i < (int)nums.size(); i++) {
    cout << i << " -> " << nums[i] << "\n";
}

// Range-based for; the reference avoids copying each element
for (const int& value : nums) {
    cout << value << "\n";
}

JavaScript

const nums = [42, 17, 99, 8, 63];

for (let i = 0; i < nums.length; i++) {
  console.log(i, '->', nums[i]);
}

// forEach hands you both the value and the index
nums.forEach((value, i) => console.log(i, '->', value));

02Operations and their cost

Time complexity for an array of n elements
Operation	Time	Why
Access `arr[i]`	O(1)	The address is computed, not searched for
Update `arr[i] = x`	O(1)	Same address arithmetic, one write
Search, unsorted	O(n)	Every element may have to be checked
Search, sorted	O(log n)	Binary search halves the range each step
Insert at the end, dynamic array	O(1) amortised	Free until a resize; the resize is spread over many appends
Insert at index 0	O(n)	All n elements shift one place right
Delete at index 0	O(n)	All remaining elements shift one place left
Delete at the end	O(1)	Nothing has to move

Space is O(n). Notice the shape of the table: anything at the end is cheap, anything at the front is linear. When a problem needs frequent insertion at the front, that is the signal to reach for a deque or a linked list instead of forcing an array to do it.

Why the end is cheap and the front is O(n): an append writes one slot, an insert at the front has to move everything out of the way first.

03Working in place

"In place" means O(1) extra space — you rearrange the array you were given instead of building a new one. Most array interview questions quietly expect it, and the trick is almost always a second index that trails the first.

Move every zero to the end, keeping the order of the rest

void moveZeros(int[] a) {
    int write = 0;                       // next slot for a non-zero value
    for (int read = 0; read < a.length; read++) {
        if (a[read] != 0) {
            a[write++] = a[read];        // compact non-zeros to the front
        }
    }
    while (write < a.length) {
        a[write++] = 0;                  // fill the tail with zeros
    }
}

One pass, no extra array, order preserved. The read pointer scans; the write pointer marks where the next kept element belongs. That read/write pair reappears constantly — in duplicate removal, in partitioning, in filtering.

Key takeaways

Use an index loop when you need i, a for-each loop when you do not.
Cheap at the end, O(n) at the front — that asymmetry drives most data-structure choices.
Binary search needs a sorted array; without sorting, search is O(n).
In place means O(1) extra space, usually achieved with a trailing write pointer.

Practice problems

Tagged by pattern, so you can tell whether you learned the idea or just the example.

Find the largest and second largest elementSingle passEasy
Reverse an array in placeTwo pointersEasy
Remove duplicates from a sorted arrayRead/write pointersEasy
Move all zeros to the endRead/write pointersEasy
Rotate an array by k steps in placeReversal trickMedium

Frequently asked questions

What is the time complexity of inserting into an array?

Appending to a dynamic array is O(1) amortised. Inserting at any other position is O(n), because every element after the insertion point must shift one place right.

Is it safe to modify an array while looping over it?

Removing elements during a forward loop shifts the remaining ones left and makes the loop skip an element. Either iterate backwards, or build a new array, or use the read/write two-index pattern.

How do I copy an array properly?

Assignment copies the reference, not the contents, so both names point at the same array. Use Arrays.copyOf in Java, list slicing or list.copy() in Python, the vector copy constructor in C++, or slice()/spread in JavaScript.

Test yourself

Test yourself on Arrays

Reading is not recall. Take a timed quiz on Arrays solo, or share a room code and battle friends on it.

Start the quiz Try a mock interview

More in Arrays

Written and maintained by the JBattle team · Updated 5 September 2026