Time vs Space Complexity — Middle Level¶

public class PrefixSum {
    private int[] prefix;

    public PrefixSum(int[] arr) {
        prefix = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
    }

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        PrefixSum ps = new PrefixSum(arr);
        System.out.println("Sum [2..5]: " + ps.rangeSum(2, 5)); // 18
        System.out.println("Sum [0..9]: " + ps.rangeSum(0, 9)); // 55
    }
}

public static int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

public static int maxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

import java.util.*;

public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>(Set.of(start));
    Queue<Integer> queue = new LinkedList<>(List.of(start));
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (visited.add(neighbor)) {
                queue.add(neighbor);
            }
        }
    }
    return order; // Space: O(V) for visited + queue
}

import java.util.*;

public static List<Integer> dfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    List<Integer> order = new ArrayList<>();
    dfsHelper(graph, start, visited, order);
    return order;
}

private static void dfsHelper(Map<Integer, List<Integer>> graph, int node,
                               Set<Integer> visited, List<Integer> order) {
    visited.add(node);
    order.add(node);
    for (int neighbor : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) {
            dfsHelper(graph, neighbor, visited, order);
        }
    }
}

import java.util.HashMap;

public class Fibonacci {
    // O(2^n) time, O(n) space
    public static int fibNaive(int n) {
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // O(n) time, O(n) space
    static HashMap<Integer, Integer> memo = new HashMap<>();
    public static int fibMemo(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, result);
        return result;
    }

    // O(n) time, O(1) space
    public static int fibOptimal(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

import java.util.HashSet;

public class Benchmark {
    public static void main(String[] args) {
        int[] sizes = {100, 1000, 10000, 100000};
        for (int n : sizes) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = i;

            long start = System.nanoTime();
            hasDupBrute(arr);
            double brute = (System.nanoTime() - start) / 1_000_000.0;

            start = System.nanoTime();
            hasDupHash(arr);
            double hash = (System.nanoTime() - start) / 1_000_000.0;

            System.out.printf("n=%6d | Brute: %8.3f ms | Hash: %8.3f ms | Speedup: %.1fx%n",
                n, brute, hash, brute / hash);
        }
    }

    static boolean hasDupBrute(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            for (int j = i + 1; j < arr.length; j++)
                if (arr[i] == arr[j]) return true;
        return false;
    }

    static boolean hasDupHash(int[] arr) {
        HashSet<Integer> seen = new HashSet<>(arr.length);
        for (int v : arr) {
            if (!seen.add(v)) return true;
        }
        return false;
    }
}

public static void benchmarkMemory(int n) {
    Runtime rt = Runtime.getRuntime();
    rt.gc();
    long before = rt.totalMemory() - rt.freeMemory();
    int[] data = new int[n];
    long after = rt.totalMemory() - rt.freeMemory();
    System.out.printf("n=%d: allocated ~%d KB%n", n, (after - before) / 1024);
}