7a:T6e5,# Forward Traversal: The Fundamental Pattern # ========================================== def forward_traversal_basic(arr): """ Visit each element from index 0 to len(arr)-1. This is the most fundamental array operation. Time Complexity: O(n) - each element visited exactly once Space Complexity: O(1) - only index variable used """ n = len(arr) for i in range(n): # Process the element at index i print(f"Index {i}: {arr[i]}") def forward_traversal_with_accumulation(arr): """ Accumulate a result while traversing forward. Example: Computing the sum of all elements. This pattern demonstrates state management during traversal. """ n = len(arr) total = 0 # Initialize accumulator before loop for i in range(n): total += arr[i] # Update accumulator at each step return total # Return accumulated result def forward_traversal_find_max(arr): """ Find the maximum element by forward traversal. Key insight: We maintain an invariant—at any point, 'current_max' holds the maximum of all elements seen so far. """ if len(arr) == 0: raise ValueError("Cannot find max of empty array") current_max = arr[0] # Initialize with first element for i in range(1, len(arr)): # Start from 1, already processed 0 if arr[i] > current_max: current_max = arr[i] return current_max # Example usage demonstrating the pattern if __name__ == "__main__": data = [5, 2, 9, 1, 7, 6, 3] print("Forward Traversal:") forward_traversal_basic(data) print(f" Sum: {forward_traversal_with_accumulation(data)}") print(f"Max: {forward_traversal_find_max(data)}")7b:T9ed,# Backward Traversal: The Reverse Pattern # ======================================== def backward_traversal_basic(arr): """ Visit each element from index len(arr)-1 down to 0. Elements are processed in reverse order. Time Complexity: O(n) - same as forward traversal Space Complexity: O(1) - only index variable used """ n = len(arr) for i in range(n - 1, -1, -1): # Start at n-1, end before -1, step -1 # Process the element at index i print(f"Index {i}: {arr[i]}") def backward_traversal_safe_removal(arr, predicate): """ Remove elements matching a predicate while traversing. CRITICAL PATTERN: When removing elements during traversal, you MUST traverse backward to avoid index invalidation. If traversing forward and removing, indices shift and you skip elements. Backward traversal avoids this problem. """ result = arr.copy() # Work on a copy to demonstrate # Traverse backward - safe for in-place removal for i in range(len(result) - 1, -1, -1): if predicate(result[i]): result.pop(i) # Remove element at index i return result def backward_traversal_find_last(arr, target): """ Find the LAST occurrence of target in the array. When you need the last match, backward traversal is natural. The first match you find IS the last occurrence. """ for i in range(len(arr) - 1, -1, -1): if arr[i] == target: return i # Return immediately - this is the last occurrence return -1 # Not found def backward_traversal_reverse_in_place(arr): """ Reverse array in-place using backward traversal to build result. Note: This specific implementation uses O(n) extra space. True in-place reversal uses two pointers (covered later). """ n = len(arr) result = [] for i in range(n - 1, -1, -1): result.append(arr[i]) return result # Example: Why backward traversal matters for removal if __name__ == "__main__": data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] print("Original:", data) print("Backward traversal:") backward_traversal_basic(data) # Remove even numbers - must traverse backward! filtered = backward_traversal_safe_removal(data, lambda x: x % 2 == 0) print(f" After removing evens: {filtered}") # Find last occurrence test = [1, 2, 3, 2, 4, 2, 5] print(f" Last occurrence of 2 in {test}: index {backward_traversal_find_last(test, 2)}")7c:Tc31,# Understanding Index Mechanics in Depth # ====================================== def demonstrate_index_phases(arr): """ Explicitly shows the three phases of each loop iteration. Understanding these phases prevents off-by-one errors. """ n = len(arr) i = 0 # Initialization happens once, before the loop while True: # PHASE 1: Check condition (beginning of each iteration) if not (i < n): print(f" Condition i < n is FALSE (i={i}, n={n}). Loop terminates.") break print(f" Condition i < n is TRUE (i={i}, n={n}). Entering body.") # PHASE 2: Execute body print(f" Processing element at index {i}: {arr[i]}") # PHASE 3: Update index (end of each iteration) i += 1 print(f" Index updated to {i}") print() def common_off_by_one_mistakes(): """ Catalog of common mistakes and their corrections. """ arr = [10, 20, 30, 40, 50] n = len(arr) # MISTAKE 1: Using <= instead of < for forward traversal # for i in range(n + 1): # WRONG! Will cause IndexError # print(arr[i]) # CORRECT: for i in range(n): # i goes from 0 to n-1 pass # arr[i] is valid # MISTAKE 2: Starting backward traversal at n instead of n-1 # for i in range(n, 0, -1): # WRONG! Misses index 0, includes invalid index n # print(arr[i]) # CORRECT: for i in range(n - 1, -1, -1): # i goes from n-1 to 0 pass # arr[i] is valid # MISTAKE 3: Forgetting that range end is exclusive # for i in range(1, n - 1): # Processes indices 1 to n-2, SKIPS 0 and n-1 # print(arr[i]) # CORRECT (if you want all elements): for i in range(0, n): # Or just range(n) pass def boundary_analysis(arr): """ Explicit boundary analysis for verifying correctness. For any traversal pattern, verify: 1. First element processed is correct 2. Last element processed is correct 3. No element is processed twice 4. No element is skipped 5. No out-of-bounds access occurs """ n = len(arr) if n == 0: print("Empty array: No iterations occur") return # Forward traversal boundary check print("Forward traversal:") first_index = 0 last_index = n - 1 print(f" First iteration: i=0, accesses arr[0]={arr[0]}") print(f" Last iteration: i={n-1}, accesses arr[{n-1}]={arr[n-1]}") print(f" Total iterations: {n}") # Backward traversal boundary check print(" Backward traversal:") first_index = n - 1 last_index = 0 print(f" First iteration: i={n-1}, accesses arr[{n-1}]={arr[n-1]}") print(f" Last iteration: i=0, accesses arr[0]={arr[0]}") print(f" Total iterations: {n}") # Example showing these concepts if __name__ == "__main__": test_array = ['A', 'B', 'C', 'D'] print("=== Demonstrating Index Phases ===") demonstrate_index_phases(test_array) print(" === Boundary Analysis ===") boundary_analysis(test_array)72:{"json":{"id":"seed_48f6b3fa09c0ae4fde0434e04f0994ec","slug":"array-traversal-patterns","category":"Data Structures & Algorithms","topic":"Array Traversal Patterns","title":"Array Traversal Patterns","description":"Master the fundamental patterns for traversing arrays—the most essential operation you'll perform countless times in your programming career. Learn forward and backward traversal, early termination strategies, and techniques for collecting, transforming, and building output during traversal.","difficulty":"BEGINNER","estimatedMinutes":60,"pages":[{"id":"seed_f458c39a5eae56ce24dc471045939f2c","title":"Linear Traversal (Forward and Backward)","order":0,"content":[{"id":"opening-hook","title":"The Foundation of Every Array Algorithm","content":[{"data":{"content":"Every algorithm that operates on arrays shares one fundamental operation: **traversal**—the act of visiting each element in a systematic order. Whether you're searching for a value, computing a sum, finding a maximum, filtering elements, or transforming data, you must first traverse the array.\n\nTraversal is so fundamental that experienced programmers often take it for granted. Yet a deep understanding of traversal mechanics—how elements are accessed, why order matters, what invariants hold during iteration, and how traversal direction affects algorithm design—forms the bedrock upon which all sophisticated array algorithms are built.\n\nIn this page, we'll explore linear traversal with the rigor it deserves, examining both forward and backward patterns, their applications, performance characteristics, and the subtle details that separate competent engineers from exceptional ones."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the mechanics of forward and backward traversal at a deep level, know when to use each direction, recognize the invariants that hold during iteration, and apply these patterns confidently to solve real-world problems. You'll also understand why traversal—despite its apparent simplicity—is the foundation of algorithmic thinking.","variant":"info"},"type":"callout"}]},{"id":"what-is-traversal","title":"What Is Array Traversal?","content":[{"data":{"content":"**Array traversal** is the process of visiting each element of an array exactly once, in a specific order, to perform some operation. This operation might be reading a value, updating it, comparing it against a target, accumulating a result, or making a decision.\n\nAt its core, traversal answers the question: *How do I examine every element in this collection?*\n\nWhile this seems elementary, traversal is actually a remarkably powerful concept. Consider that virtually every array-based algorithm can be decomposed into:\n\n1. **Traversal pattern** — How do we visit elements?\n2. **Per-element operation** — What do we do at each element?\n3. **State accumulation** — What do we remember as we proceed?\n4. **Termination condition** — When do we stop?\n\nThe choices you make for each of these determine your algorithm's correctness, efficiency, and elegance."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Traversal as a Building Block","content":"Think of traversal patterns as reusable templates. Once you internalize forward traversal, backward traversal, and their variants, you can focus on the unique logic of each problem rather than reinventing the iteration mechanics every time.","variant":"tip"},"type":"callout"},{"data":{"content":"**Formal Definition:**\n\nGiven an array `A` of `n` elements indexed from `0` to `n-1`, traversal involves:\n\n- Initializing an index variable (e.g., `i = 0` for forward traversal)\n- Visiting the element at the current index (`A[i]`)\n- Updating the index to move to the next element (`i++` or `i--`)\n- Repeating until a boundary condition is met (`i < n` or `i >= 0`)\n\nThis simple loop structure—initialize, visit, update, check—is the skeleton upon which all array algorithms are built."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"forward-traversal","title":"Forward Traversal: From Start to End","content":[{"data":{"content":"**Forward traversal** visits elements from the first index (0) to the last index (n-1), processing them in their natural, stored order. This is the most common and intuitive traversal pattern, matching how humans naturally read from left to right.\n\n**The Canonical Forward Traversal Pattern:**\n\n```\nfor i = 0 to n-1:\n process(A[i])\n```\n\nThis pattern guarantees:\n- Every element is visited exactly once\n- Elements are visited in index order: A[0], A[1], A[2], ..., A[n-1]\n- The loop terminates after n iterations"},"type":"text"},{"data":{"code":"$7a","fileName":"forward_traversal.py","showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"The Loop Invariant","content":"A **loop invariant** is a condition that holds true before and after each iteration. For forward traversal: \"All elements from A[0] to A[i-1] have been processed.\" At the start (i=0), no elements have been processed (vacuously true). After each iteration, one more element has been processed. At termination (i=n), all elements have been processed. This reasoning proves correctness.","variant":"note"},"type":"callout"},{"data":{"content":"**When to Use Forward Traversal:**\n\nForward traversal is the default choice when:\n\n- **Order doesn't matter:** You're computing aggregates (sum, average, count) where processing order is irrelevant\n- **Natural order is required:** You're building output that should match input order\n- **Dependencies flow forward:** Each computation depends on previously visited elements\n- **Reading/displaying data:** Presenting array contents in their stored sequence\n- **Finding first occurrence:** You want the earliest element matching some condition\n\nForward traversal leverages **spatial locality**—accessing consecutive memory addresses, which is cache-friendly and maximizes hardware efficiency on modern processors."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"backward-traversal","title":"Backward Traversal: From End to Start","content":[{"data":{"content":"**Backward traversal** visits elements from the last index (n-1) to the first index (0), processing them in reverse order. While less common than forward traversal, this pattern is essential for many algorithms and sometimes the only correct approach.\n\n**The Canonical Backward Traversal Pattern:**\n\n```\nfor i = n-1 down to 0:\n process(A[i])\n```\n\nThis pattern guarantees:\n- Every element is visited exactly once\n- Elements are visited in reverse index order: A[n-1], A[n-2], ..., A[0]\n- The loop terminates after n iterations"},"type":"text"},{"data":{"code":"$7b","fileName":"backward_traversal.py","showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Critical Pattern: Removing Elements During Traversal","content":"When you need to remove elements while iterating, ALWAYS traverse backward. If you traverse forward and remove an element, all subsequent indices shift down by one, causing you to skip the next element. Backward traversal avoids this entirely because removals only affect indices you've already processed.","variant":"warning"},"type":"callout"},{"data":{"content":"**When to Use Backward Traversal:**\n\nBackward traversal is the correct choice when:\n\n- **Removing elements:** Indices of later elements don't shift when earlier elements are removed\n- **Building reversed output:** Natural way to reverse without extra data structures\n- **Finding last occurrence:** First match in reverse order is the last match in forward order\n- **Dependencies flow backward:** Each computation depends on elements to the right\n- **Stack-like processing:** Last-in-first-out ordering is required\n- **Processing from most recent:** When newer elements (often at the end) have priority\n\n**Common algorithms using backward traversal:**\n\n- **Suffix computations** — suffix sums, suffix products\n- **Right-to-left dynamic programming** — when recurrence looks rightward\n- **Histogram problems** — computing spans looking backward\n- **Undo operations** — reversing a sequence of changes\n- **Garbage collection** — processing from end to avoid shifting"},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"index-management","title":"The Mechanics of Index Management","content":[{"data":{"content":"Understanding the precise mechanics of index management is crucial for writing correct traversal code. Many bugs stem from off-by-one errors, incorrect bounds, or misunderstanding when the index is updated.\n\n**Key Index Properties:**"},"type":"text"},{"data":{"rows":[["Starting index","0","n-1"],["Ending index (inclusive)","n-1","0"],["Continuation condition","i < n","i >= 0"],["Index update","i++","i--"],["Elements visited","n","n"]],"headers":["Property","Forward","Backward"]},"type":"table"},{"data":{"content":"**The Three Phases of Each Iteration:**\n\n1. **Check condition** — Is the loop done?\n2. **Execute body** — Process current element\n3. **Update index** — Move to next element"},"type":"text"},{"data":{"code":"$7c","fileName":"index_mechanics.py","showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"The 0/n-1 Rule","content":"A helpful mnemonic: **Forward starts at 0, ends before n. Backward starts at n-1, ends at 0 (inclusive).** The asymmetry arises because we use 0-based indexing but measure length starting from 1. When writing loops, mentally verify: \"What's the first index? What's the last index? Does my condition include both?\"","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"complexity-analysis","title":"Time and Space Complexity of Traversal","content":[{"data":{"content":"Understanding the complexity of traversal is fundamental to analyzing any array algorithm. Since traversal is a building block, its complexity directly affects the complexity of algorithms that use it.\n\n**Time Complexity: O(n)**\n\nA single traversal of an array with n elements requires exactly n iterations. Each iteration:\n- Accesses one element: O(1)\n- Performs a constant amount of work: O(1)\n\nTotal: n × O(1) = O(n)\n\nThis linear time complexity is **optimal for problems requiring examination of all elements** because you cannot determine properties of unseen elements. Any algorithm that must verify every element cannot be faster than O(n).\n\n**Space Complexity: O(1)**\n\nBasic traversal requires only a constant amount of extra space:\n- One index variable (e.g., `i`)\n- Possibly a few accumulator variables\n\nThe input array itself doesn't count toward space complexity (it's the input, not additional space)."},"type":"text"},{"data":{"rows":[["Single forward traversal","O(n)","O(1)","Visit each element once"],["Single backward traversal","O(n)","O(1)","Same as forward, different order"],["Find min/max","O(n)","O(1)","Must check every element"],["Compute sum/average","O(n)","O(1)","Single pass accumulation"],["Count occurrences","O(n)","O(1)","Count matches while traversing"],["Find all occurrences","O(n)","O(k)","k = number of matches found"],["Build output array","O(n)","O(n)","Output size proportional to input"],["Nested traversal","O(n²)","O(1)","For each element, traverse again"]],"caption":"Complexity of Common Traversal Operations","headers":["Operation","Time","Space","Notes"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"Hidden Complexity Trap","content":"Watch for operations inside the loop that aren't O(1). For example, if you call a function that itself traverses the array inside your loop, you get O(n) × O(n) = O(n²) total time. Similarly, operations like list concatenation in Python (list1 + list2) are O(m) where m is the length of list2, which can silently turn your O(n) traversal into O(n²).","variant":"warning"},"type":"callout"},{"data":{"content":"**Why O(n) Is Often Optimal:**\n\nFor many problems, O(n) is not just common—it's provably optimal. Consider:\n\n- **Finding the maximum:** Without checking every element, you might miss the actual maximum\n- **Computing a sum:** Every element contributes, so all must be visited\n- **Searching unsorted data:** The target might be anywhere\n\nThese problems have an **information-theoretic lower bound** of Ω(n), meaning no algorithm can solve them faster than linear time in the worst case. When you achieve O(n) for such problems, you're optimal.\n\nHowever, for problems where the answer depends on only a subset of elements, or where the data has structure (like being sorted), faster approaches exist. Recognizing when O(n) is necessary versus when it can be beaten is a crucial skill."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"real-world-applications","title":"Real-World Applications of Linear Traversal","content":[{"data":{"content":"Linear traversal appears in virtually every software system. Understanding these applications helps you recognize traversal patterns in real problems and appreciate why this fundamental skill matters beyond academic exercises."},"type":"text"},{"data":{"items":["**Log Processing** — Scanning log entries chronologically to compute statistics, detect patterns, or find anomalies. Logs are typically ordered by timestamp, and forward traversal respects this temporal ordering.","**Stream Processing** — Processing data streams (sensor readings, network packets, user events) in arrival order. Each element may depend on previous elements for windowed computations.","**Rendering Pipelines** — Drawing elements in order for correct layering. Forward traversal ensures background elements are rendered before foreground elements.","**Cumulative Statistics** — Computing running totals, moving averages, or cumulative distributions. Each step builds on previous computations.","**Validation Passes** — Checking each field in a form, each row in a dataset, or each configuration value against rules."],"title":{"icon":"Target","text":"Applications of Forward Traversal","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"items":["**Undo Systems** — Processing action history from most recent to oldest. The last action performed is the first to be undone.","**Memory Deallocation** — Freeing resources in reverse order of allocation to avoid premature invalidation of references.","**Stack Trace Processing** — Analyzing call stacks from innermost (most recent) to outermost (oldest) function call.","**Version Rollback** — Reverting changes by applying inverse operations from newest to oldest.","**Right-to-Left Text Processing** — Handling RTL languages (Arabic, Hebrew) where natural reading order requires backward processing of certain elements."],"title":{"icon":"Zap","text":"Applications of Backward Traversal","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Sparkles","title":"Pattern Recognition","content":"When approaching a new problem, ask: **Does order matter?** If yes, does the problem naturally proceed from first-to-last or last-to-first? Does any element's processing depend on already-processed elements? The answers guide your choice of traversal direction.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"decision-framework","title":"Choosing Between Forward and Backward Traversal","content":[{"data":{"content":"While forward traversal is the default, there are specific situations where backward traversal is required or preferable. Developing a mental framework for this choice improves both code correctness and elegance."},"type":"text"},{"data":{"left":[{"data":{"items":["Computing aggregates (sum, count, average)","Output should match input order","Finding first occurrence","Building prefix computations","No modifications to the array","Dependencies flow left-to-right","No strong reason for reverse"],"title":{"icon":"CheckCircle","text":"Use Forward Traversal When","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Removing elements during iteration","Finding last occurrence","Building suffix computations","Reversing without extra space","Processing most-recent-first","Dependencies flow right-to-left","Stack-like (LIFO) semantics needed"],"title":{"icon":"Zap","text":"Use Backward Traversal When","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"The Modification Rule","content":"If you're modifying the array structure (adding/removing elements) during traversal, think carefully about how indices shift. Backward traversal when removing, forward traversal (with careful index management) when inserting, are common safe patterns.","variant":"tip"},"type":"callout"},{"data":{"content":"**When Either Works:**\n\nFor many problems, both directions produce correct results. In these cases:\n\n1. **Prefer forward traversal** — It's more intuitive and conventional\n2. **Consider cache locality** — Both are similar, but forward may have slight edge\n3. **Match the problem's natural framing** — If the problem statement describes left-to-right processing, use forward\n4. **Consider readability** — Choose whichever makes the code's intent clearer\n\nThe key insight is that traversal direction is a *tool*, not a rigid rule. Understanding both patterns lets you select the appropriate one for each situation."},"type":"text"}],"titleType":"number","titleNumber":7},{"id":"common-patterns","title":"Common Traversal Patterns and Idioms","content":[{"data":{"content":"Experienced programmers recognize recurring patterns that combine basic traversal with specific operations. These idioms appear frequently and are worth committing to memory."},"type":"text"},{"data":{"tabs":[{"id":"accumulation","label":"Accumulation","content":[{"data":{"content":"**Accumulation** computes a single result from all elements. Initialize an accumulator before the loop, update it in each iteration, and return it after."},"type":"text"},{"data":{"code":"# Accumulation Pattern Examples\n\ndef sum_elements(arr):\n \"\"\"Basic accumulation: sum\"\"\"\n total = 0 # Initialize accumulator\n for x in arr:\n total += x # Update accumulator\n return total # Return result\n\ndef product_elements(arr):\n \"\"\"Accumulation: product (note: start at 1, not 0)\"\"\"\n product = 1\n for x in arr:\n product *= x\n return product\n\ndef find_min_max(arr):\n \"\"\"Accumulation: track multiple values\"\"\"\n if not arr:\n return None, None\n min_val = max_val = arr[0]\n for x in arr[1:]:\n if x < min_val:\n min_val = x\n if x > max_val:\n max_val = x\n return min_val, max_val","showLineNumbers":true},"type":"code"}],"titleIcon":"Target"},{"id":"search","label":"Search","content":[{"data":{"content":"**Search** finds an element or position matching criteria. Return immediately upon finding, or return a sentinel (like -1) if not found."},"type":"text"},{"data":{"code":"# Search Pattern Examples\n\ndef linear_search(arr, target):\n \"\"\"Find first index of target, or -1\"\"\"\n for i in range(len(arr)):\n if arr[i] == target:\n return i # Found - return immediately\n return -1 # Not found\n\ndef find_first_match(arr, predicate):\n \"\"\"Find first element satisfying predicate\"\"\"\n for x in arr:\n if predicate(x):\n return x\n return None\n\ndef find_all_indices(arr, target):\n \"\"\"Find ALL indices (uses accumulation too)\"\"\"\n indices = [] # Accumulate matching indices\n for i in range(len(arr)):\n if arr[i] == target:\n indices.append(i)\n return indices\n\n# Usage\ndata = [3, 1, 4, 1, 5, 9, 2, 6]\nprint(find_all_indices(data, 1)) # [1, 3]","showLineNumbers":true},"type":"code"}],"titleIcon":"Target"},{"id":"existence","label":"Existence Check","content":[{"data":{"content":"**Existence checks** determine if any/all elements satisfy a condition. \"Any\" returns True early on first match. \"All\" returns False early on first non-match."},"type":"text"},{"data":{"code":"# Existence Check Patterns\n\ndef contains_any(arr, predicate):\n \"\"\"True if ANY element satisfies predicate\"\"\"\n for x in arr:\n if predicate(x):\n return True # Found one - short-circuit\n return False # None found\n\ndef contains_all(arr, predicate):\n \"\"\"True if ALL elements satisfy predicate\"\"\"\n for x in arr:\n if not predicate(x):\n return False # Found counter-example\n return True # All passed\n\ndef contains_none(arr, predicate):\n \"\"\"True if NO element satisfies predicate\"\"\"\n return not contains_any(arr, predicate)\n\n# Examples\nnumbers = [2, 4, 6, 8, 10]\nprint(contains_all(numbers, lambda x: x % 2 == 0)) # True\nprint(contains_any(numbers, lambda x: x > 7)) # True\nprint(contains_none(numbers, lambda x: x < 0)) # True","showLineNumbers":true},"type":"code"}],"titleIcon":"CheckCircle"},{"id":"comparison","label":"Adjacent Comparison","content":[{"data":{"content":"**Adjacent comparison** compares each element with its neighbor. Useful for detecting patterns, validating sortedness, or finding transitions."},"type":"text"},{"data":{"code":"# Adjacent Comparison Patterns\n\ndef is_sorted_ascending(arr):\n \"\"\"Check if array is sorted (non-decreasing)\"\"\"\n for i in range(len(arr) - 1):\n if arr[i] > arr[i + 1]:\n return False\n return True\n\ndef count_ascending_pairs(arr):\n \"\"\"Count pairs where arr[i] < arr[i+1]\"\"\"\n count = 0\n for i in range(len(arr) - 1):\n if arr[i] < arr[i + 1]:\n count += 1\n return count\n\ndef find_first_decrease(arr):\n \"\"\"Find where sorted order first breaks\"\"\"\n for i in range(len(arr) - 1):\n if arr[i] > arr[i + 1]:\n return i\n return -1 # Array is fully sorted\n\n# Key insight: loop runs to len(arr) - 1 to avoid out-of-bounds\n# when accessing arr[i + 1]","showLineNumbers":true},"type":"code"}],"titleIcon":"Zap"}]},"type":"tabs"},{"data":{"icon":"Info","title":"Composing Patterns","content":"These patterns often combine. For example, \"find the maximum element that satisfies a condition\" combines search (find matching elements) with accumulation (track the maximum). Recognizing atomic patterns helps you decompose complex operations.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: Mastering Linear Traversal","content":[{"data":{"content":"We've explored linear traversal with the depth it deserves. Let's consolidate the key insights from this foundational topic:"},"type":"text"},{"data":{"type":"ordered","items":["**Traversal is fundamental** — Every array algorithm builds on the ability to visit elements systematically","**Forward traversal** visits elements from index 0 to n-1, matching natural order and optimizing cache locality","**Backward traversal** visits from n-1 to 0, essential for removal during iteration and last-occurrence searches","**Loop invariants** prove correctness by establishing what's true before and after each iteration","**O(n) time, O(1) space** is the baseline complexity for single-pass traversal","**Direction choice matters** — Backward when removing elements, forward as the default otherwise","**Common patterns** (accumulation, search, existence, comparison) compose to solve complex problems"],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nBasic traversal visits every element. But many problems allow—or require—stopping early. In the next page, we'll explore **traversal with early termination**: how to efficiently short-circuit when you've found what you need, and the patterns that make early exit both safe and effective."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a deep understanding of linear traversal—the most fundamental array operation. You can write forward and backward traversals correctly, understand their complexity, and recognize the common patterns that build upon them. In the next page, we'll extend these skills with early termination strategies.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_98cb230de0afe37755466341b7c5e4cc","title":"Traversal with Early Termination","order":1,"content":null,"isLocked":true},{"id":"seed_ad672001e177f9dd311e2490a5081318","title":"Collecting and Transforming During Traversal","order":2,"content":null,"isLocked":true},{"id":"seed_9a0e0265f37ae6a2da73b5a2779fd955","title":"Building Output Arrays During Traversal","order":3,"content":null,"isLocked":true}]}}