When I’m solving a fast-paced coding challenge I often confuse myself with off-by-one errors.
- Should I loop until
- When is it safe to index into an array? (
range(0,len(array))lead to index out of bounds errors or will it end exactly at the array’s last element?
None of these questions are difficult to answer. But, in the heat of the moment when solving a coding challenge I find it easy to second guess myself.
The purpose of this blog post is to clearly explain and demonstrate the answers to these questions in order to cement my understanding of them. The answers to all of these questions should be second nature to any competitive programmer. I should instinctively know the answers and how to apply them in the moment without a second thought.
Should I loop until
The confusion here comes from 0-based indexing common to most programming languages. The question is: does the
len count the elements of an array in a 0-based or 1-based way? If I never learned about 0-based array indexing this probably wouldn’t be confusing.
A list with 5 elements in it has a
len of 5. Duh, right? But wait, if it has 5 elements why can’t we index the 5th element with the number 5?
>>> array = [1,2,3,4,5] >>> array Traceback (most recent call last): File "<stdin>", line 1, in <module> IndexError: list index out of range
It’s computer science 101: indexing into an array is always 0-based. The 1st element is at the 0th index, while the 5th element is at the 4th index.
It’s really simple. The
len function just counts the number of elements in the array (like 1, 2, 3…), while indexing is always 0-based.
So, when writing a while loop we want to loop until our pointer is less than the array’s
>>> n = 0 >>> while n < len(array): ... print(array[n]) ... n += 1 ... 1 2 3 4 5 >>>
Using less than or equal to will get us an index out of range error because it tries to reference an element in the array’s 5th index position which doesn’t exist.
>>> n = 0 >>> while n <= len(array): ... print(array[n]) ... n += 1 ... 1 2 3 4 5 Traceback (most recent call last): File "<stdin>", line 2, in <module> IndexError: list index out of range
When is it safe to index into an array? (
It is always safe to index into an array when
index<len(array) is true. This is because
len will always be 1 bigger than the maximum available index. By the same reasoning,
index<=len(array) is not safe. This condition could lead to attempting to index the 5th position of an array with only 5 elements. This will lead to an index out of bounds exception.
range(0,len(array)) lead to index out of bounds errors or will it end exactly at the array’s last element?
This is an important question in the Python world because the
range method is commonly used when writing loops. The most important thing to keep in mind is that the
range iterable is inclusive at the bottom of the range but exclusive at the top.
In other words,
range(0,5) will only iterate through the values
[0, 1, 2, 3, 4]. This means that iterating over
range(0,len(array)) elements of an array is safe. It is safe because the value at the top of the range, the second parameter passed into the range function, will not be included in the range itself.
>>> for i in range(0,5): ... print i ... 0 1 2 3 4