Space Time Trade-offs

Definition

---

Common Trade-off Patterns

---

Real-World Examples

---

Algorithm Examples

// Example 1: Two Sum - Classic trade-off
public class TwoSum {

    // O(n²) time, O(1) space
    public int[] twoSumBruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    // O(n) time, O(n) space - trade space for time
    public int[] twoSumHashMap(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

// Example 2: Fibonacci - Memoization
public class Fibonacci {

    // O(2^n) time, O(n) space (call stack)
    public int fibRecursive(int n) {
        if (n <= 1) return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }

    // O(n) time, O(n) space - memoization
    public int fibMemo(int n, int[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    // O(n) time, O(1) space - optimal
    public int fibIterative(int n) {
        if (n <= 1) return n;
        int prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

// Example 3: Prefix Sum - Preprocessing trade-off
public class PrefixSum {
    private int[] prefix;

    // O(n) preprocessing, O(n) space
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    // O(1) range sum query
    public int rangeSum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }

    // Without preprocessing: O(n) per query
    // With preprocessing: O(1) per query
}

---

Trade-off Matrix

---

Data Structure Trade-offs

---

Tips & Tricks

---