Know this before you start: “Index into a list and walk left → right”
Indexing and walking through an array
nums[i] reads any position instantly. A loop from 0 to n − 1 visits every item once: the building block of almost every solution.
The idea
An array (a Python list) keeps items side by side, numbered from 0. Because they're side by side, nums[i] jumps straight to position i in O(1), no matter how long the list is.
Most solutions walk the array once from left to right, carrying a little information as they go: the best so far, a running total, what they've seen. One pass over n items is O(n).
Python gives you the index and value together with enumerate, and negative indexes count from the end: nums[-1] is the last item.
See it step by step
Find the largest number and where it is in [4, 9, 2, 9, 1]
- Start with best = nums[0] = 4 at index 0.
- i = 1: 9 > 4 → best = 9 at index 1.
- i = 2: 2 isn't bigger. i = 3: 9 isn't bigger (keep the first one). i = 4: 1 isn't bigger.
- Answer: 9 at index 1, after looking at each item exactly once.
In code (Python)
def largest(nums):
best_i = 0
for i, x in enumerate(nums): # index and value together
if x > nums[best_i]:
best_i = i
return nums[best_i], best_i
nums = [4, 9, 2, 9, 1]
print(nums[0], nums[-1], len(nums)) # 4 1 5
print(largest(nums)) # (9, 1)Reading nums[i]: O(1). Walking the whole array: O(n).
When you'll use it
- Every array or string problem starts here.
- Whenever the answer can be built by looking at each item once, carrying a small summary.
Common mistakes
- Off by one: valid indexes are 0 … n − 1, so range(n), not range(n + 1).
- Changing a list's length while looping over it.
