FilesExpand file tree

main

/

zigzagiterator.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

57 lines (43 loc) · 1.33 KB

main

/

zigzagiterator.py

Copy path

Top

File metadata and controls

• Code
• Blame

57 lines (43 loc) · 1.33 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

"""

Zigzag Iterator

Interleave elements from two lists in a zigzag fashion. Elements are

yielded alternately from each list until both are exhausted.

Reference: https://leetcode.com/problems/zigzag-iterator/

Complexity:

Time: O(n) total across all next() calls

Space: O(n)

"""

from __future__ import annotations

from collections import deque

class ZigZagIterator:

"""Iterator that interleaves elements from two lists.

Examples:

>>> it = ZigZagIterator([1, 2], [3, 4, 5])

>>> it.next()

1

>>> it.next()

3

"""

def __init__(self, v1: list[int], v2: list[int]) -> None:

"""Initialize with two lists.

Args:

v1: First input list.

v2: Second input list.

"""

self.queue: deque[list[int]] = deque(lst for lst in (v1, v2) if lst)

def next(self) -> int:

"""Return the next element in zigzag order.

Returns:

The next interleaved element.

"""

current_list = self.queue.popleft()

ret = current_list.pop(0)

if current_list:

self.queue.append(current_list)

return ret

def has_next(self) -> bool:

"""Check if there are more elements.

Returns:

True if elements remain, False otherwise.

"""

return bool(self.queue)