Array Traversal Patterns in DSA Rust - Time & Space Complexity

Time Complexity: Array Traversal Patterns

O(n)

Understanding Time Complexity

When we look at array traversal, we want to know how the time to finish changes as the array gets bigger.

We ask: How many steps does it take to visit every item in the array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_array(arr: &[i32]) -> i32 {
    let mut total = 0;
    for &value in arr.iter() {
        total += value;
    }
    total
}

This code adds up all the numbers in an array by visiting each element once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the array once.
• How many times: Exactly as many times as there are elements (n times).

How Execution Grows With Input

As the array gets bigger, the number of steps grows directly with the number of items.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: Doubling the array size doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Since the loop is simple, it must be faster than other loops."

[OK] Correct: Even a simple loop still touches every element, so time grows with input size just the same.

Interview Connect

Understanding how simple loops scale helps you explain and improve code efficiency in many real tasks.

Self-Check

"What if we nested another loop inside to compare each element with every other? How would the time complexity change?"

Practice

1. What does the following Rust code snippet do?
for i in 0..5 { println!("{}", i); }

easy

A. Prints numbers from 1 to 4

B. Prints numbers from 1 to 5

C. Prints numbers from 0 to 5

D. Prints numbers from 0 to 4

Solution

1. Step 1: Understand the range syntax 0..5

   The range 0..5 in Rust includes numbers starting at 0 up to but not including 5.

2. Step 2: Trace the loop iterations

   The loop variable i takes values 0, 1, 2, 3, and 4, printing each number.

3. Final Answer:

   Prints numbers from 0 to 4 -> Option D

4. Quick Check:

   Range 0..5 excludes 5, so output is 0 to 4 [OK]

Hint: Remember Rust ranges exclude the end number [OK]

Common Mistakes:

• Thinking 0..5 includes 5
• Confusing 0..5 with 0..=5
• Assuming loop starts at 1

2. Which of the following is the correct syntax to iterate over the indices of an array arr in Rust?

easy

A. for i in 0..arr.len() { println!("{}", arr[i]); }

B. for i in 0..arr { println!("{}", i); }

C. for i in arr { println!("{}", i); }

D. for i in arr.len() { println!("{}", i); }

Solution

1. Step 1: Check valid iteration over array indices

   Rust arrays have a length method .len(), so 0..arr.len() gives valid indices.

2. Step 2: Access elements by index

   Using arr[i] inside the loop accesses each element correctly.

3. Final Answer:

   for i in 0..arr.len() { println!("{}", arr[i]); } -> Option A

4. Quick Check:

   Use 0..arr.len() for index-based iteration [OK]

Hint: Use arr.len() for array length, not arr alone [OK]

Common Mistakes:

• Using 0..arr instead of 0..arr.len()
• Trying to iterate directly over arr without reference
• Using arr.len() without range syntax

3. What is the output of this Rust code?

let arr = [10, 20, 30];
for i in (0..arr.len()).rev() {
    print!("{} ", arr[i]);
}

medium

A. 10 20 30

B. 0 1 2

C. 30 20 10

D. Compilation error

Solution

1. Step 1: Understand the range and reverse

   The range 0..arr.len() is 0..3, which is 0,1,2. Using .rev() reverses it to 2,1,0.

2. Step 2: Print elements in reverse order

   arr[2] = 30, arr[1] = 20, arr[0] = 10, so output is "30 20 10 "

3. Final Answer:

   30 20 10 -> Option C

4. Quick Check:

   Reverse iteration prints elements backward [OK]

Hint: Use .rev() to reverse range iteration [OK]

Common Mistakes:

• Forgetting .rev() reverses the order
• Printing indices instead of array values
• Confusing range end with inclusive

4. Identify the error in this Rust code snippet that tries to print all elements of an array arr:

let arr = [1, 2, 3];
for i in 0..arr.len() {
    println!("{}", arr[i+1]);
}

medium

A. Syntax error due to missing semicolon

B. Index out of bounds error at runtime

C. No error, prints all elements correctly

D. Compilation error due to type mismatch

Solution

1. Step 1: Analyze the loop indices and access

   The loop runs i from 0 to 2 (arr.len()=3). Accessing arr[i+1] means indices 1,2,3.

2. Step 2: Identify out of bounds access

   arr[3] does not exist, causing runtime panic (index out of bounds).

3. Final Answer:

   Index out of bounds error at runtime -> Option B

4. Quick Check:

   Accessing arr[i+1] exceeds array length [OK]

Hint: Check array indices carefully to avoid out of bounds [OK]

Common Mistakes:

• Assuming arr[i+1] is safe for all i
• Ignoring runtime panics
• Confusing compile-time and runtime errors

5. Given a Rust array arr of integers, which code snippet correctly prints only the even-indexed elements (0, 2, 4, ...) of the array?

hard

A. for i in (0..arr.len()).step_by(2) { println!("{}", arr[i]); }

B. for i in 0..arr.len() { if i % 2 == 1 { println!("{}", arr[i]); } }

C. for i in 0..arr.len() { println!("{}", arr[i * 2]); }

D. for i in (0..arr.len()).rev().step_by(2) { println!("{}", arr[i]); }

Solution

1. Step 1: Understand step_by usage

   The method step_by(2) skips every second index, so 0, 2, 4, ...

2. Step 2: Confirm correct element access

   Using arr[i] inside the loop prints elements at even indices correctly.

3. Final Answer:

   for i in (0..arr.len()).step_by(2) { println!("{}", arr[i]); } -> Option A

4. Quick Check:

   step_by(2) iterates over even indices [OK]

Hint: Use step_by(2) to jump every two elements [OK]

Common Mistakes:

• Using i % 2 == 1 instead of 0 for even indices
• Multiplying i by 2 causing out of bounds
• Using rev() which reverses order unnecessarily