Iterator interface implementation in PHP - Time & Space Complexity

Time Complexity: Iterator interface implementation

O(n)

Understanding Time Complexity

When we use the Iterator interface in PHP, we want to know how the time to go through items changes as the number of items grows.

We ask: How does looping through all elements behave as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class MyIterator implements Iterator {
    private array $items;
    private int $position = 0;

    public function __construct(array $items) {
        $this->items = $items;
    }

    public function current() {
        return $this->items[$this->position];
    }

    public function key() {
        return $this->position;
    }

    public function next(): void {
        $this->position++;
    }

    public function rewind(): void {
        $this->position = 0;
    }

    public function valid(): bool {
        return isset($this->items[$this->position]);
    }
}

$iterator = new MyIterator([1, 2, 3, 4, 5]);
foreach ($iterator as $key => $value) {
    echo "$key: $value\n";
}
    

This code defines a class that lets us loop over an array using the Iterator interface methods.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The foreach loop calls the Iterator methods repeatedly to access each item.
• How many times: Once for each element in the array, so as many times as the number of items.

How Execution Grows With Input

As the number of items grows, the number of method calls grows directly with it.

Input Size (n)	Approx. Operations
10	About 10 calls to current(), next(), valid()
100	About 100 calls to current(), next(), valid()
1000	About 1000 calls to current(), next(), valid()

Pattern observation: The work grows evenly as the list grows; doubling the items doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to loop through all items grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Using the Iterator interface makes looping slower and more complex than a simple array loop."

[OK] Correct: The Iterator methods are called once per item, just like a normal loop visits each element once, so the time grows the same way.

Interview Connect

Understanding how iterators work and their time cost helps you explain how your code handles data step-by-step, a useful skill in many coding situations.

Self-Check

"What if the iterator's current() method did extra work each time it was called? How would that affect the time complexity?"

Practice

1. Which of the following methods is NOT required when implementing the Iterator interface in PHP?

easy

A. sort()

B. current()

C. next()

D. rewind()

Solution

1. Step 1: Recall Iterator interface methods

   The Iterator interface requires implementing rewind(), current(), key(), next(), and valid() methods.

2. Step 2: Identify the method not in Iterator

   The sort() method is not part of the Iterator interface; it is unrelated to iteration.

3. Final Answer:

   sort() -> Option A

4. Quick Check:

   Iterator methods exclude sort() [OK]

Hint: Remember: Iterator needs rewind, current, key, next, valid only [OK]

Common Mistakes:

• Confusing sort() as part of Iterator
• Forgetting to implement key() or valid()
• Thinking rewind() is optional

2. Which of the following is the correct syntax to declare a class MyIterator that implements the Iterator interface?

easy

A. class MyIterator implements Iterator { }

B. class MyIterator extends Iterator { }

C. class MyIterator uses Iterator { }

D. class MyIterator interface Iterator { }

Solution

1. Step 1: Recall PHP interface implementation syntax

   In PHP, a class implements an interface using the keyword 'implements'.

2. Step 2: Check each option's syntax

   class MyIterator implements Iterator { } uses 'implements' correctly. The other options use invalid keywords or syntax.

3. Final Answer:

   class MyIterator implements Iterator { } -> Option A

4. Quick Check:

   Use 'implements' keyword for interfaces [OK]

Hint: Use 'implements' keyword to implement interfaces in PHP [OK]

Common Mistakes:

• Using 'extends' instead of 'implements' for interfaces
• Using 'uses' or 'interface' keywords incorrectly
• Missing curly braces after class declaration

3. What will be the output of the following PHP code?

$items = ['a', 'b', 'c'];

class MyIterator implements Iterator {
    private array $items;
    private int $index = 0;

    public function __construct(array $items) {
        $this->items = $items;
    }

    public function current() {
        return $this->items[$this->index];
    }

    public function key() {
        return $this->index;
    }

    public function next(): void {
        $this->index++;
    }

    public function rewind(): void {
        $this->index = 0;
    }

    public function valid(): bool {
        return isset($this->items[$this->index]);
    }
}

$iterator = new MyIterator($items);
foreach ($iterator as $key => $value) {
    echo "$key:$value ";
}

medium

A. a:b c:d e:f

B. 0:a 1:b 2:c

C. 0:0 1:1 2:2

D. Error: Undefined variable

Solution

1. Step 1: Understand the iterator implementation

   The class stores items and uses an index to track position. Methods current(), key(), next(), rewind(), and valid() are correctly implemented.

2. Step 2: Trace the foreach loop output

   foreach uses key() and current() to print "key:value" pairs. Indexes 0,1,2 correspond to 'a','b','c'. Output is "0:a 1:b 2:c "

3. Final Answer:

   0:a 1:b 2:c -> Option B

4. Quick Check:

   Iterator keys and values match array indexes and elements [OK]

Hint: Trace index and current() output for each loop iteration [OK]

Common Mistakes:

• Confusing keys with values
• Forgetting to implement valid() correctly
• Expecting output without spaces

4. Consider this broken iterator class:

class BrokenIterator implements Iterator {
    private array $data = [1, 2, 3];
    private int $pos = 0;

    public function current() {
        return $this->data[$this->pos];
    }

    public function key() {
        return $this->pos;
    }

    public function next() {
        $this->pos++;
    }

    public function rewind() {
        $this->pos = 0;
    }

    public function valid() {
        return $this->pos < count($this->data);
    }
}

What is the main issue that could cause unexpected behavior when using this iterator in a foreach loop?

medium

A. The next() method does not have a void return type

B. The valid() method should use isset() instead of count()

C. The valid() method returns a boolean but should return an integer

D. The next() and rewind() methods lack return type declarations

Solution

1. Step 1: Check method signatures against Iterator interface

   Iterator interface requires next() and rewind() to have void return type declarations.

2. Step 2: Identify missing return types

   In the code, next() and rewind() lack ': void' return type, which can cause compatibility issues in strict mode.

3. Final Answer:

   Missing void return types in next() and rewind() -> Option D

4. Quick Check:

   next() and rewind() must declare void return type [OK]

Hint: Check method signatures match interface exactly including return types [OK]

Common Mistakes:

• Ignoring return type declarations
• Thinking valid() must return integer
• Confusing isset() and count() usage in valid()

5. You want to create a custom iterator EvenNumbers that iterates over only even numbers from a given array. Which implementation of the valid() method correctly skips odd numbers during iteration?

hard

A. public function valid(): bool {
return isset($this->items[$this->index]);
}

B. public function valid(): bool {
return $this->items[$this->index] % 2 === 0;
}

C. public function valid(): bool {
while (isset($this->items[$this->index]) && $this->items[$this->index] % 2 !== 0) {
$this->index++;
}
return isset($this->items[$this->index]);
}

D. public function valid(): bool {
return $this->index < count($this->items);
}

Solution

1. Step 1: Understand the goal of skipping odd numbers

   The iterator must advance the index until it points to an even number or end of array.

2. Step 2: Analyze each valid() implementation

   public function valid(): bool { while (isset($this->items[$this->index]) && $this->items[$this->index] % 2 !== 0) { $this->index++; } return isset($this->items[$this->index]); } uses a while loop to skip odd numbers by incrementing index, then checks if current index exists. The other options do not skip odd numbers properly.

3. Final Answer:

   while loop in valid() to skip odd numbers -> Option C

4. Quick Check:

   valid() must skip odd values to find even numbers [OK]

Hint: Use a loop inside valid() to skip unwanted elements [OK]

Common Mistakes:

• Returning true without skipping odd numbers
• Not checking if index exists before accessing array
• Using valid() only to check index range