Approximate Range for numerical variables

In competitive programming, use:

• int for values up to around (10^9).
• long long for values up to around (10^18)

ASCII Values

• Uppercase letters (A - Z): 65 to 90
  • 'A' = 65
  • 'Z' = 90
• Lowercase letters (a - z): 97 to 122
  • 'a' = 97
  • 'z' = 122
• Note: The gap between the uppercase and lowercase ranges (ASCII 91 to 96) contains symbols like [, \, ], ^, _, and ```. The lowercase value of any letter is always exactly 32 greater than its uppercase counterpart (e.g., 'A' is 65, 'a' is 65 + 32 = 97).

#Note that the newline "\n" works faster than endl, because endl always causes a flush operation.
#8 bits = 1 byte
#Note that e is a scientific way to write 10 to the power something and it works in programming languages as well e.g.: 1e24 is (1 multiplied by 10 to the power 24)

Use the below functions to find the minimum and maximum elements in vectors
Note that it returns the pointer and we are dereferencing it to find the actual value
The min() and max() functions work directly on two values.
You cannot directly write min(v) or max(v).
Instead, use min_element() and max_element() from the <algorithm> library.

plain textCopy

    int mn = *min_element(v.begin(), v.end());
    int mx = *max_element(v.begin(), v.end());
//Both min_element() and max_element() take O(n) time, where n is the number of elements.

Time Complexity

Time Complexity measures how the runtime of an algorithm scales as the input size (N) grows. It does not measure absolute seconds, as that depends on hardware; instead, it counts the total number of fundamental operations executed.

Space Complexity

Space Complexity measures how the memory footprint of an algorithm scales with the input size. In problem-solving, this usually refers to auxiliary space—the temporary, extra memory your algorithm allocates (like hash maps, dynamic arrays, or the recursion call stack), excluding the memory needed to store the initial input.

Big O Notation (O) is the mathematical standard used to express these complexities. It strictly defines the worst-case scenario (the upper bound).

When calculating Big O, you drop constants and lower-order terms. For example, if an algorithm takes O(2N^2 + 50N + 5), it simplifies to O(N^2). As N approaches infinity, the constants and the 50N become statistically irrelevant; the N^2 term is the bottleneck that dictates system failure.

The Essential Big O Hierarchy (Fastest to Slowest):

• O(1) Constant: Execution time or space remains exactly the same regardless of input size.
  Examples: Accessing an array by index, math formulas, pushing to a stack.
• O(log N) Logarithmic: The algorithm repeatedly halves the search space. It is incredibly efficient, taking very few extra steps even if the dataset expands by millions.
  Examples: Binary Search, finding an item in a balanced Binary Search Tree.
• O(N) Linear: Execution scales at a 1:1 ratio with the input.
  Examples: Iterating through a standard array with a single for loop, Two Pointers.
• O(N log N) Linearithmic: The baseline for optimal comparison-based algorithms.
  Examples: Standard library sorting (like C++ std::sort or Java Arrays.sort()), Merge Sort.
• O(N^2) Quadratic: Every element interacts with every other element. Usually causes a "Time Limit Exceeded" (TLE) error on LeetCode for inputs larger than 10^4.
  Examples: Double nested loops, Bubble Sort, Selection Sort.
• O(2^N) Exponential: The runtime doubles with every single addition to the input.
  Examples: Unoptimized branching recursion (like naive Fibonacci), generating all subsets of a set.

Range based for loops in C++

Range-based loops provide an easier way to traverse containers like vectors, arrays, maps, etc., without using indices or iterators.

1. Without Reference (&)

for (int value : v) {
    cout << value << " ";
}

• A copy of each element is stored in value.
• Any modification affects only the copy, not the original vector.

for (int value : v) {
    value++;  // Original vector remains unchanged
}

2. With Reference (&)

for (int &value : v) {
    value++;
}

• value becomes a reference to the actual element.
• Changes directly affect the original vector.
• No unnecessary copying takes place.

3. With Constant Reference

for (const int &value : v) {
    cout << value << " ";
}

• Avoids copying.
• Does not allow modification of original elements.

Quick comparison:

Traversing maps in C++

A map stores elements as key-value pairs.

• first → Key
• second → Value

1. Range-Based Loop

for (auto &itr : mp) {
    cout << itr.first << " " << itr.second;
}

• auto automatically determines the data type.
• & avoids copying and allows modification of values.
• itr.first accesses the key.
• itr.second accesses the value.

Example:

for (auto &itr : mp) {
    itr.second++;  // Modifies original map
}

Note: Map keys are immutable, but values can be modified.

2. Accessing Pairs Using Iterators

When an iterator points to a pair, we can access its members using:

itr->first   // Key
itr->second  // Value

This is equivalent to:

(*itr).first
(*itr).second

Example:

for (auto itr = mp.begin(); itr != mp.end(); itr++) {
    cout << itr->first << " " << itr->second;
}

Standard Template Library

Here's a table that might come in very handy to understand the syntax and complexities of common functions that are associated with different data structures and might just be what you need:

Sorting Algorithms

1. Bubble Sort

Compares adjacent elements and swaps them if they are in the wrong order. Repeats until sorted. In each iteration the max element bubbles to the end of the array.

• Easy to understand, but slow for large arrays.
• Worst time: O(n²)

void bubbleSort(vector<int>& a) {
    int n = a.size();

    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;

        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }

        if (!swapped) break;
    }
}

2. Selection Sort

Finds the smallest element and puts it at the beginning. Repeats for the remaining elements.

• Uses fewer swaps.
• Time: O(n²)

void selectionSort(vector<int>& a) {
    int n = a.size();

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex])
                minIndex = j;
        }

        swap(a[i], a[minIndex]);
    }
}

3. Insertion Sort

Takes one element at a time and inserts it into the correct position in the already-sorted part.

• Good for small or nearly sorted arrays.
• Worst time: O(n²)

void insertionSort(vector<int>& a) {
    int n = a.size();

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }
}

4. Merge Sort

Divides the array into smaller parts, sorts them, and merges them back together.

• Reliable and efficient.
• Time: O(n log n)

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> temp;
    int i = l, j = m + 1;

    while (i <= m && j <= r) {
        if (a[i] <= a[j])
            temp.push_back(a[i++]);
        else
            temp.push_back(a[j++]);
    }

    while (i <= m) temp.push_back(a[i++]);
    while (j <= r) temp.push_back(a[j++]);

    for (int k = 0; k < temp.size(); k++)
        a[l + k] = temp[k];
}

void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;

    int m = l + (r - l) / 2;

    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

// Call: mergeSort(a, 0, a.size() - 1);

5.Quick Sort

Picks a pivot, places smaller elements on one side and larger elements on the other, then sorts both sides.

• Usually very fast in practice.
• Worst time: O(n²)

int partition(vector<int>& a, int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }

    swap(a[i + 1], a[high]);
    return i + 1;
}

void quickSort(vector<int>& a, int low, int high) {
    if (low >= high) return;

    int p = partition(a, low, high);

    quickSort(a, low, p - 1);
    quickSort(a, p + 1, high);
}

// Call: quickSort(a, 0, a.size() - 1);

Bitwise AND (&)

Bitwise AND (&) in C++ compares the corresponding bits of two integers and returns 1 only when both bits are 1; otherwise, it returns 0. It is commonly used in DSA for checking bits, clearing bits, identifying common set bits, and working with bit masks.

Bitwise OR (|)

Bitwise OR (|) in C++ compares the corresponding bits of two integers and returns 1 when at least one bit is 1; it returns 0 only when both bits are 0. It is commonly used in DSA to set bits, combine bit masks, and enable specific flags.

XOR(^) operator

XOR (^) in C++ is a bitwise operator that compares corresponding bits of two integers and returns 1 if the bits are different and 0 if they are the same. It is commonly used in bit manipulation and DSA problems because of its cancellation properties, which help find unique or missing numbers efficiently.