Space Complexity

public class SpaceComplexity {

    // O(1) auxiliary space — in-place, only a few variables
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];   // only 1 extra variable
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        // Space: O(1) auxiliary — just 'temp', 'i', 'j'
    }

    // O(n) auxiliary space — creates a new array
    static int[] copyArray(int[] arr) {
        int[] copy = new int[arr.length];  // O(n) extra space
        for (int i = 0; i < arr.length; i++) copy[i] = arr[i];
        return copy;
    }

    // O(log n) space — recursive binary search (call stack depth)
    static int binarySearchRec(int[] arr, int lo, int hi, int target) {
        if (lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) return binarySearchRec(arr, mid + 1, hi, target);
        return binarySearchRec(arr, lo, mid - 1, target);
        // Recursion depth = log₂(n) → O(log n) stack space
    }

    // O(n) space — recursive factorial (call stack depth = n)
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
        // n recursive calls on stack → O(n) space
    }

    // O(n) space — DP array
    static long fibDP(int n) {
        long[] dp = new long[n + 1];  // O(n) space
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }

    // O(1) space — optimized Fibonacci (only keep last 2 values)
    static long fibOptimized(int n) {
        if (n <= 1) return n;
        long prev2 = 0, prev1 = 1;  // O(1) space
        for (int i = 2; i <= n; i++) {
            long curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}