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.
Declaring 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.
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);
}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)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";
}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));size() inside the condition
In C++, nums.size() returns an unsigned type. Comparing a signed i against it triggers a warning, and an empty vector makes size() - 1 wrap to a huge number — a classic source of infinite loops. Cast it, or use size_t deliberately.
Operations and their cost
| 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.
Working 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.
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
| Problem | Pattern | Level |
|---|---|---|
| Find the largest and second largest element | Single pass | Easy |
| Reverse an array in place | Two pointers | Easy |
| Remove duplicates from a sorted array | Read/write pointers | Easy |
| Move all zeros to the end | Read/write pointers | Easy |
| Rotate an array by k steps in place | Reversal trick | Medium |
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 on Arrays
Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.
⚡ Start the Arrays quiz