Space, Trade-offs and Integer Sizes

Memory counts too

Space complexity is how much extra memory your code needs as the input grows.

Two ways to solve one problem

Problem: does a list contain the same number twice?

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

bool hasDuplicateSlow(const vector<int>& v) {      // O(n^2) time, O(1) space
    for (size_t i = 0; i < v.size(); i++)
        for (size_t j = i + 1; j < v.size(); j++)
            if (v[i] == v[j]) return true;
    return false;
}

bool hasDuplicateFast(const vector<int>& v) {      // O(n) time, O(n) space
    unordered_set<int> seen;
    for (int x : v) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

int main() {
    vector<int> data = {5, 1, 9, 3, 9, 2};
    cout << hasDuplicateSlow(data) << " " << hasDuplicateFast(data) << endl;
    return 0;
}

Output

1 1

The fast version spends some memory to save a lot of time – a trade-off you'll see again and again.

Tip: const vector<int>& passes the vector by reference, so it isn't copied: O(1) instead of O(n). Use it whenever a function only reads a big container.

Watch out for overflow

An int holds up to about 2.1 billion. Bigger results silently wrap around to nonsense. Use long long (up to about 9 × 10¹⁸) for big sums and products:

#include <iostream>
using namespace std;

int main() {
    int n = 100000;
    long long pairsBig = 1LL * n * (n - 1) / 2;   // multiply as long long
    cout << "pairs: " << pairsBig << endl;
    cout << "int max: " << 2147483647 << endl;
    return 0;
}

Output

pairs: 4999950000
int max: 2147483647

Common mistake: n * (n - 1) with two ints overflows before it's stored in a long long. Write 1LL * n * (n - 1) so the multiplication itself happens in long long.