Array Algorithms

Binary Search Fundamentals

Binary search operates on sorted sequences with distinct elements. The algorithm halves the search space repeatedly until locating the target or exhausting the range.

Critical Implementation Details:

1. Midpoint Calculation: Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow in languages with fixed-width integers.

2. Termination: The loop continues while lo <= hi for inclusive bounds.

3. Boundary Adjustment: Move lo to mid + 1 or hi to mid - 1 to avoid infinite loops.

Iterative Implementation:

from typing import List

class BinarySearch:
    def locate(self, arr: List[int], target: int) -> int:
        lo, hi = 0, len(arr) - 1
        
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

Search Insert Position: When the target is absent, the lo pointer naturally indicates the insertion point.

def search_insert(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

Integer Square Root: Apply binary search on the range [1, x] to find the largest integer whose square does not exceed x.

def integer_sqrt(self, x: int) -> int:
    if x < 2:
        return x
    lo, hi = 1, x
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        square = mid * mid
        if square == x:
            return mid
        elif square < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

Perfect Square Check: Returns boolean by verifying if any integer squares to the input.

def is_perfect_square(self, num: int) -> bool:
    lo, hi = 1, num
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        sq = mid * mid
        if sq == num:
            return True
        elif sq < num:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Finding Boundaries: To locate the first and last positions of a target, perform two separate searches—one for the left boundary (first occurrence) and one for the right boundary (last occurrence).

def search_range(self, nums: List[int], target: int) -> List[int]:
    def find_boundary(arr: List[int], tgt: int, find_left: bool) -> int:
        idx = -1
        lo, hi = 0, len(arr) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] == tgt:
                idx = mid
                if find_left:
                    hi = mid - 1
                else:
                    lo = mid + 1
            elif arr[mid] < tgt:
                lo = mid + 1
            else:
                hi = mid - 1
        return idx
    
    left = find_boundary(nums, target, True)
    if left == -1:
        return [-1, -1]
    right = find_boundary(nums, target, False)
    return [left, right]

Two-Pointer Techniques

In-Place Removal: Process arrays without allocating additional storage by maintaining read and write pointers.

def remove_element(self, nums: List[int], val: int) -> int:
    writer = 0
    for reader in range(len(nums)):
        if nums[reader] != val:
            nums[writer] = nums[reader]
            writer += 1
    return writer

Bidirectional Removal: Alternate approach using pointers at both ends, swapping valid elements toward the front.

def remove_element_bidirectional(self, nums: List[int], val: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        while left <= right and nums[left] != val:
            left += 1
        while left <= right and nums[right] == val:
            right -= 1
        if left < right:
            nums[left] = nums[right]
            left += 1
            right -= 1
    return left

Duplicate Removal: For sorted arrays, skip consecutive identical values by comparing adjacent elements.

def remove_duplicates(self, nums: List[int]) -> int:
    if not nums:
        return 0
    anchor = 1
    for scout in range(1, len(nums)):
        if nums[scout] != nums[scout - 1]:
            nums[anchor] = nums[scout]
            anchor += 1
    return anchor

Zero Relocation: Partition the array by moving non-zero elements forward, then filling the remainder with zeros.

def move_zeroes(self, nums: List[int]) -> None:
    insert_pos = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[insert_pos] = nums[i]
            insert_pos += 1
    for i in range(insert_pos, len(nums)):
        nums[i] = 0

String Backspace Processing: Traverse from right to left, using counters to skip characters marked for deletion.

def backspace_compare(self, s: str, t: str) -> bool:
    i, j = len(s) - 1, len(t) - 1
    skip_s = skip_t = 0
    
    while i >= 0 or j >= 0:
        while i >= 0:
            if s[i] == '#':
                skip_s += 1
                i -= 1
            elif skip_s > 0:
                skip_s -= 1
                i -= 1
            else:
                break
        
        while j >= 0:
            if t[j] == '#':
                skip_t += 1
                j -= 1
            elif skip_t > 0:
                skip_t -= 1
                j -= 1
            else:
                break
        
        if i >= 0 and j >= 0 and s[i] != t[j]:
            return False
        if (i >= 0) != (j >= 0):
            return False
        i -= 1
        j -= 1
    return True

Sorted Squares: Since the input is sorted by absolute value (negatives decreasing, positives increasing), merge from both ends toward the center.

def sorted_squares(self, nums: List[int]) -> List[int]:
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    position = n - 1
    
    while left <= right:
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[position] = left_sq
            left += 1
        else:
            result[position] = right_sq
            right -= 1
        position -= 1
    return result

Sliding Window Strategy

Minimum Size Subarray: Expand the window until the sum meets the target, then contract from the left to find the minimum valid length.

def min_subarray_len(self, target: int, nums: List[int]) -> int:
    window_start = curr_sum = 0
    min_length = float('inf')
    
    for window_end in range(len(nums)):
        curr_sum += nums[window_end]
        
        while curr_sum >= target:
            min_length = min(min_length, window_end - window_start + 1)
            curr_sum -= nums[window_start]
            window_start += 1
    
    return 0 if min_length == float('inf') else min_length

Fruit Into Baskets: Find the longest contiguous subarray containing at most two distinct values (fruit types).

def total_fruit(self, fruits: List[int]) -> int:
    from collections import defaultdict
    basket = defaultdict(int)
    max_fruits = 0
    start = 0
    
    for end in range(len(fruits)):
        basket[fruits[end]] += 1
        
        while len(basket) > 2:
            basket[fruits[start]] -= 1
            if basket[fruits[start]] == 0:
                del basket[fruits[start]]
            start += 1
        
        max_fruits = max(max_fruits, end - start + 1)
    return max_fruits

Minimum Window Substring: Track character frequencies required from string t, using a counter to determine when the window becomes validd.

def min_window(self, s: str, t: str) -> str:
    from collections import Counter
    
    required = Counter(t)
    missing = len(t)
    best_left, best_len = -1, len(s) + 1
    left = 0
    
    for right, char in enumerate(s):
        if required[char] > 0:
            missing -= 1
        required[char] -= 1
        
        while missing == 0:
            if right - left < best_len:
                best_left, best_len = left, right - left
            required[s[left]] += 1
            if required[s[left]] > 0:
                missing += 1
            left += 1
    
    return "" if best_left == -1 else s[best_left:best_left + best_len + 1]

Matrix Traveersal

Spiral Matrix Generation: Populate an n×n matrix in spiral order using boundary markers.

def generate_matrix(self, n: int) -> List[List[int]]:
    matrix = [[0] * n for _ in range(n)]
    top, bottom = 0, n - 1
    left, right = 0, n - 1
    num = 1
    
    while num <= n * n:
        for c in range(left, right + 1):
            matrix[top][c] = num
            num += 1
        top += 1
        
        for r in range(top, bottom + 1):
            matrix[r][right] = num
            num += 1
        right -= 1
        
        for c in range(right, left - 1, -1):
            matrix[bottom][c] = num
            num += 1
        bottom -= 1
        
        for r in range(bottom, top - 1, -1):
            matrix[r][left] = num
            num += 1
        left += 1
    
    return matrix

Spiral Order Extraction: Traverse an m×n matrix in spiral sequence, checking boundary collisions.

def spiral_order(self, matrix: List[List[int]]) -> List[int]:
    if not matrix:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while True:
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1
        if top > bottom:
            break
        
        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1
        if left > right:
            break
        
        for c in range(right, left - 1, -1):
            result.append(matrix[bottom][c])
        bottom -= 1
        if top > bottom:
            break
        
        for r in range(bottom, top - 1, -1):
            result.append(matrix[r][left])
        left += 1
        if left > right:
            break
    
    return result

Linked List Patterns

Node Definition and Structure

Linked lists consist of nodes containing data and a reference to the subsequent node. Unlike arrays, memory allocation is non-contiguous.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Sentinel Node Pattern: Using a dummy head node simplifies edge cases where the actual head might be removed or modified.

Basic Operations

Element Removal: Skip nodes matching the target value by adjusting predecessor references.

def remove_elements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
    sentinel = ListNode(0, head)
    current = sentinel
    
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return sentinel.next

Custom Linked List Design: Implementing a singly linked list with index-based access requires traversal from the head.

class MyLinkedList:
    def __init__(self):
        self.sentinel = ListNode(0)
        self.size = 0
    
    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        node = self.sentinel.next
        for _ in range(index):
            node = node.next
        return node.val
    
    def add_at_head(self, val: int) -> None:
        self.add_at_index(0, val)
    
    def add_at_tail(self, val: int) -> None:
        self.add_at_index(self.size, val)
    
    def add_at_index(self, index: int, val: int) -> None:
        if index > self.size:
            return
        index = max(0, index)
        predecessor = self.sentinel
        for _ in range(index):
            predecessor = predecessor.next
        predecessor.next = ListNode(val, predecessor.next)
        self.size += 1
    
    def delete_at_index(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        predecessor = self.sentinel
        for _ in range(index):
            predecessor = predecessor.next
        predecessor.next = predecessor.next.next
        self.size -= 1

Doubly Linked List Variant: Bidirectional traversal optimizes operations near the tail.

class DListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class MyDoublyLinkedList:
    def __init__(self):
        self.head = self.tail = None
        self.size = 0
    
    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        if index < self.size // 2:
            node = self.head
            for _ in range(index):
                node = node.next
        else:
            node = self.tail
            for _ in range(self.size - index - 1):
                node = node.prev
        return node.val

Advanced Manipulations

In-Place Reversal: Iterate through the list, reversing link directions iterative.

def reverse_list(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Recursive Reversal: Alternative approach using call stack for backward traversal.

def reverse_list_recursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    new_head = self.reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Pairwise Swapping: Exchange adjacent nodes by modifying three pointers per pair.

def swap_pairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    sentinel = ListNode(0, head)
    prev = sentinel
    
    while prev.next and prev.next.next:
        first = prev.next
        second = prev.next.next
        
        prev.next = second
        first.next = second.next
        second.next = first
        prev = first
    
    return sentinel.next

Nth Node Removal: Maintain a gap of n nodes between leader and follower pointers.

def remove_nth_from_end(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    sentinel = ListNode(0, head)
    leader = follower = sentinel
    
    for _ in range(n + 1):
        leader = leader.next
    
    while leader:
        leader = leader.next
        follower = follower.next
    
    follower.next = follower.next.next
    return sentinel.next

Intersection Detection: Align the traversal by swapping starting points when reaching the end.

def get_intersection_node(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    ptr_a, ptr_b = headA, headB
    
    while ptr_a != ptr_b:
        ptr_a = ptr_a.next if ptr_a else headB
        ptr_b = ptr_b.next if ptr_b else headA
    
    return ptr_a

Cycle Detection and Entry: Floyd's Tortoise and Hare algorithm detects cycles; when pointers meet, reset one to head and advance both at equal speed to find the entry point.

def detect_cycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return None
    
    tortoise = head.next
    hare = head.next.next if head.next else None
    
    while hare and hare.next:
        if tortoise == hare:
            break
        tortoise = tortoise.next
        hare = hare.next.next
    
    if not hare or not hare.next:
        return None
    
    tortoise = head
    while tortoise != hare:
        tortoise = tortoise.next
        hare = hare.next
    
    return tortoise