Arrays and Strings

📖 Introduction

Arrays and strings are the workhorses of programming. In my projects, I constantly work with lists of data—user records, log entries, API responses—and string manipulation for parsing, validation, and formatting. Understanding how Python implements these structures, and mastering the algorithmic techniques for processing them efficiently, has been fundamental to writing performant code.

This article covers Python's list and string internals, essential techniques like two-pointer and sliding window, and the most common array/string problems you'll encounter.

🎯 Python List Internals

Python lists are dynamic arrays—contiguous memory blocks that resize automatically.

Memory Layout

import sys

# Lists are over-allocated for efficiency
lst = []
print(f"Empty list: {sys.getsizeof(lst)} bytes")

for i in range(20):
    lst.append(i)
    print(f"Length {len(lst):2d}: {sys.getsizeof(lst)} bytes")

# Output shows capacity jumps:
# Length  1: 88 bytes
# Length  5: 120 bytes
# Length  9: 184 bytes
# ...

Time Complexity of List Operations

Operation

Average

Worst

Notes

lst[i]

O(1)

Direct index access

lst.append(x)

O(1)*

O(n)

Amortized O(1)

lst.pop()

O(1)

Remove from end

lst.pop(0)

O(n)

Shift all elements

lst.insert(i, x)

O(n)

Shift elements after i

x in lst

O(n)

Linear search

lst[i:j]

O(j-i)

Create new list

lst.sort()

O(n log n)

Timsort

from collections import deque

# Inefficient: O(n) for each pop(0)
def process_queue_list(items: list):
    while items:
        item = items.pop(0)  # O(n) - shifts all elements!
        process(item)

# Efficient: O(1) for each popleft()
def process_queue_deque(items: list):
    queue = deque(items)
    while queue:
        item = queue.popleft()  # O(1)
        process(item)

📝 Python String Internals

Strings in Python are immutable sequences of Unicode characters.

Immutability Implications

# Strings are immutable - each operation creates a new string
s = "hello"
s = s + " world"  # Creates new string, old one garbage collected

# Inefficient string concatenation: O(n²)
def bad_string_build(words: list) -> str:
    result = ""
    for word in words:
        result += word  # Creates new string each time!
    return result

# Efficient string building: O(n)
def good_string_build(words: list) -> str:
    return "".join(words)  # Single string creation


# Benchmark
import time

words = ["word"] * 10000

start = time.perf_counter()
bad_string_build(words)
print(f"Concatenation: {time.perf_counter() - start:.4f}s")

start = time.perf_counter()
good_string_build(words)
print(f"Join: {time.perf_counter() - start:.4f}s")

String Interning

# Python interns small strings and identifiers
a = "hello"
b = "hello"
print(a is b)  # True - same object in memory

# But not all strings
c = "hello world!"
d = "hello world!"
print(c is d)  # May be False - not interned

# Use == for string comparison, not 'is'

👆 Two-Pointer Technique

Two pointers is a pattern where you use two indices to traverse an array, often from opposite ends or at different speeds.

Pattern 1: Opposite Direction

def two_sum_sorted(arr: list, target: int) -> tuple:
    """
    Find pair summing to target in sorted array.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum
    
    return None


def is_palindrome(s: str) -> bool:
    """
    Check if string is palindrome.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True


def reverse_array_inplace(arr: list) -> list:
    """
    Reverse array without extra space.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    
    return arr

Pattern 2: Same Direction (Fast/Slow)

def remove_duplicates_sorted(arr: list) -> int:
    """
    Remove duplicates from sorted array in-place.
    Returns new length.
    Time: O(n), Space: O(1)
    """
    if not arr:
        return 0
    
    # slow: position to write next unique element
    # fast: scanning through array
    slow = 0
    
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    
    return slow + 1


def move_zeros(arr: list) -> list:
    """
    Move all zeros to end, maintain relative order.
    Time: O(n), Space: O(1)
    """
    # slow: next position for non-zero
    slow = 0
    
    for fast in range(len(arr)):
        if arr[fast] != 0:
            arr[slow], arr[fast] = arr[fast], arr[slow]
            slow += 1
    
    return arr


def partition_array(arr: list, pivot: int) -> list:
    """
    Partition: elements < pivot, then >= pivot.
    Time: O(n), Space: O(1)
    """
    slow = 0
    
    for fast in range(len(arr)):
        if arr[fast] < pivot:
            arr[slow], arr[fast] = arr[fast], arr[slow]
            slow += 1
    
    return arr

Pattern 3: Three Pointers

def sort_colors(arr: list) -> list:
    """
    Dutch National Flag problem.
    Sort array of 0s, 1s, and 2s in-place.
    Time: O(n), Space: O(1)
    """
    low, mid, high = 0, 0, len(arr) - 1
    
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
    
    return arr


def three_sum(arr: list, target: int) -> list:
    """
    Find all triplets summing to target.
    Time: O(n²), Space: O(1) excluding output
    """
    arr.sort()
    result = []
    
    for i in range(len(arr) - 2):
        # Skip duplicates for first element
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        
        # Two-pointer for remaining two elements
        left, right = i + 1, len(arr) - 1
        
        while left < right:
            total = arr[i] + arr[left] + arr[right]
            
            if total == target:
                result.append([arr[i], arr[left], arr[right]])
                
                # Skip duplicates
                while left < right and arr[left] == arr[left + 1]:
                    left += 1
                while left < right and arr[right] == arr[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
    
    return result

🪟 Sliding Window Technique

Sliding window maintains a "window" over contiguous elements, sliding it to process subarrays/substrings efficiently.

Fixed-Size Window

def max_sum_subarray(arr: list, k: int) -> int:
    """
    Maximum sum of any subarray of size k.
    Time: O(n), Space: O(1)
    """
    if len(arr) < k:
        return None
    
    # Calculate initial window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window: remove left, add right
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum


def find_all_averages(arr: list, k: int) -> list:
    """
    Find averages of all subarrays of size k.
    Time: O(n), Space: O(n-k+1)
    """
    if len(arr) < k:
        return []
    
    averages = []
    window_sum = sum(arr[:k])
    averages.append(window_sum / k)
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        averages.append(window_sum / k)
    
    return averages

Variable-Size Window

def min_subarray_sum(arr: list, target: int) -> int:
    """
    Minimum length subarray with sum >= target.
    Time: O(n), Space: O(1)
    """
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    for right in range(len(arr)):
        window_sum += arr[right]
        
        # Shrink window while condition met
        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0


def longest_substring_k_distinct(s: str, k: int) -> int:
    """
    Longest substring with at most k distinct characters.
    Time: O(n), Space: O(k)
    """
    from collections import defaultdict
    
    char_count = defaultdict(int)
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        char_count[s[right]] += 1
        
        # Shrink while too many distinct chars
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length


def longest_substring_no_repeat(s: str) -> int:
    """
    Longest substring without repeating characters.
    Time: O(n), Space: O(min(n, alphabet_size))
    """
    char_index = {}  # char -> last seen index
    max_length = 0
    left = 0
    
    for right, char in enumerate(s):
        # If char seen and within current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

📊 Prefix Sum Technique

Prefix sums enable O(1) range sum queries after O(n) preprocessing.

def build_prefix_sum(arr: list) -> list:
    """
    Build prefix sum array.
    prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
    """
    prefix = [0] * (len(arr) + 1)
    for i, num in enumerate(arr):
        prefix[i + 1] = prefix[i] + num
    return prefix


def range_sum(prefix: list, left: int, right: int) -> int:
    """
    Sum of arr[left:right+1] in O(1).
    """
    return prefix[right + 1] - prefix[left]


# Example
arr = [1, 2, 3, 4, 5]
prefix = build_prefix_sum(arr)  # [0, 1, 3, 6, 10, 15]

print(range_sum(prefix, 1, 3))  # 2 + 3 + 4 = 9


def subarray_sum_equals_k(arr: list, k: int) -> int:
    """
    Count subarrays with sum exactly k.
    Time: O(n), Space: O(n)
    """
    from collections import defaultdict
    
    count = 0
    current_sum = 0
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1  # Empty prefix
    
    for num in arr:
        current_sum += num
        
        # If (current_sum - k) seen before, we found a subarray
        if current_sum - k in prefix_counts:
            count += prefix_counts[current_sum - k]
        
        prefix_counts[current_sum] += 1
    
    return count

🔄 Common Array Problems

Kadane's Algorithm (Maximum Subarray)

def max_subarray_sum(arr: list) -> int:
    """
    Find maximum sum of contiguous subarray.
    Kadane's Algorithm.
    Time: O(n), Space: O(1)
    """
    if not arr:
        return 0
    
    max_sum = current_sum = arr[0]
    
    for num in arr[1:]:
        # Either extend current subarray or start new
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum


def max_subarray_with_indices(arr: list) -> tuple:
    """
    Return max sum and start/end indices.
    """
    if not arr:
        return (0, -1, -1)
    
    max_sum = current_sum = arr[0]
    start = end = temp_start = 0
    
    for i in range(1, len(arr)):
        if arr[i] > current_sum + arr[i]:
            current_sum = arr[i]
            temp_start = i
        else:
            current_sum += arr[i]
        
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
    
    return (max_sum, start, end)

Merge Intervals

def merge_intervals(intervals: list) -> list:
    """
    Merge overlapping intervals.
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return []
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        
        if start <= last_end:  # Overlapping
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])
    
    return merged


# Example
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))  # [[1, 6], [8, 10], [15, 18]]

Rotate Array

def rotate_right(arr: list, k: int) -> list:
    """
    Rotate array right by k positions.
    Time: O(n), Space: O(1)
    """
    n = len(arr)
    k = k % n  # Handle k > n
    
    def reverse(start: int, end: int):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    # Reverse entire array, then reverse parts
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)
    
    return arr


# Example: [1, 2, 3, 4, 5] rotated by 2
# Step 1: Reverse all → [5, 4, 3, 2, 1]
# Step 2: Reverse first k → [4, 5, 3, 2, 1]
# Step 3: Reverse rest → [4, 5, 1, 2, 3]

🔤 Common String Problems

Anagram Check

from collections import Counter

def is_anagram(s1: str, s2: str) -> bool:
    """
    Check if s2 is anagram of s1.
    Time: O(n), Space: O(1) - 26 letters max
    """
    return Counter(s1) == Counter(s2)


def find_anagrams(s: str, p: str) -> list:
    """
    Find all anagram starting indices of p in s.
    Time: O(n), Space: O(1)
    """
    if len(p) > len(s):
        return []
    
    p_count = Counter(p)
    window_count = Counter(s[:len(p)])
    result = []
    
    if window_count == p_count:
        result.append(0)
    
    for i in range(len(p), len(s)):
        # Add new char, remove old char
        window_count[s[i]] += 1
        old_char = s[i - len(p)]
        window_count[old_char] -= 1
        
        if window_count[old_char] == 0:
            del window_count[old_char]
        
        if window_count == p_count:
            result.append(i - len(p) + 1)
    
    return result

Valid Parentheses (Stack-based)

def is_valid_parentheses(s: str) -> bool:
    """
    Check if parentheses are balanced.
    Time: O(n), Space: O(n)
    """
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    
    return len(stack) == 0

Longest Common Prefix

def longest_common_prefix(strs: list) -> str:
    """
    Find longest common prefix among strings.
    Time: O(S) where S is sum of all characters
    Space: O(1)
    """
    if not strs:
        return ""
    
    # Find shortest string length
    min_len = min(len(s) for s in strs)
    
    for i in range(min_len):
        char = strs[0][i]
        for s in strs[1:]:
            if s[i] != char:
                return strs[0][:i]
    
    return strs[0][:min_len]


def lcp_binary_search(strs: list) -> str:
    """
    Binary search approach.
    Time: O(S log m) where m is min string length
    """
    if not strs:
        return ""
    
    min_len = min(len(s) for s in strs)
    
    def is_common_prefix(length: int) -> bool:
        prefix = strs[0][:length]
        return all(s.startswith(prefix) for s in strs)
    
    low, high = 0, min_len
    
    while low < high:
        mid = (low + high + 1) // 2
        if is_common_prefix(mid):
            low = mid
        else:
            high = mid - 1
    
    return strs[0][:low]

📝 Practice Exercises

Exercise 1: Container With Most Water

def max_water(heights: list) -> int:
    """
    Find max water that can be contained between two lines.
    Area = min(height[i], height[j]) * (j - i)
    """
    # Hint: Two pointers from opposite ends
    pass

Solution

def max_water(heights: list) -> int:
    left, right = 0, len(heights) - 1
    max_area = 0
    
    while left < right:
        width = right - left
        height = min(heights[left], heights[right])
        max_area = max(max_area, width * height)
        
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

Exercise 2: Minimum Window Substring

def min_window(s: str, t: str) -> str:
    """
    Find minimum window in s containing all characters of t.
    """
    # Hint: Sliding window with character counts
    pass

Solution

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    
    t_count = Counter(t)
    required = len(t_count)
    
    left = 0
    formed = 0
    window_count = {}
    result = (float('inf'), None, None)
    
    for right, char in enumerate(s):
        window_count[char] = window_count.get(char, 0) + 1
        
        if char in t_count and window_count[char] == t_count[char]:
            formed += 1
        
        while left <= right and formed == required:
            if right - left + 1 < result[0]:
                result = (right - left + 1, left, right)
            
            left_char = s[left]
            window_count[left_char] -= 1
            
            if left_char in t_count and window_count[left_char] < t_count[left_char]:
                formed -= 1
            
            left += 1
    
    return "" if result[0] == float('inf') else s[result[1]:result[2] + 1]

Exercise 3: Product of Array Except Self

def product_except_self(arr: list) -> list:
    """
    Return array where each element is product of all others.
    Cannot use division. Must be O(n) time.
    """
    pass

Solution

def product_except_self(arr: list) -> list:
    n = len(arr)
    result = [1] * n
    
    # Left products
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= arr[i]
    
    # Right products
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= arr[i]
    
    return result

🔑 Key Takeaways

Python lists are dynamic arrays with O(1) amortized append
Strings are immutable—use join() for efficient concatenation
Two pointers solve many problems in O(n) time
Sliding window efficiently processes contiguous subarrays
Prefix sums enable O(1) range queries
Know your techniques—most problems combine these patterns

🚀 What's Next?

In the next article, we'll explore linked lists:

Singly and doubly linked list implementation
Pointer manipulation techniques
Fast/slow pointer (Floyd's algorithm)
Common linked list problems

Next: Article 5 - Linked Lists

📚 References

Python Wiki: TimeComplexity
LeetCode Array/String problems
"Cracking the Coding Interview" - Arrays and Strings chapter

PreviousRecursion and Recursive Thinking NextLinked Lists

Last updated 1 month ago

hashtag📖 Introduction

hashtag🎯 Python List Internals

hashtagMemory Layout

hashtagTime Complexity of List Operations

hashtag📝 Python String Internals

hashtagImmutability Implications

hashtagString Interning

hashtag👆 Two-Pointer Technique

hashtagPattern 1: Opposite Direction

hashtagPattern 2: Same Direction (Fast/Slow)

hashtagPattern 3: Three Pointers

hashtag🪟 Sliding Window Technique

hashtagFixed-Size Window

hashtagVariable-Size Window

hashtag📊 Prefix Sum Technique

hashtag🔄 Common Array Problems

hashtagKadane's Algorithm (Maximum Subarray)

hashtagMerge Intervals

hashtagRotate Array

hashtag🔤 Common String Problems

hashtagAnagram Check

hashtagValid Parentheses (Stack-based)

hashtagLongest Common Prefix

hashtag📝 Practice Exercises

hashtagExercise 1: Container With Most Water

hashtagExercise 2: Minimum Window Substring

hashtagExercise 3: Product of Array Except Self

hashtag🔑 Key Takeaways

hashtag🚀 What's Next?

hashtag📚 References

📖 Introduction

🎯 Python List Internals

Memory Layout

Time Complexity of List Operations

📝 Python String Internals

Immutability Implications

String Interning

👆 Two-Pointer Technique

Pattern 1: Opposite Direction

Pattern 2: Same Direction (Fast/Slow)

Pattern 3: Three Pointers

🪟 Sliding Window Technique

Fixed-Size Window

Variable-Size Window

📊 Prefix Sum Technique

🔄 Common Array Problems

Kadane's Algorithm (Maximum Subarray)

Merge Intervals

Rotate Array

🔤 Common String Problems

Anagram Check

Valid Parentheses (Stack-based)

Longest Common Prefix

📝 Practice Exercises

Exercise 1: Container With Most Water

Exercise 2: Minimum Window Substring

Exercise 3: Product of Array Except Self

🔑 Key Takeaways

🚀 What's Next?

📚 References