Array Traversal Patterns

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

# Understanding Dynamic Array Growth
# ===================================
 
import sys
 
def demonstrate_list_growth():
    """
    Show how Python lists grow in capacity.
    """
    sizes = []
    data = []
    
    for i in range(100):
        data.append(i)
        # sys.getsizeof gives the list object size (changes with capacity)
        size = sys.getsizeof(data)
        if not sizes or size != sizes[-1]:
            sizes.append(size)
            print(f"After {len(data)} elements: {size} bytes allocated")
 
def count_and_cumulative_cost(n):
    """
    Calculate the total copy operations for n appends
    assuming doubling strategy starting with capacity 1.
    """
    capacity = 1
    total_copies = 0
    
    for i in range(1, n + 1):
        if i > capacity:
            # Need to resize: copy all existing elements
            total_copies += (i - 1)  # Copy old elements
            capacity *= 2  # Double capacity
    
    return total_copies
 
# Demonstration: verify amortized O(1)
if __name__ == "__main__":
    print("List growth pattern:")
    demonstrate_list_growth()
    
    print("\nTotal copy operations for n appends (doubling):")
    for n in [10, 100, 1000, 10000]:
        copies = count_and_cumulative_cost(n)
        print(f"  n={n:5d}: {copies:6d} copies, ratio = {copies/n:.2f} copies per append")

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

# Append vs. Pre-allocation Strategies
# =====================================
 
# Strategy 1: Incremental Append (simple, flexible)
def map_with_append(arr, transform):
    """
    Build output by appending.
    Good when output size is unknown or smaller than input.
    """
    result = []
    for x in arr:
        result.append(transform(x))
    return result
 
 
# Strategy 2: Pre-allocation (optimal for known-size maps)
def map_with_prealloc(arr, transform):
    """
    Pre-allocate output of exact size.
    Optimal when output has same length as input.
    
    Note: Uses None as placeholder, then fills.
    """
    n = len(arr)
    result = [None] * n  # Pre-allocate
    for i in range(n):
        result[i] = transform(arr[i])
    return result
 
 
# Strategy 3: Hybrid - Pre-allocate with hint
def filter_with_hint(arr, predicate, size_hint=None):
    """
    Pre-allocate based on expected output size.
    Falls back to append if hint is exhausted.
    
    Useful when you have statistics about filter rates.
    """
    if size_hint is None:
        # Default: assume 50% pass
        size_hint = len(arr) // 2
    
    # Pre-allocate
    result = [None] * size_hint
    count = 0
    
    for x in arr:
        if predicate(x):
            if count < size_hint:
                result[count] = x
            else:
                result.append(x)  # Overflow - use append
            count += 1
    
    # Trim or extend result to actual size
    del result[count:]
    return result
 
 
# Comparison benchmark
import time
 
def benchmark_allocation_strategies():
    data = list(range(1000000))
    transform = lambda x: x * 2
    
    # Append
    start = time.time()
    result1 = map_with_append(data, transform)
    append_time = time.time() - start
    
    # Pre-allocation
    start = time.time()
    result2 = map_with_prealloc(data, transform)
    prealloc_time = time.time() - start
    
    # Python list comprehension (optimized)
    start = time.time()
    result3 = [x * 2 for x in data]
    comprehension_time = time.time() - start
    
    print(f"Append:        {append_time:.4f}s")
    print(f"Pre-allocate:  {prealloc_time:.4f}s")
    print(f"Comprehension: {comprehension_time:.4f}s")
    print(f"Pre-alloc speedup: {append_time/prealloc_time:.2f}x")
 
 
if __name__ == "__main__":
    benchmark_allocation_strategies()

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

# Building Multiple Output Arrays Simultaneously
# ===============================================
 
def partition(arr, predicate):
    """
    Split array into two: elements passing and failing predicate.
    Single pass builds both outputs.
    
    Returns: (passing, failing) tuple
    """
    passing = []
    failing = []
    
    for x in arr:
        if predicate(x):
            passing.append(x)
        else:
            failing.append(x)
    
    return passing, failing
 
 
def multi_partition(arr, classifier):
    """
    Partition into multiple groups based on a classifier function.
    
    classifier(element) -> category label
    Returns: dict mapping category -> list of elements
    """
    groups = {}
    
    for x in arr:
        category = classifier(x)
        if category not in groups:
            groups[category] = []
        groups[category].append(x)
    
    return groups
 
 
def unzip(pairs):
    """
    Transform list of pairs into two parallel lists.
    [(a1, b1), (a2, b2), ...] -> ([a1, a2, ...], [b1, b2, ...])
    """
    firsts = []
    seconds = []
    
    for a, b in pairs:
        firsts.append(a)
        seconds.append(b)
    
    return firsts, seconds
 
 
def extract_indices_and_values(arr, predicate):
    """
    Get both WHERE elements match AND WHAT they are.
    Returns parallel arrays of indices and values.
    """
    indices = []
    values = []
    
    for i, x in enumerate(arr):
        if predicate(x):
            indices.append(i)
            values.append(x)
    
    return indices, values
 
 
def compute_running_statistics(arr):
    """
    Compute multiple running statistics in one pass.
    Returns parallel arrays of running min, max, sum.
    """
    if not arr:
        return [], [], []
    
    running_mins = []
    running_maxs = []
    running_sums = []
    
    current_min = arr[0]
    current_max = arr[0]
    current_sum = 0
    
    for x in arr:
        current_min = min(current_min, x)
        current_max = max(current_max, x)
        current_sum += x
        
        running_mins.append(current_min)
        running_maxs.append(current_max)
        running_sums.append(current_sum)
    
    return running_mins, running_maxs, running_sums
 
 
# Practical example: separate valid and invalid records
def validate_records(records):
    """
    Validate records and return (valid_records, errors) tuple.
    Errors include the record and reason for failure.
    """
    valid = []
    errors = []
    
    for record in records:
        # Check required fields
        if 'id' not in record:
            errors.append((record, "Missing 'id' field"))
            continue
        if 'value' not in record:
            errors.append((record, "Missing 'value' field"))
            continue
            
        # Check value constraints
        if not isinstance(record['value'], (int, float)):
            errors.append((record, "Value must be numeric"))
            continue
        if record['value'] < 0:
            errors.append((record, "Value must be non-negative"))
            continue
        
        # All checks passed
        valid.append(record)
    
    return valid, errors
 
 
# Demonstration
if __name__ == "__main__":
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    
    # Partition: evens and odds
    evens, odds = partition(numbers, lambda x: x % 2 == 0)
    print(f"Evens: {evens}")
    print(f"Odds: {odds}")
    
    # Multi-partition: by modulo 3
    by_mod3 = multi_partition(numbers, lambda x: x % 3)
    print(f"\nBy mod 3: {by_mod3}")
    
    # Unzip pairs
    pairs = [(1, 'a'), (2, 'b'), (3, 'c')]
    nums, chars = unzip(pairs)
    print(f"\nUnzipped: {nums} and {chars}")
    
    # Running statistics
    data = [5, 3, 8, 1, 9, 2]
    mins, maxs, sums = compute_running_statistics(data)
    print(f"\nData: {data}")
    print(f"Running min: {mins}")
    print(f"Running max: {maxs}")
    print(f"Running sum: {sums}")

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

# In-Place Modification Patterns
# ===============================
 
def map_in_place(arr, transform):
    """
    Apply transformation to each element in-place.
    No new array allocated.
    
    Time: O(n)
    Space: O(1) - no additional array
    """
    for i in range(len(arr)):
        arr[i] = transform(arr[i])
    # No return - array modified directly
 
 
def reverse_in_place(arr):
    """
    Reverse array in-place using two pointers.
    Classic O(1) space reversal.
    """
    left = 0
    right = len(arr) - 1
    
    while left < right:
        # Swap elements
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
 
 
def remove_element_in_place(arr, target):
    """
    Remove all occurrences of target in-place.
    Returns the new length (valid portion of array).
    
    Two-pointer technique: write pointer trails read pointer.
    Elements not equal to target are kept.
    """
    write_index = 0
    
    for read_index in range(len(arr)):
        if arr[read_index] != target:
            arr[write_index] = arr[read_index]
            write_index += 1
    
    # Array[0:write_index] contains valid elements
    # Elements after write_index are "garbage"
    return write_index
 
 
def remove_duplicates_sorted_in_place(arr):
    """
    Remove duplicates from sorted array in-place.
    Returns new length.
    
    Key insight: In sorted array, duplicates are adjacent.
    Only copy when we find a new value.
    """
    if len(arr) <= 1:
        return len(arr)
    
    write_index = 1  # First element is always unique
    
    for read_index in range(1, len(arr)):
        if arr[read_index] != arr[write_index - 1]:
            arr[write_index] = arr[read_index]
            write_index += 1
    
    return write_index
 
 
def partition_in_place(arr, pivot):
    """
    Partition array around pivot value in-place.
    Elements < pivot come before elements >= pivot.
    Returns index of first element >= pivot.
    
    This is the foundation of quicksort partitioning.
    """
    write_index = 0
    
    for read_index in range(len(arr)):
        if arr[read_index] < pivot:
            arr[write_index], arr[read_index] = arr[read_index], arr[write_index]
            write_index += 1
    
    return write_index
 
 
def move_zeros_to_end(arr):
    """
    Move all zeros to end while maintaining relative order of non-zeros.
    Classic interview problem.
    """
    write_index = 0
    
    # First pass: move non-zeros to front
    for read_index in range(len(arr)):
        if arr[read_index] != 0:
            arr[write_index] = arr[read_index]
            write_index += 1
    
    # Second pass: fill remainder with zeros
    while write_index < len(arr):
        arr[write_index] = 0
        write_index += 1
 
 
# Demonstration
if __name__ == "__main__":
    # Map in-place
    data = [1, 2, 3, 4, 5]
    print(f"Original: {data}")
    map_in_place(data, lambda x: x * 2)
    print(f"After doubling in-place: {data}")
    
    # Reverse in-place
    data = [1, 2, 3, 4, 5]
    reverse_in_place(data)
    print(f"\nReversed in-place: {data}")
    
    # Remove element
    data = [3, 2, 2, 3, 4, 2, 5]
    print(f"\nOriginal: {data}")
    new_len = remove_element_in_place(data, 2)
    print(f"After removing 2s: {data[:new_len]} (length = {new_len})")
    
    # Remove duplicates (sorted)
    data = [1, 1, 2, 2, 2, 3, 4, 4, 5]
    print(f"\nSorted with dups: {data}")
    new_len = remove_duplicates_sorted_in_place(data)
    print(f"After dedup: {data[:new_len]} (length = {new_len})")
    
    # Move zeros
    data = [0, 1, 0, 3, 12]
    print(f"\nWith zeros: {data}")
    move_zeros_to_end(data)
    print(f"Zeros at end: {data}")

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

# Building Arrays of Different Structures
# ========================================
 
# 1. Building nested arrays (chunking)
def chunk(arr, size):
    """
    Split array into chunks of given size.
    [1,2,3,4,5] with size=2 -> [[1,2], [3,4], [5]]
    """
    result = []
    current_chunk = []
    
    for x in arr:
        current_chunk.append(x)
        if len(current_chunk) == size:
            result.append(current_chunk)
            current_chunk = []
    
    # Don't forget the last partial chunk
    if current_chunk:
        result.append(current_chunk)
    
    return result
 
 
def group_consecutive(arr, key_fn):
    """
    Group consecutive elements with same key.
    [1,1,2,2,2,1,3,3] -> [[1,1], [2,2,2], [1], [3,3]]
    (preserves order, groups only consecutive identical)
    """
    if not arr:
        return []
    
    result = []
    current_group = [arr[0]]
    current_key = key_fn(arr[0])
    
    for x in arr[1:]:
        x_key = key_fn(x)
        if x_key == current_key:
            current_group.append(x)
        else:
            result.append(current_group)
            current_group = [x]
            current_key = x_key
    
    result.append(current_group)  # Last group
    return result
 
 
# 2. Flattening nested arrays
def flatten_one_level(nested):
    """Flatten one level of nesting."""
    result = []
    for sublist in nested:
        for item in sublist:
            result.append(item)
    return result
 
 
def flatten_deep(nested):
    """Recursively flatten all levels of nesting."""
    result = []
    
    def helper(item):
        if isinstance(item, list):
            for sub in item:
                helper(sub)
        else:
            result.append(item)
    
    helper(nested)
    return result
 
 
# 3. Building index arrays
def argsort(arr, reverse=False):
    """
    Return indices that would sort the array.
    Like numpy.argsort.
    """
    indexed = list(enumerate(arr))
    indexed.sort(key=lambda pair: pair[1], reverse=reverse)
    return [idx for idx, val in indexed]
 
 
def where(arr, predicate):
    """
    Return indices where predicate is True.
    Like numpy.where.
    """
    return [i for i, x in enumerate(arr) if predicate(x)]
 
 
# 4. Building lookup structures
def build_index_map(arr):
    """
    Build value -> list of indices mapping.
    Useful for quick lookups.
    """
    index_map = {}
    for i, x in enumerate(arr):
        if x not in index_map:
            index_map[x] = []
        index_map[x].append(i)
    return index_map
 
 
def encode_run_length(arr):
    """
    Run-length encoding: compress consecutive duplicates.
    [1,1,1,2,2,3,1,1] -> [(1,3), (2,2), (3,1), (1,2)]
    (value, count) pairs
    """
    if not arr:
        return []
    
    result = []
    current_value = arr[0]
    current_count = 1
    
    for x in arr[1:]:
        if x == current_value:
            current_count += 1
        else:
            result.append((current_value, current_count))
            current_value = x
            current_count = 1
    
    result.append((current_value, current_count))
    return result
 
 
def decode_run_length(encoded):
    """Expand run-length encoded data back to full array."""
    result = []
    for value, count in encoded:
        result.extend([value] * count)
    return result
 
 
# 5. Building sparse representations
def to_sparse(arr, default=0):
    """
    Convert to sparse representation: only store non-default values.
    Returns list of (index, value) pairs.
    """
    return [(i, x) for i, x in enumerate(arr) if x != default]
 
 
def from_sparse(sparse, length, default=0):
    """Reconstruct full array from sparse representation."""
    result = [default] * length
    for index, value in sparse:
        result[index] = value
    return result
 
 
# Demonstration
if __name__ == "__main__":
    # Chunking
    data = [1, 2, 3, 4, 5, 6, 7]
    print(f"Chunked into 3s: {chunk(data, 3)}")
    
    # Group consecutive
    data = [1, 1, 2, 2, 2, 1, 3, 3]
    print(f"Grouped consecutive: {group_consecutive(data, lambda x: x)}")
    
    # Flatten
    nested = [[1, 2], [3, [4, 5]], 6]
    print(f"\nDeep flatten: {flatten_deep(nested)}")
    
    # Argsort
    data = [30, 10, 20, 50, 40]
    indices = argsort(data)
    print(f"\nData: {data}")
    print(f"Argsort: {indices} (sorted order: {[data[i] for i in indices]})")
    
    # Run-length encoding
    data = [1, 1, 1, 2, 2, 3, 1, 1]
    encoded = encode_run_length(data)
    print(f"\nOriginal: {data}")
    print(f"RLE encoded: {encoded}")
    print(f"Decoded: {decode_run_length(encoded)}")
    
    # Sparse representation
    sparse_data = [0, 0, 5, 0, 0, 0, 3, 0, 0, 8, 0]
    sparse = to_sparse(sparse_data)
    print(f"\nFull: {sparse_data}")
    print(f"Sparse: {sparse}")

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

# Memory Efficiency Techniques
# =============================
 
import sys
 
# 1. Generator-based processing (no full array in memory)
def filter_large_file_generator(file_path, predicate):
    """
    Process large file line-by-line without loading into memory.
    Yields matching lines one at a time.
    """
    with open(file_path, 'r') as f:
        for line in f:
            if predicate(line):
                yield line.strip()
 
 
def process_in_chunks(data, chunk_size, processor):
    """
    Process large array in chunks to limit peak memory.
    Useful when processor needs to accumulate temporary data.
    """
    results = []
    for i in range(0, len(data), chunk_size):
        chunk = data[i:i + chunk_size]
        chunk_result = processor(chunk)
        results.append(chunk_result)
        # chunk goes out of scope and can be garbage collected
    return results
 
 
# 2. Comparing memory usage
def memory_comparison():
    """Compare memory usage of different approaches."""
    n = 100000
    
    # Full list
    full_list = [x * 2 for x in range(n)]
    list_size = sys.getsizeof(full_list) + sum(sys.getsizeof(x) for x in full_list[:100]) * (n // 100)
    
    # Generator (lazy evaluation)
    generator = (x * 2 for x in range(n))
    gen_size = sys.getsizeof(generator)
    
    print(f"List of {n} elements: ~{list_size // 1024} KB")
    print(f"Equivalent generator: ~{gen_size} bytes")
 
 
# 3. Buffer reuse pattern
class BufferedProcessor:
    """
    Reuse internal buffer to avoid repeated allocations.
    Useful for processing many small arrays.
    """
    def __init__(self, max_size):
        self.buffer = [None] * max_size
        self.max_size = max_size
    
    def process(self, data, transform):
        """
        Transform data using pre-allocated buffer.
        Returns view of buffer (caller should copy if needed).
        """
        n = len(data)
        if n > self.max_size:
            raise ValueError(f"Data too large: {n} > {self.max_size}")
        
        for i in range(n):
            self.buffer[i] = transform(data[i])
        
        return self.buffer[:n]  # Return slice (view)
 
 
# 4. Streaming aggregation (no intermediate storage)
def streaming_statistics(data_generator):
    """
    Compute statistics without storing all data.
    Works on infinite streams.
    """
    count = 0
    total = 0
    min_val = float('inf')
    max_val = float('-inf')
    
    for x in data_generator:
        count += 1
        total += x
        min_val = min(min_val, x)
        max_val = max(max_val, x)
    
    return {
        'count': count,
        'sum': total,
        'mean': total / count if count > 0 else 0,
        'min': min_val if count > 0 else None,
        'max': max_val if count > 0 else None
    }
 
 
# Demonstration
if __name__ == "__main__":
    memory_comparison()
    
    # Streaming statistics on generated data
    def generate_data():
        for i in range(1000000):
            yield i * 0.5
    
    stats = streaming_statistics(generate_data())
    print(f"\nStreaming stats on 1M generated values:")
    for key, value in stats.items():
        print(f"  {key}: {value}")

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

# Practical Examples: Combining All Techniques
# =============================================
 
# Example 1: Log File Analyzer
# Build multiple outputs, handle streaming, aggregate statistics
 
def analyze_logs(log_entries):
    """
    Analyze log entries, producing:
    - Grouped entries by level
    - Error message frequencies
    - Hourly counts
    
    Single pass builds all outputs.
    """
    by_level = {}          # level -> list of entries
    error_messages = {}    # message -> count
    hourly_counts = {}     # hour -> count
    
    for entry in log_entries:
        level = entry.get('level', 'UNKNOWN')
        hour = entry.get('timestamp', '').split(':')[0]  # Extract hour
        
        # Group by level
        if level not in by_level:
            by_level[level] = []
        by_level[level].append(entry)
        
        # Count error messages
        if level == 'ERROR':
            message = entry.get('message', 'Unknown error')
            error_messages[message] = error_messages.get(message, 0) + 1
        
        # Count by hour
        if hour:
            hourly_counts[hour] = hourly_counts.get(hour, 0) + 1
    
    return {
        'by_level': by_level,
        'error_frequencies': error_messages,
        'hourly_counts': hourly_counts
    }
 
 
# Example 2: Data Pipeline with Pre-allocated Output
# Process transactions with known output size
 
def process_transactions(transactions):
    """
    Process transactions to compute daily summaries.
    Pre-allocates output when size is known.
    """
    # Group transactions by date
    by_date = {}
    for txn in transactions:
        date = txn['date']
        if date not in by_date:
            by_date[date] = []
        by_date[date].append(txn)
    
    # Pre-allocate summary array (one per date)
    dates = sorted(by_date.keys())
    summaries = [None] * len(dates)
    
    for i, date in enumerate(dates):
        day_transactions = by_date[date]
        summaries[i] = {
            'date': date,
            'count': len(day_transactions),
            'total': sum(txn['amount'] for txn in day_transactions),
            'average': sum(txn['amount'] for txn in day_transactions) / len(day_transactions)
        }
    
    return summaries
 
 
# Example 3: In-Place Data Cleaning
# Clean and normalize data without extra allocation
 
def clean_data_in_place(records):
    """
    Clean records in-place:
    1. Normalize string fields (strip, lowercase)
    2. Remove records with missing required fields
    3. Deduplicate by ID
    
    Returns new valid length.
    """
    seen_ids = set()
    write_idx = 0
    
    for read_idx in range(len(records)):
        record = records[read_idx]
        
        # Skip if missing ID
        if 'id' not in record or record['id'] is None:
            continue
        
        # Skip duplicates
        if record['id'] in seen_ids:
            continue
        seen_ids.add(record['id'])
        
        # Normalize string fields in-place
        for key in ['name', 'email', 'category']:
            if key in record and isinstance(record[key], str):
                record[key] = record[key].strip().lower()
        
        # Keep this record
        records[write_idx] = record
        write_idx += 1
    
    return write_idx
 
 
# Example 4: Windowed Aggregation
# Build overlapping window statistics
 
def rolling_average(arr, window_size):
    """
    Compute rolling average with given window size.
    Uses running sum for O(n) instead of O(n*k).
    """
    if len(arr) < window_size:
        return []
    
    n = len(arr)
    result = [0.0] * (n - window_size + 1)
    
    # Compute first window sum
    window_sum = sum(arr[:window_size])
    result[0] = window_sum / window_size
    
    # Slide window: subtract leaving element, add entering element
    for i in range(1, n - window_size + 1):
        window_sum -= arr[i - 1]          # Remove old
        window_sum += arr[i + window_size - 1]  # Add new
        result[i] = window_sum / window_size
    
    return result
 
 
# Demonstration
if __name__ == "__main__":
    # Test log analysis
    logs = [
        {'level': 'INFO', 'timestamp': '10:30:00', 'message': 'Started'},
        {'level': 'ERROR', 'timestamp': '10:35:22', 'message': 'Connection failed'},
        {'level': 'ERROR', 'timestamp': '10:40:00', 'message': 'Connection failed'},
        {'level': 'INFO', 'timestamp': '11:00:00', 'message': 'Recovered'},
        {'level': 'ERROR', 'timestamp': '11:30:00', 'message': 'Timeout'},
    ]
    
    analysis = analyze_logs(logs)
    print("Log Analysis:")
    print(f"  Error frequencies: {analysis['error_frequencies']}")
    print(f"  Hourly counts: {analysis['hourly_counts']}")
    
    # Test rolling average
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    rolling = rolling_average(data, 3)
    print(f"\nRolling average (window=3): {rolling}")