0 ≤ index < length           # Valid index range
array[i] accessible in O(1)  # Random access

from typing import TypeVar, Generic, List, Optional, Iterator

T = TypeVar('T')

class DynamicArray(Generic[T]):
    """
    Dynamic array implementation with amortized O(1) append.
    
    >>> arr = DynamicArray[int]()
    >>> arr.append(1)
    >>> arr.append(2)
    >>> arr.append(3)
    >>> len(arr)
    3
    >>> arr[1]
    2
    >>> arr[-1]
    3
    >>> arr[1] = 10
    >>> arr[1]
    10
    >>> arr.pop()
    3
    >>> len(arr)
    2
    """
    
    INITIAL_CAPACITY = 4
    GROWTH_FACTOR = 2
    
    def __init__(self):
        self._capacity: int = self.INITIAL_CAPACITY
        self._size: int = 0
        self._data: List[Optional[T]] = [None] * self._capacity
    
    def __len__(self) -> int:
        """Return number of elements. O(1)"""
        return self._size
    
    def __getitem__(self, index: int) -> T:
        """Get element at index. Supports negative indexing. O(1)"""
        if index < 0:
            index = self._size + index
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of bounds for size {self._size}")
        return self._data[index]  # type: ignore
    
    def __setitem__(self, index: int, value: T) -> None:
        """Set element at index. O(1)"""
        if index < 0:
            index = self._size + index
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of bounds for size {self._size}")
        self._data[index] = value
    
    def append(self, value: T) -> None:
        """Add element at end. O(1) amortized."""
        if self._size == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)
        self._data[self._size] = value
        self._size += 1
    
    def pop(self) -> T:
        """Remove and return last element. O(1)"""
        if self._size == 0:
            raise IndexError("Pop from empty array")
        self._size -= 1
        value = self._data[self._size]
        self._data[self._size] = None  # Help garbage collection
        # Optionally shrink if too empty
        if self._size < self._capacity // 4 and self._capacity > self.INITIAL_CAPACITY:
            self._resize(self._capacity // 2)
        return value  # type: ignore
    
    def insert(self, index: int, value: T) -> None:
        """Insert at index, shifting elements right. O(n)"""
        if index < 0 or index > self._size:
            raise IndexError(f"Index {index} out of bounds")
        if self._size == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)
        # Shift elements right
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        self._data[index] = value
        self._size += 1
    
    def remove(self, index: int) -> T:
        """Remove element at index, shifting elements left. O(n)"""
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of bounds")
        value = self._data[index]
        # Shift elements left
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]
        self._size -= 1
        self._data[self._size] = None
        return value  # type: ignore
    
    def _resize(self, new_capacity: int) -> None:
        """Resize internal array. O(n)"""
        new_data: List[Optional[T]] = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity
    
    def __iter__(self) -> Iterator[T]:
        """Iterate over elements. O(n) total."""
        for i in range(self._size):
            yield self._data[i]  # type: ignore
    
    def __repr__(self) -> str:
        return f"DynamicArray({[self._data[i] for i in range(self._size)]})"


if __name__ == "__main__":
    import doctest
    doctest.testmod()

┌─────────────────────────────────────────────────────────┐
│ Memory Layout: Contiguous allocation                    │
├─────────────────────────────────────────────────────────┤
│ Base Address: 0x1000                                    │
│                                                         │
│  Index:    0      1      2      3      4               │
│          ┌──────┬──────┬──────┬──────┬──────┐          │
│ Address: │0x1000│0x1004│0x1008│0x100C│0x1010│          │
│          │  10  │  20  │  30  │  40  │  50  │          │
│          └──────┴──────┴──────┴──────┴──────┘          │
│                                                         │
│ Address of element[i] = base + (i × element_size)      │
│ Example: element[2] = 0x1000 + (2 × 4) = 0x1008        │
└─────────────────────────────────────────────────────────┘

from typing import List

def array_operations_demo():
    """
    Demonstration of Python list operations with complexity.
    
    >>> array_operations_demo()
    Creation: [1, 2, 3, 4, 5]
    Access arr[2]: 3
    Slice arr[1:4]: [2, 3, 4]
    After append: [1, 2, 3, 4, 5, 6]
    After insert at 0: [0, 1, 2, 3, 4, 5, 6]
    After pop: [0, 1, 2, 3, 4, 5]
    After remove(3): [0, 1, 2, 4, 5]
    Reversed: [5, 4, 2, 1, 0]
    Sorted: [0, 1, 2, 4, 5]
    """
    # Creation - O(n)
    arr: List[int] = [1, 2, 3, 4, 5]
    print(f"Creation: {arr}")
    
    # Access - O(1)
    print(f"Access arr[2]: {arr[2]}")
    
    # Slicing - O(k) where k = slice size
    print(f"Slice arr[1:4]: {arr[1:4]}")
    
    # Append - O(1) amortized
    arr.append(6)
    print(f"After append: {arr}")
    
    # Insert at index - O(n)
    arr.insert(0, 0)
    print(f"After insert at 0: {arr}")
    
    # Pop from end - O(1)
    arr.pop()
    print(f"After pop: {arr}")
    
    # Remove by value - O(n)
    arr.remove(3)
    print(f"After remove(3): {arr}")
    
    # Reverse - O(n)
    arr.reverse()
    print(f"Reversed: {arr}")
    
    # Sort - O(n log n)
    arr.sort()
    print(f"Sorted: {arr}")


# List comprehensions - Pythonic array creation
def list_comprehension_examples():
    """
    >>> squares = [x**2 for x in range(5)]
    >>> squares
    [0, 1, 4, 9, 16]
    >>> evens = [x for x in range(10) if x % 2 == 0]
    >>> evens
    [0, 2, 4, 6, 8]
    >>> matrix = [[i*3+j for j in range(3)] for i in range(3)]
    >>> matrix
    [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
    """
    pass


if __name__ == "__main__":
    import doctest
    doctest.testmod()

Step 1: Handle k > n case
  k = k % n = 3 % 7 = 3
  
Step 2: Reverse entire array
  [1, 2, 3, 4, 5, 6, 7] → [7, 6, 5, 4, 3, 2, 1]
  
Step 3: Reverse first k elements
  [7, 6, 5, 4, 3, 2, 1] → [5, 6, 7, 4, 3, 2, 1]
        ↑───↑
       k elements
       
Step 4: Reverse remaining n-k elements
  [5, 6, 7, 4, 3, 2, 1] → [5, 6, 7, 1, 2, 3, 4]
              ↑───────↑
             n-k elements

Final: [5, 6, 7, 1, 2, 3, 4] ✓

from typing import List

def matrix_operations():
    """
    2D array operations and traversal patterns.
    
    >>> matrix = [[1,2,3], [4,5,6], [7,8,9]]
    >>> # Row-major traversal
    >>> [matrix[i][j] for i in range(3) for j in range(3)]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> # Column-major traversal
    >>> [matrix[i][j] for j in range(3) for i in range(3)]
    [1, 4, 7, 2, 5, 8, 3, 6, 9]
    >>> # Diagonal traversal
    >>> [matrix[i][i] for i in range(3)]
    [1, 5, 9]
    >>> # Anti-diagonal
    >>> [matrix[i][2-i] for i in range(3)]
    [3, 5, 7]
    """
    pass


def transpose(matrix: List[List[int]]) -> List[List[int]]:
    """
    Transpose matrix (swap rows and columns).
    
    >>> transpose([[1,2,3], [4,5,6]])
    [[1, 4], [2, 5], [3, 6]]
    """
    if not matrix:
        return []
    rows, cols = len(matrix), len(matrix[0])
    return [[matrix[i][j] for i in range(rows)] for j in range(cols)]

class CircularArray:
    """
    Array with wrap-around indexing.
    
    >>> ca = CircularArray([1, 2, 3, 4, 5])
    >>> ca[7]  # 7 % 5 = 2
    3
    >>> ca[-1]  # Wraps to last element
    5
    """
    def __init__(self, data: List[int]):
        self.data = data
        self.n = len(data)
    
    def __getitem__(self, index: int) -> int:
        return self.data[index % self.n]

from typing import List

def product_except_self(nums: List[int]) -> List[int]:
    """
    Calculate product of all elements except self.
    
    Approach: Use prefix and suffix products.
    - prefix[i] = product of all elements before index i
    - suffix[i] = product of all elements after index i
    - result[i] = prefix[i] * suffix[i]
    
    Time Complexity: O(n) - two passes
    Space Complexity: O(1) - output array not counted
    
    >>> product_except_self([1, 2, 3, 4])
    [24, 12, 8, 6]
    >>> product_except_self([-1, 1, 0, -3, 3])
    [0, 0, 9, 0, 0]
    >>> product_except_self([2, 3])
    [3, 2]
    """
    n = len(nums)
    result = [1] * n
    
    # First pass: calculate prefix products
    # result[i] = product of nums[0] * nums[1] * ... * nums[i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Second pass: multiply by suffix products
    # result[i] *= nums[i+1] * nums[i+2] * ... * nums[n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result


def product_except_self_with_visualization(nums: List[int]) -> List[int]:
    """
    Same algorithm with step-by-step visualization.
    
    >>> product_except_self_with_visualization([1, 2, 3, 4])
    Initial: [1, 2, 3, 4]
    <BLANKLINE>
    Pass 1 - Prefix Products:
    i=0: prefix=1, result=[1, 1, 1, 1]
    i=1: prefix=1, result=[1, 1, 1, 1]
    i=2: prefix=2, result=[1, 1, 2, 1]
    i=3: prefix=6, result=[1, 1, 2, 6]
    <BLANKLINE>
    Pass 2 - Suffix Products:
    i=3: suffix=1, result=[1, 1, 2, 6]
    i=2: suffix=4, result=[1, 1, 8, 6]
    i=1: suffix=12, result=[1, 12, 8, 6]
    i=0: suffix=24, result=[24, 12, 8, 6]
    <BLANKLINE>
    Final: [24, 12, 8, 6]
    [24, 12, 8, 6]
    """
    n = len(nums)
    result = [1] * n
    
    print(f"Initial: {nums}")
    print(f"\nPass 1 - Prefix Products:")
    
    prefix = 1
    for i in range(n):
        result[i] = prefix
        print(f"i={i}: prefix={prefix}, result={result}")
        prefix *= nums[i]
    
    print(f"\nPass 2 - Suffix Products:")
    
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        print(f"i={i}: suffix={suffix}, result={result}")
        suffix *= nums[i]
    
    print(f"\nFinal: {result}")
    return result


# Unit tests
def test_product_except_self():
    assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert product_except_self([0, 1, 2]) == [2, 0, 0]
    assert product_except_self([0, 0]) == [0, 0]
    assert product_except_self([5]) == [1]  # Edge case: single element
    print("All tests passed!")


if __name__ == "__main__":
    import doctest
    doctest.testmod()
    test_product_except_self()