Index-Based Traversal of 1D Arrays in Python

Tuhin Paul
1d
257
0
2

Article

What Is Array Traversal?

In computer science, array traversal refers to the process of visiting each element of an array exactly once in a systematic order. It is one of the most fundamental operations performed on arrays and forms the backbone of countless algorithms—from searching and sorting to dynamic programming and graph traversal.

In Python, while we often work with lists (which are dynamic arrays), the concept of traversal remains the same: accessing each element sequentially to read, modify, or analyze it.

Index-Based vs Direct Iteration in Python

Python offers two primary ways to traverse a list:

Direct iteration (Pythonic way)
```
 for item in my_list:
    print(item)
```
This is clean, readable, and efficient when you only need the values.
Index-based traversal

for i in range(len(my_list)):
    print(i, my_list[i])

This gives you explicit access to both the index and the value, which is essential in many algorithmic scenarios.

Why Understanding Traversal Matters for Algorithm Design

Index-based traversal is critical when:

You need to compare or modify elements based on their positions (e.g., arr[i] and arr[i+1]).
You're implementing algorithms like bubble sort, sliding window, or two-pointer techniques.
You must return indices (e.g., in search problems like “find the index of the first occurrence”).
You're working with multiple arrays simultaneously and need synchronized indices.

Mastering index-based traversal builds the foundation for more advanced algorithmic thinking.

Different Ways to Traverse a 1D Array Using Index

1. Using a `for` Loop with `range(len(array))`

This is the most common method for index-based traversal. It iterates from index 0 to len(array) - 1.

def traverse_forward_with_index(arr):
    """Traverse array from start to end using index."""
    for i in range(len(arr)):
        print(f"Index: {i}, Value: {arr[i]}")

2. Using a `while` Loop with an Index Variable

A while loop offers more control, especially when the traversal logic is conditional.

def traverse_with_while(arr):
    """Traverse using a while loop and manual index management."""
    i = 0
    while i < len(arr):
        print(f"Index: {i}, Value: {arr[i]}")
        i += 1

3. Traversal with Step Values

You can skip elements using a step parameter in range(start, stop, step).

def traverse_with_step(arr, step=2):
    """Traverse every 'step'-th element."""
    for i in range(0, len(arr), step):
        print(f"Index: {i}, Value: {arr[i]}")

4. Reverse Traversal Using Index

Sometimes you need to process elements from the end to the beginning.

def traverse_reverse(arr):
    """Traverse array from last index to first."""
    for i in range(len(arr) - 1, -1, -1):
        print(f"Index: {i}, Value: {arr[i]}")

Real-Time Scenario: Stock Price Analysis

Problem Statement

You are given a list of daily stock prices. You need to find the maximum profit that can be achieved by buying on one day and selling on a later day. If no profit is possible, return 0.

Why index-based traversal?
Because you must compare each price with all future prices, which requires knowing both current and future indices to enforce the "buy before sell" rule.

Solution Using Index-Based Traversal

def max_profit(prices):
    """
    Find maximum profit from buying and selling stock once.
    Uses index-based traversal to compare each day with future days.
    
    Args:
        prices (list): List of daily stock prices.
    
    Returns:
        int: Maximum profit possible.
    """
    max_profit_val = 0
    n = len(prices)
    
    # Traverse each day as potential buy day
    for buy_day in range(n):
        # Traverse all future days as potential sell days
        for sell_day in range(buy_day + 1, n):
            profit = prices[sell_day] - prices[buy_day]
            if profit > max_profit_val:
                max_profit_val = profit
                
    return max_profit_val

Note: While this is O(n²), it clearly demonstrates the need for index-based traversal. A more efficient O(n) solution exists, but even that often uses index tracking.

Algorithmic Analysis

Time Complexity

Forward/Reverse/Step Traversal:
Each element is visited once → O(n) time, where n = len(array).
Nested Traversal (e.g., max_profit):
In worst case, visits ~n²/2 pairs → O(n²) time.

Space Complexity

All traversal methods use only a constant amount of extra space (for index variables, loop counters, etc.).
No additional data structures proportional to input size are created.
→ O(1) auxiliary space complexity.

Key Insight: Traversal itself is inherently linear in time and constant in space, making it highly efficient.

Python Code Examples (Complete Implementation)

def traverse_forward(arr):
    """Standard forward traversal using index."""
    result = []
    for i in range(len(arr)):
        result.append((i, arr[i]))
    return result

def traverse_reverse(arr):
    """Reverse traversal using index."""
    result = []
    for i in range(len(arr) - 1, -1, -1):
        result.append((i, arr[i]))
    return result

def traverse_step(arr, step=2):
    """Traversal with custom step size."""
    if step <= 0:
        raise ValueError("Step must be positive")
    result = []
    for i in range(0, len(arr), step):
        result.append((i, arr[i]))
    return result

def max_profit(prices):
    """Real-world example: max profit from stock prices."""
    if len(prices) < 2:
        return 0
        
    max_profit_val = 0
    n = len(prices)
    
    for buy_day in range(n):
        for sell_day in range(buy_day + 1, n):
            profit = prices[sell_day] - prices[buy_day]
            max_profit_val = max(max_profit_val, profit)
            
    return max_profit_val

Test Cases

We’ll use simple assert statements for clarity and brevity.

# Test Case 1: Forward traversal
arr1 = [10, 20, 30]
expected_forward = [(0, 10), (1, 20), (2, 30)]
assert traverse_forward(arr1) == expected_forward

# Test Case 2: Reverse traversal
expected_reverse = [(2, 30), (1, 20), (0, 10)]
assert traverse_reverse(arr1) == expected_reverse

# Test Case 3: Step traversal
arr2 = [1, 2, 3, 4, 5, 6]
expected_step = [(0, 1), (2, 3), (4, 5)]
assert traverse_step(arr2, step=2) == expected_step

# Test Case 4: Empty array
empty = []
assert traverse_forward(empty) == []
assert traverse_reverse(empty) == []
assert traverse_step(empty, step=1) == []

# Test Case 5: Real-world scenario
assert max_profit([7, 1, 5, 3, 6, 4]) == 5  # Buy at 1, sell at 6
assert max_profit([7, 6, 4, 3, 1]) == 0     # Prices only fall
assert max_profit([1]) == 0                 # Only one day
assert max_profit([]) == 0                  # No data

print(" All test cases passed!")

Conclusion

Best Practices for Index-Based Traversal

Prefer direct iteration (for item in arr) when you only need values— it’s more Pythonic and readable.
Use index-based traversal when:
- You need both index and value (enumerate() is often better—see note below).
- You’re modifying the array during iteration.
- You’re comparing or accessing neighboring/specific elements by position.
Avoid manual index management with while unless necessary—it’s error-prone (off-by-one bugs).
Always validate array bounds if using dynamic indices.

When to Use Index vs Direct Iteration

Scenario	Recommended Approach
Print all values	Direct iteration
Modify elements in-place	Index-based or`enumerate`
Compare`arr[i]`and`arr[i+1]`	Index-based
Find index of target	Index-based
Process every 3rd element	Index with step
Reverse processing	Reverse index traversal

Mastering index-based traversal equips you with the precision needed for algorithm design, while respecting Python’s idioms ensures your code remains clean and maintainable. Use the right tool for the job—and now you know them all.