Arrays and Strings: Fundamentals

# Array: Contiguous memory allocation
# Fixed size (in most languages)

# Memory layout
array_memory = {
    "index": [0,   1,   2,   3,   4,   5],
    "value": [10,  25,  33,  47,  62,  99],
    "memory": ["@100", "@104", "@108", "@112", "@116", "@120"]
}
# Each int takes 4 bytes (typical)

class Array:
    """Simple array implementation"""
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.data = [None] * capacity
    
    def get(self, index):
        """O(1) - Direct access by index"""
        if 0 <= index < self.size:
            return self.data[index]
        raise IndexError("Index out of bounds")
    
    def set(self, index, value):
        """O(1) - Set value at index"""
        if 0 <= index < self.size:
            self.data[index] = value
        else:
            raise IndexError("Index out of bounds")
    
    def append(self, value):
        """O(1) amortized - Add to end"""
        if self.size == self.capacity:
            self._resize()
        self.data[self.size] = value
        self.size += 1
    
    def insert(self, index, value):
        """O(n) - Insert at index"""
        if self.size == self.capacity:
            self._resize()
        
        # 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 delete(self, index):
        """O(n) - Delete at index"""
        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
        return value
    
    def _resize(self):
        """O(n) - Double capacity"""
        new_data = [None] * (self.capacity * 2)
        for i in range(self.capacity):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity *= 2

# Array operations complexity

array_complexity = {
    "access": "O(1)",
    "search": "O(n)",
    "insertion": "O(n)",
    "deletion": "O(n)",
    "append": "O(1) amortized"
}

# 2D Array / Matrix

matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]

# Access element
def get_element(matrix, row, col):
    return matrix[row][col]  # O(1)

# Traverse matrix
def traverse_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    
    for i in range(rows):
        for j in range(cols):
            print(matrix[i][j], end=" ")
        print()

# Diagonal traversal
def diagonal_traverse(matrix):
    if not matrix or not matrix[0]:
        return []
    
    result = []
    for d in range(len(matrix) + len(matrix[0]) - 1):
        row = min(d, len(matrix) - 1)
        col = d - row
        
        if d % 2 == 0:
            # Even diagonals: bottom-left to top-right
            while row >= 0 and col < len(matrix[0]):
                result.append(matrix[row][col])
                row -= 1
                col += 1
        else:
            # Odd diagonals: top-right to bottom-left
            col = min(d, len(matrix[0]) - 1)
            row = d - col
            while col >= 0 and row < len(matrix):
                result.append(matrix[row][col])
                row += 1
                col -= 1
    
    return result

# Strings are arrays of characters
# Most languages: immutable (Python, Java)
# Some: mutable (C++, C#)

# String creation
s = "hello world"
chars = ['h', 'e', 'l', 'l', 'o']

# String operations
string_operations = {
    "length": len(s),                    # O(1) - stored
    "access": s[0],                       # O(1)
    "concatenation": s + "!",             # O(n)
    "substring": s[0:5],                  # O(k)
    "search": s.find("world"),            # O(n)
}

# String manipulation functions

def reverse_string(s):
    """Reverse a string"""
    return s[::-1]

def reverse_words(s):
    """Reverse words in a string"""
    return ' '.join(s.split()[::-1])

def is_palindrome(s):
    """Check if string is palindrome"""
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

def count_characters(s):
    """Count character frequency"""
    from collections import Counter
    return Counter(s)

def is_anagram(s1, s2):
    """Check if two strings are anagrams"""
    return sorted(s1) == sorted(s2)

def longest_unique_substring(s):
    """Find longest substring without repeating"""
    seen = {}
    start = 0
    max_length = 0
    result = ""
    
    for i, char in enumerate(s):
        if char in seen and seen[char] >= start:
            start = seen[char] + 1
        
        if i - start + 1 > max_length:
            max_length = i - start + 1
            result = s[start:i+1]
        
        seen[char] = i
    
    return result

# Brute force search
def naive_search(text, pattern):
    """O(n*m) time complexity"""
    matches = []
    
    for i in range(len(text) - len(pattern) + 1):
        match = True
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            matches.append(i)
    
    return matches


# KMP Algorithm (Knuth-Morris-Pratt)
def kmp_search(text, pattern):
    """O(n + m) time complexity"""
    if not pattern:
        return [0]
    
    # Build LPS (Longest Prefix Suffix) array
    lps = [0] * len(pattern)
    length = 0
    i = 1
    
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    # Search
    matches = []
    i = j = 0
    
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == len(pattern):
            matches.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return matches


# Rabin-Karp Algorithm
def rabin_karp(text, pattern, d=256, q=101):
    """O(n + m) average time"""
    n, m = len(text), len(pattern)
    h = pow(d, m - 1, q)
    p = t = 0
    
    # Calculate hash
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q
    
    matches = []
    
    for i in range(n - m + 1):
        if p == t:
            if text[i:i+m] == pattern:
                matches.append(i)
        
        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
            if t < 0:
                t += q
    
    return matches

# Fixed sliding window
def find_max_sum(arr, k):
    """Find maximum sum of k consecutive elements"""
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum


# Variable sliding window
def min_subarray_len(target, nums):
    """Find minimum length of subarray with sum >= target"""
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    for right in range(len(nums)):
        window_sum += nums[right]
        
        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= nums[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0


# Longest substring with k distinct characters
def longest_k_distinct(s, k):
    if k == 0:
        return 0
    
    char_count = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        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

# Remove duplicates from sorted array
def remove_duplicates(nums):
    """In-place, returns new length"""
    if not nums:
        return 0
    
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1


# Container with most water
def max_area(height):
    """Two pointer approach"""
    left = 0
    right = len(height) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water


# 3Sum problem
def three_sum(nums):
    """Find all unique triplets that sum to 0"""
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    
    return result

# Prefix sum for range queries
class PrefixSum:
    def __init__(self, nums):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)
    
    def range_sum(self, left, right):
        """O(1) range sum query"""
        return self.prefix[right + 1] - self.prefix[left]


# Subarray sum equals k
def subarray_sum(nums, k):
    """Count subarrays with sum k"""
    count = 0
    prefix_sum = 0
    prefix_counts = {0: 1}
    
    for num in nums:
        prefix_sum += num
        
        if prefix_sum - k in prefix_counts:
            count += prefix_counts[prefix_sum - k]
        
        prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1
    
    return count

# Find missing positive
def first_missing_positive(nums):
    """Find smallest missing positive integer"""
    n = len(nums)
    
    # Place each number in its correct position
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            correct_idx = nums[i] - 1
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
    
    # Find first position with wrong value
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    
    return n + 1


# Find duplicates
def find_duplicates(nums):
    """Find all duplicates using negative marking"""
    duplicates = []
    
    for num in nums:
        idx = abs(num)
        
        if nums[idx] < 0:
            duplicates.append(idx)
        else:
            nums[idx] = -nums[idx]
    
    return duplicates

# Problem: Find two numbers that add to target
# Return their indices

# Solution 1: Brute force - O(n²)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# Solution 2: Hash map - O(n)
def two_sum_hashmap(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Solution 3: Two pointers (sorted array) - O(n log n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    
    while left < right:
        current = nums[left] + nums[right]
        
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    
    return []

# Problem: Find contiguous subarray with largest sum

def max_subarray(nums):
    """Kadane's Algorithm - O(n)"""
    max_sum = nums[0]
    current_sum = nums[0]
    
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum


def max_subarray_with_indices(nums):
    """Also return start and end indices"""
    max_sum = nums[0]
    current_sum = nums[0]
    start = end = 0
    temp_start = 0
    
    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            temp_start = i
        else:
            current_sum += nums[i]
        
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
    
    return max_sum, start, end

def compress_string(s):
    """Compress string like 'aabbbc' -> 'a2b3c1'"""
    if not s:
        return s
    
    result = []
    count = 1
    
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1
        else:
            result.append(s[i-1] + str(count))
            count = 1
    
    result.append(s[-1] + str(count))
    
    compressed = ''.join(result)
    return compressed if len(compressed) < len(s) else s