What is Space Complexity?

🧠 What is Space Complexity?

Space complexity is the amount of extra memory your algorithm uses relative to the input size.

It includes:

• Variables

• Data structures (arrays, maps, sets, etc.)

• Function call stack (for recursion)

🔸 Note: Input itself is not counted — only extra space your code uses.

---

🛠 How to Decide Space Complexity (Step by Step)

Let’s break it down:

✅ Step 1: Look at your variables

• Constants → O(1)

• Arrays, vectors, etc. → O(n) if you create one of size n

• 2D arrays → O(n²)

✅ Step 2: Check loops or recursion

• If recursion goes n levels deep → O(n) stack space

• Storing recursive results? Add that too.

✅ Step 3: Check data structures

• vector<int> v(n) → O(n)

• unordered_map<char, int> storing up to 26 keys → O(1)

• But if map size grows with input → O(n)

---

🔎 Example 1: Brute-force Max Avg Subarray

double findMaxAverage(vector<int>& nums, int k) {
    double maxAvg = INT_MIN;
    for (int i = 0; i <= nums.size() - k; i++) {
        double sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        maxAvg = max(maxAvg, sum / k);
    }
    return maxAvg;
}

✅ Space Analysis:

• maxAvg and sum are scalars → O(1)

• No extra array or recursion

• ➤ Space Complexity: O(1)

---

🔎 Example 2: Using HashMap

unordered_map<char, int> freq;
for (char c : s) {
    freq[c]++;
}

If input string s has all lowercase letters:

• Max 26 keys → still O(1)
  But if input allows Unicode / no size limit:

• Could grow with input size → O(n)

---

🔎 Example 3: Recursive Fibonacci

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

❌ Space: O(n) stack (recursive calls)

---

🧪 Rule of Thumb

Code Feature	Space Complexity
Constant variables	O(1)
Array of size n	O(n)
2D array of n x m	O(n * m)
Recursion to depth n	O(n) stack
Hash map storing n items	O(n)
Sliding window (sum only)	O(1)

---