Week 1: C++ & Complexity Foundations

1. C++ Essentials for DSA

You don't need every corner of C++ for this course — you need the handful of features that show up in nearly every solution: references, pass-by-reference, and reading a function signature fluently.

References & pass-by-reference

A reference is an alias for an existing variable — no copy is made. Passing a large structure like a vector by reference avoids copying it on every call, which matters constantly once you're passing arrays into recursive functions:

#include <vector>
using namespace std;

// Pass by value: nums is a full COPY -- changes here don't affect the caller's vector
void doubleAllCopy(vector<int> nums) {
    for (int& n : nums) n *= 2;
}

// Pass by reference: nums IS the caller's vector -- no copy, changes persist
void doubleAllRef(vector<int>& nums) {
    for (int& n : nums) n *= 2;
}

// Pass by const reference: no copy, AND the compiler forbids modifying nums
int sumAll(const vector<int>& nums) {
    int total = 0;
    for (int n : nums) total += n;
    return total;
}

Structs for grouping data

A lightweight struct is how you'll bundle related values together — you'll use exactly this pattern for tree and linked-list nodes starting Week 6:

struct Point {
    int x;
    int y;
};

Point p = {3, 4};
int distSquared = p.x * p.x + p.y * p.y;

2. Time & Space Complexity

Big-O notation describes how an algorithm's runtime (or memory use) grows as input size n grows — not the exact number of operations, but the growth trend once n gets large. It's the language every interviewer will use to ask "can you do better?"

// O(1) -- constant time, independent of n
int firstElement(const vector<int>& nums) {
    return nums[0];
}

// O(n) -- one pass over the input
int sum(const vector<int>& nums) {
    int total = 0;
    for (int x : nums) total += x;   // n iterations
    return total;
}

// O(n^2) -- nested loops over the same input
bool hasDuplicate(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++)
        for (int j = i + 1; j < nums.size(); j++)   // n iterations, n times
            if (nums[i] == nums[j]) return true;
    return false;
}

// O(log n) -- halves the search space each step
int binarySearch(const vector<int>& sorted, int target) {
    int lo = 0, hi = sorted.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] == target) return mid;
        else if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

To derive complexity: count how the number of operations scales with n, then drop constants and lower-order terms. 3n + 100 is O(n); n² + 500n is O(n²) — the n² term dominates once n is large enough, regardless of the constant in front of it.

Space complexity follows the same idea, but for memory: a function using a fixed number of variables is O(1) space; one that allocates a new array of size n is O(n) space — and that includes the memory used by recursion's call stack, which matters once recursive solutions show up starting Week 8.

3. STL Essentials: vector, pair & <algorithm>

The C++ Standard Template Library is what makes C++ competitive for interviews despite its low-level reputation — vector and the algorithm header cover most of what you'd otherwise hand-write in a lower-level language.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9};

    nums.push_back(3);              // append -- amortized O(1)
    nums.pop_back();                // remove last element
    int n = nums.size();            // O(1)

    sort(nums.begin(), nums.end()); // O(n log n), ascending
    sort(nums.begin(), nums.end(), greater<int>()); // descending

    auto it = find(nums.begin(), nums.end(), 8);  // O(n) linear search
    bool found = (it != nums.end());

    int mx = *max_element(nums.begin(), nums.end());
    int mn = *min_element(nums.begin(), nums.end());

    pair<int, int> p = {1, 2};
    cout << p.first << ", " << p.second << "\n";
}

pair<int, int> shows up constantly for bundling two related values — a coordinate, an (index, value) tuple, or an edge in a graph starting Week 12. Getting fluent with sort, find, and the *_element family now means you won't hand-roll them later when a harder problem needs your full attention elsewhere.

4. Setting Up Your Workflow

You need a C++17-capable compiler and a fast way to compile and run one file at a time — no build system required for this course:

g++ --version
# g++ (...) 11.x or later

g++ -std=c++17 -O2 -o solution solution.cpp
./solution

-std=c++17 enables the C++17 features this course uses (structured bindings, if with an initializer); -O2 turns on optimizations, which matters when you're timing a solution against a large test case. Most learners in this course also keep an account on an online judge (LeetCode or GeeksforGeeks) open alongside their editor to submit and time solutions against real constraints.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.