Algorithms All in One

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

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            low = mid + 1; // Search in the right half
        } else {
            high = mid - 1; // Search in the left half
        }
    }

    return -1; // Target not found
}

Breadth First Search (BFS)

void bfs(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        cout << vertex << " ";

        for (int neighbor : graph[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

Depth First Search (DFS)

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int vertex) {
    visited[vertex] = true;
    cout << vertex << " ";

    for (int neighbor : graph[vertex]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor);
        }
    }
}

// Wrapper function to initialize visited array
void dfsStart(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    dfs(graph, visited, start);
}

Sliding Window

int slidingWindow(vector<int>& arr) {
    int result = 0;
    int left = 0, right = 0;
    unordered_map<int, int> window;  // or other data structure as needed

    while (right < arr.size()) {
        // 1. Add the right element to window
        window[arr[right]]++;

        // 2. Contract window if needed
        while (left <= right && /* condition to shrink window */) {
            // Remove left element from window
            window[arr[left]]--;
            if (window[arr[left]] == 0) {
                window.erase(arr[left]);
            }
            left++;
        }

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

        right++;
    }

    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.

int maxArea(vector<int>& height) {
    int maxWater = 0;
    int left = 0;
    int right = height.size() - 1;

    while (left < right) {
        // Calculate width * height
        int width = right - left;
        int h = min(height[left], height[right]);
        maxWater = max(maxWater, width * h);

        // Move the pointer with smaller height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

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.

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Fill the dp table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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.

bool canJump(vector<int>& nums) {
    int maxReach = 0;
    int n = nums.size();

    for (int i = 0; i <= maxReach; i++) {
        // If we can reach the last index at any point
        if (maxReach >= n - 1) return true;

        // Update the farthest index we can reach
        maxReach = max(maxReach, i + nums[i]);

        // If we can't move forward
        if (i == maxReach && i < n - 1) return false;
    }

    return true;
}

Bit Manipulation

Note

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

int singleNumber(vector<int>& nums) {
    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 (int num : 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.

void backtrack(vector<int>& nums, int start, vector<int>& curr, vector<vector<int>>& result) {
    // Add current subset to result
    result.push_back(curr);

    // Try adding each remaining number
    for (int i = start; i < nums.size(); i++) {
        // Include nums[i]
        curr.push_back(nums[i]);

        // Recur with next position
        backtrack(nums, i + 1, curr, result);

        // Backtrack by removing nums[i]
        curr.pop_back();
    }
}

Merge Sort

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}