DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Array Traversal

What Is Array Traversal?

Traversal means visiting every element in an array — or a defined subset of elements — in a controlled order. It is the most fundamental operation you perform on an array, and nearly every other array algorithm is built on top of it.

The word "visiting" is intentional. Traversal is not just printing. Visiting an element might mean:

›Checking if it satisfies a condition
›Accumulating it into a sum or product
›Comparing it against a running value
›Deciding whether to skip, swap, or transform it

The traversal pattern you choose determines what information is available at each step. Choosing the right pattern for the problem is as important as choosing the right algorithm.

Traversal 1: Forward Traversal (Index-Based)

The most common pattern. Visit every element from index 0 to index length - 1 in order.

Use this when you need both the element's value and its position (index) at the same time. The index lets you look ahead (arr[i+1]), look behind (arr[i-1]), or write to the same position (arr[i] = newValue).

Java

public class ForwardTraversal {

    public static void main(String[] args) {
        int[] prices = {120, 85, 200, 95, 150, 60};

        // Index-based forward traversal
        // Use when you need both value and position
        System.out.println("All prices:");
        for (int i = 0; i < prices.length; i++) {
            System.out.println("  Index " + i + ": " + prices[i]);
        }

        // Count prices above 100
        int count = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] > 100) {
                count++;
            }
        }
        System.out.println("Prices above 100: " + count);
    }
}

Output:
All prices:
  Index 0: 120
  Index 1: 85
  Index 2: 200
  Index 3: 95
  Index 4: 150
  Index 5: 60
Prices above 100: 3

Traversal 2: For-Each (Enhanced For Loop)

When you only need the element's value and do not need to write back to the array or access neighboring elements, a for-each loop is cleaner and less error-prone.

For-each eliminates the index entirely — no off-by-one risk, no boundary to manage.

Java

public class ForEachTraversal {

    public static void main(String[] args) {
        int[] temperatures = {22, 19, 25, 17, 28, 21};

        // For-each — use when you only need values, not positions
        int sum = 0;
        for (int temp : temperatures) {
            sum += temp;
        }

        double average = (double) sum / temperatures.length;
        System.out.println("Sum:     " + sum);
        System.out.printf("Average: %.2f%n", average);

        // Check if any temperature is dangerously high
        boolean dangerousHeat = false;
        for (int temp : temperatures) {
            if (temp > 26) {
                dangerousHeat = true;
                break; // Stop as soon as we find one
            }
        }
        System.out.println("Dangerous heat: " + dangerousHeat);
    }
}

Output:
Sum:     132
Average: 22.00
Dangerous heat: true

Index-Based vs For-Each: When to Use Which

Use index-based (for i = 0 to n-1) when:
  - You need to write back to the array:    arr[i] = newValue
  - You need to look ahead:                 arr[i+1]
  - You need to look behind:                arr[i-1]
  - You need to compare two positions:      arr[i] vs arr[j]
  - You need to traverse two arrays at once

Use for-each when:
  - You only need to read element values
  - No index arithmetic is needed
  - Cleaner, less error-prone code is preferred

Traversal 3: Backward Traversal

Traverse from the last element to the first. Use this when processing order matters and the problem naturally works from right to left — reversing a result, undoing operations, or comparing symmetric positions.

Java

public class BackwardTraversal {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        // Backward traversal — start at length-1, stop at 0 (inclusive)
        System.out.print("Reversed: ");
        for (int i = numbers.length - 1; i >= 0; i--) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();

        // Practical use: find the last even number
        int lastEven = -1;
        for (int i = numbers.length - 1; i >= 0; i--) {
            if (numbers[i] % 2 == 0) {
                lastEven = numbers[i];
                break; // Stop at the first even from the right
            }
        }
        System.out.println("Last even number: " + lastEven);
    }
}

Output:
Reversed: 5 4 3 2 1
Last even number: 4

Dry Run: Backward Traversal on [1, 2, 3, 4, 5]

Array:  [1, 2, 3, 4, 5]
Index:   0  1  2  3  4

i = 4 → arr[4] = 5  → print 5
i = 3 → arr[3] = 4  → print 4
i = 2 → arr[2] = 3  → print 3
i = 1 → arr[1] = 2  → print 2
i = 0 → arr[0] = 1  → print 1

i = -1 → condition i >= 0 is false → loop ends

Output: 5 4 3 2 1

Common mistake: using i > 0 instead of i >= 0
  → skips index 0 → misses the first element

Traversal 4: Partial Traversal (Subarray)

Sometimes you do not need the entire array — only a specific range from index left to index right. This is partial traversal, and it is the foundation of sliding window, divide and conquer, and binary search.

Java

public class PartialTraversal {

    // Traverse a subarray from index left to right (inclusive)
    public static int subarraySum(int[] arr, int left, int right) {
        int sum = 0;

        // Only visit elements within the specified range
        for (int i = left; i <= right; i++) {
            sum += arr[i];
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {3, 7, 1, 8, 4, 5, 2, 9};

        System.out.println("Full array sum:        " + subarraySum(arr, 0, arr.length - 1));
        System.out.println("Sum from index 2 to 5: " + subarraySum(arr, 2, 5));
        System.out.println("Sum from index 4 to 7: " + subarraySum(arr, 4, 7));
    }
}

Output:
Full array sum:        39
Sum from index 2 to 5: 18
Sum from index 4 to 7: 20

Traversal 5: Skipping Elements

Visit every kth element, every even index, every odd index, or any other regular pattern. This appears in problems involving alternating positions, stride-based processing, or specific offsets.

Java

public class SkipTraversal {

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80};

        // Even indices only (0, 2, 4, 6)
        System.out.print("Even indices:  ");
        for (int i = 0; i < arr.length; i += 2) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // Odd indices only (1, 3, 5, 7)
        System.out.print("Odd indices:   ");
        for (int i = 1; i < arr.length; i += 2) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // Every third element (0, 3, 6)
        System.out.print("Every 3rd:     ");
        for (int i = 0; i < arr.length; i += 3) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Output:
Even indices:  10 30 50 70
Odd indices:   20 40 60 80
Every 3rd:     10 40 70

Traversal 6: Traversal with `enumerate` / Index-Value Pairs

When you need both the index and the value simultaneously — especially for tracking positions of elements that satisfy a condition — use index-value traversal. In Python this is enumerate, in Java and C++ it is a standard indexed loop, in JavaScript it is entries().

Java

public class IndexValueTraversal {

    public static void main(String[] args) {
        int[] scores = {72, 88, 55, 91, 63, 77, 48, 95};
        int threshold = 80;

        // Find all indices where score exceeds threshold
        System.out.println("High scorers (score > " + threshold + "):");
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] > threshold) {
                System.out.println("  Student " + i + ": score = " + scores[i]);
            }
        }

        // Find the index of the maximum element
        int maxIndex = 0;
        for (int i = 1; i < scores.length; i++) {
            if (scores[i] > scores[maxIndex]) {
                maxIndex = i;  // Track position, not just value
            }
        }
        System.out.println("Highest scorer: Student " + maxIndex
            + " with score " + scores[maxIndex]);
    }
}

Output:
High scorers (score > 80):
  Student 1: score = 88
  Student 3: score = 91
  Student 7: score = 95
Highest scorer: Student 7 with score 95

Traversal 7: Two-Pointer Traversal

Use one pointer at each end of the array, moving them toward each other. This pattern appears when a problem involves comparing or combining elements from opposite ends — checking palindromes, moving zeros to one end, partitioning around a pivot.

This is not the full two-pointer technique for pair-sum problems (which involves sorted arrays). This is the structural pattern of having two indices converging inward.

Java

public class TwoPointerTraversal {

    // Check if array is a palindrome using two-pointer traversal
    public static boolean isPalindrome(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        // Move both pointers inward, comparing at each step
        while (left < right) {
            if (arr[left] != arr[right]) {
                return false; // Mismatch — not a palindrome
            }
            left++;   // Move left pointer right
            right--;  // Move right pointer left
        }

        return true; // All pairs matched
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 1};
        int[] b = {1, 2, 3, 4, 5};
        int[] c = {5, 5, 5};
        int[] d = {1};

        System.out.println("[1,2,3,2,1] palindrome: " + isPalindrome(a));
        System.out.println("[1,2,3,4,5] palindrome: " + isPalindrome(b));
        System.out.println("[5,5,5]     palindrome: " + isPalindrome(c));
        System.out.println("[1]         palindrome: " + isPalindrome(d));
    }
}

Output:
[1,2,3,2,1] palindrome: true
[1,2,3,4,5] palindrome: false
[5,5,5]     palindrome: true
[1]         palindrome: true

Dry Run: Palindrome Check on [1, 2, 3, 2, 1]

Array:  [1, 2, 3, 2, 1]
         L           R

Step 1: left=0, right=4 → arr[0]=1, arr[4]=1 → match → left=1, right=3
Step 2: left=1, right=3 → arr[1]=2, arr[3]=2 → match → left=2, right=2
Step 3: left=2 >= right=2 → condition false → exit loop

Return true — all symmetric pairs matched

Why left < right (not <=)?
  When left == right, we are at the middle element of an odd-length array.
  A single element always matches itself — no comparison needed.
  Checking it would be wasted work with no correctness benefit.

Handling Edge Cases in Traversal

Every traversal must handle these cases correctly. Forgetting them is the most common source of bugs in array problems.

Empty Array

Before any traversal that makes assumptions about array content, check for empty input:

Java

public class EdgeCases {

    public static int findMax(int[] arr) {
        // Guard: empty array has no maximum
        if (arr.length == 0) {
            throw new IllegalArgumentException("Array is empty");
        }

        int max = arr[0]; // Safe — we know arr has at least one element
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        return max;
    }

    public static void main(String[] args) {
        int[] normal = {3, 1, 7, 2};
        System.out.println("Max of [3,1,7,2]: " + findMax(normal));

        int[] single = {42};
        System.out.println("Max of [42]:      " + findMax(single));

        // Empty array would throw — handle before calling
        int[] empty = {};
        System.out.println("Empty? " + (empty.length == 0 ? "yes, skip" : findMax(empty)));
    }
}

Output:
Max of [3,1,7,2]: 7
Max of [42]:      42
Empty? yes, skip

The Critical Off-By-One Boundaries

FORWARD traversal:
  Correct:   i = 0; i < arr.length      → visits 0, 1, ..., n-1
  Wrong:     i = 0; i <= arr.length     → visits 0, 1, ..., n → CRASH at n
  Wrong:     i = 1; i < arr.length      → skips index 0 (first element)

BACKWARD traversal:
  Correct:   i = arr.length - 1; i >= 0 → visits n-1, n-2, ..., 0
  Wrong:     i = arr.length;     i >= 0 → starts at arr[n] → OUT OF BOUNDS
  Wrong:     i = arr.length - 1; i > 0  → skips index 0 (first element)

PARTIAL traversal (left to right inclusive):
  Correct:   i = left; i <= right        → visits left, left+1, ..., right
  Wrong:     i = left; i < right         → misses arr[right] (off by one)

TWO-POINTER converging:
  Correct:   while (left < right)        → stops when pointers meet or cross
  Wrong:     while (left <= right)       → compares middle element to itself (harmless
                                           but unnecessary; logic depends on problem)

Traversal Pattern Summary

Pattern	Loop Style	When to Use
Forward index-based	`for i = 0 to n-1`	Need index, write-back, or look-ahead
Forward for-each	`for each x in arr`	Only need values, no index needed
Backward	`for i = n-1 to 0`	Right-to-left processing, finding last match
Partial	`for i = left to right`	Subarrays, divide and conquer, binary search
Skipping	`i += k` in loop	Every kth element, alternating positions
Index-value pairs	`enumerate` / `entries()`	Need both index and value cleanly
Two-pointer converging	`left++, right--`	Palindrome, symmetric comparison, partitioning

Interview Questions

Q: When should you use a for-each loop versus an index-based for loop?

Use for-each when you only need to read element values and the index is irrelevant. It is cleaner and eliminates the risk of off-by-one errors. Use an index-based for loop when you need to write back to the array (arr[i] = value), access neighboring elements (arr[i+1]), traverse two arrays simultaneously using the same index, or use the index as part of the computation.

Q: How do you find the index of the maximum element, not just the maximum value?

Track maxIndex initialized to 0, and update it whenever you find a larger value. After traversal, arr[maxIndex] is the maximum value and maxIndex is its position. Never use a for-each loop for this — you need the index, which for-each does not expose.

Q: What is the correct loop boundary for backward traversal?

Start at arr.length - 1 (last valid index) and use i >= 0 as the stopping condition (inclusive of index 0). A common mistake is using i > 0 which misses the element at index 0, or starting at arr.length which accesses one past the end.

Q: How does two-pointer traversal reduce work compared to nested loops?

Nested loops check every combination — O(n²) comparisons. Two-pointer traversal uses one pointer from each end and moves them inward based on a comparison — O(n) comparisons total. Each pointer moves at most n times, and together they cover all necessary comparisons without redundancy. This works because the structure of the problem (symmetric comparison, sorted order) means you can eliminate large sections of the search space with each step.

FAQs

What is the difference between range(n) and range(len(arr)) in Python?

range(n) generates indices 0 through n-1 when n is a known constant. range(len(arr)) generates the same indices dynamically based on the array's actual length. Always use range(len(arr)) when traversing an array — it is correct regardless of array size. Using range(n) with a hardcoded n is fragile and breaks if the array changes size.

Why does Python's enumerate start at 0 by default, and can you change it?

enumerate(arr) produces (0, arr[0]), (1, arr[1]), .... You can change the starting index with enumerate(arr, start=1) to get (1, arr[0]), (2, arr[1]), .... This is useful when displaying "Student 1" through "Student n" to users, but for algorithmic purposes always use 0-based indexing.

Is it safe to modify an array while traversing it?

Modifying elements at the current index or positions you have already passed is safe. Modifying the length of the array during traversal (inserting or removing elements) is dangerous — it shifts elements and invalidates your index. In Python, never use list.remove() or list.insert() inside a for i in range(len(arr)) loop. In Java, never modify an ArrayList's size inside a for-each loop — use an index-based loop instead or collect changes and apply them after traversal.

When should you break out of a traversal early?

When the problem asks for the first occurrence of something (first element matching a condition, first duplicate, first index where a value appears). Once found, further traversal is wasted work. Always break or return immediately upon finding the answer. Continuing to traverse wastes O(n) time that could be O(1) in the best case.

Quick Quiz

Question 1: You need to find the index of the last element greater than 50 in an array. Which traversal is most efficient?

›A) Forward traversal, record every matching index, return the last one
›B) Backward traversal, return the first matching index found
›C) For-each loop, track the matching value
›D) Two-pointer traversal from both ends

Answer: B) Backward traversal, return the first match found. Traversing from right to left, the first element you find that is greater than 50 is the last such element in forward order. Break immediately — O(1) best case. Forward traversal with tracking finds the correct answer but cannot break early, costing O(n) in all cases.

Question 2: What is wrong with this loop: for (int i = 0; i <= arr.length; i++)?

›A) It starts at the wrong index
›B) It accesses arr[arr.length] which is out of bounds
›C) It skips the last element
›D) Nothing — it is correct

Answer: B) It accesses arr[arr.length] which is out of bounds. Valid indices run from 0 to arr.length - 1. When i == arr.length, accessing arr[i] reaches one past the end of the array. The correct condition is i < arr.length.

Question 3: You want to visit elements at indices 2, 4, 6, 8 in an array of length 10. What is the correct loop?

›A) for i = 0 to 9, if i % 2 == 0
›B) for i = 2; i < 10; i += 2
›C) for i = 1; i < 10; i += 2
›D) for i = 0; i < 10; i++ and check i > 1

Answer: B) for i = 2; i < 10; i += 2. Start at index 2, stop before index 10, increment by 2. This visits exactly indices 2, 4, 6, 8. Option A also works but wastes half the iterations checking the condition.

Question 4: In the two-pointer palindrome check, why is the stopping condition left < right rather than left <= right?

›A) To avoid an infinite loop
›B) When left == right, both pointers are at the middle element — comparing it to itself is unnecessary
›C) To prevent out-of-bounds access
›D) left <= right would give wrong results

Answer: B) When left == right, both pointers are at the middle element — comparing it to itself is unnecessary. The middle element of an odd-length array always matches itself. Stopping at left < right correctly handles both odd-length arrays (stops at the middle) and even-length arrays (stops when pointers cross). The result is correct either way, but left < right avoids one unnecessary comparison.

Summary

Array traversal is the foundation of every array algorithm. The pattern you choose controls what information is available at each step and how efficiently the algorithm runs.

The key traversal patterns to carry forward:

›Forward index-based (for i = 0; i < n; i++) — when you need index, write-back, or look-ahead
›Forward for-each (for each x in arr) — when only values are needed, cleaner and safer
›Backward (for i = n-1; i >= 0; i--) — right-to-left, finding last occurrence, reverse processing
›Partial (for i = left; i <= right; i++) — subarrays, divide and conquer, range operations
›Skipping (i += k) — every kth element, alternating positions
›Index-value pairs (enumerate, entries()) — clean access to both index and value
›Two-pointer converging (left++, right--) — symmetric comparison, partitioning

Always verify two boundaries before traversal: is the array empty, and are the loop bounds correct? Off-by-one errors and empty-array crashes are the two most common traversal bugs in every interview and every codebase.

In the next topic, you will explore Array Operations — insert, delete, search, and update with their true time complexities and the implementation details that matter in interviews.

←

PreviousHow Arrays Work in Memory

NextArray Operations

→