Algorithms All in One

This section contains code for all the important algorithms in one place.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            low = mid + 1  # Move to the right half
        else:
            high = mid - 1  # Move to the left half

    return -1  # Target not found

Breadth First Search (BFS)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Depth First Search (DFS)

def dfs(graph, visited, vertex):
    visited.add(vertex)
    print(vertex, end=" ")

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, visited, neighbor)

# Wrapper function to initialize visited set
def dfs_start(graph, start):
    visited = set()
    dfs(graph, visited, start)

Sliding Window

def sliding_window(arr):
    # Initialize window boundaries and result
    left = right = 0
    result = 0
    window = {}  # or other data structure as needed

    while right < len(arr):
        # 1. Expand: add element at right pointer
        window[arr[right]] = window.get(arr[right], 0) + 1

        # 2. Contract: if window needs shrinking
        while left <= right and /* condition to shrink window */:
            # Remove element at left pointer
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1

        # 3. Update result using current window
        result = max(result, right - left + 1)  # or other calculation

        right += 1

    return result

Two Pointers

Note

Two Pointers approach is too broad to be covered in a single snippet. This section will contain the snippet for a classic two pointers problem.

def max_area(height):
    max_water = 0
    left, right = 0, len(height) - 1

    while left < right:
        # Calculate width * height
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        # Move the pointer with smaller height
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

Dynamic Programming

Note

DP is too broad to be covered in a single snippet. This section will contain the snippet for a classic DP problem.

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill the dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                # If characters match, add 1 to diagonal value
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # If they don't match, take max of left and up
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Greedy

Note

Greedy algorithms make locally optimal choices at each step. This section contains a classic greedy problem implementation.

def can_jump(nums: List[int]) -> bool:
    max_reach = 0
    n = len(nums)

    for i in range(n):
        # If we can't reach current index
        if i > max_reach:
            return False

        # Update the farthest index we can reach
        max_reach = max(max_reach, i + nums[i])

        # If we can reach the last index
        if max_reach >= n - 1:
            return True

    return True

Bit Manipulation

Note

Bit manipulation involves operating on individual bits of numbers. This section contains a classic bit manipulation problem.

def single_number(nums: List[int]) -> int:
    result = 0

    # XOR all numbers together
    # Properties used:
    # 1. a ^ a = 0 (XOR with self gives 0)
    # 2. a ^ 0 = a (XOR with 0 gives number itself)
    # 3. a ^ b ^ a = b (XOR is associative)
    for num in nums:
        result ^= num

    return result

Backtracking

Note

Backtracking is an algorithmic technique that considers searching every possible combination in order to solve a computational problem. This section contains a classic backtracking problem.

def backtrack(start, curr, result):
    # Add current subset to result
    result.append(curr[:])

    # Try adding each remaining number
    for i in range(start, len(nums)):
        # Include nums[i]
        curr.append(nums[i])

        # Recur with next position
        backtrack(i + 1, curr, result)

        # Backtrack by removing nums[i]
        curr.pop()

Merge Sort

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1