Home › DSA › Foundations

Quadratic Space On

Quadratic Space Complexity describes algorithms where the memory usage grows proportionally to the square of the input size. This type of complexity is common in dynamic programming (DP) problems that require a 2D table to store intermediate results, especially when solving problems involving grids or pairs.

Key Characteristics

In an algorithm with space complexity:

Memory usage grows with the square of the input size.
This is typical in algorithms that use a 2D array or matrix to store information for each pair of elements or each cell in a grid.

Code Example: Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem is a classic DP problem where we use a 2D table to store the length of the longest common subsequence between prefixes of two strings.

java

class Solution {

  public int longest_common_subsequence(String X, String Y) {
    int m = X.length();
    int n = Y.length();

    // Create a 2D DP table with dimensions (m+1) x (n+1)
    int[][] dp = new int[m + 1][n + 1];

    // Fill the DP table
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }

    // The bottom-right cell of the table contains the length of the LCS
    return dp[m][n];
  }

  public static void main(String[] args) {
    String X = "AGGTAB";
    String Y = "GXTXAYB";

    Solution solution = new Solution();
    int lcsLength = solution.longest_common_subsequence(X, Y);

    System.out.println("Length of Longest Common Subsequence: " + lcsLength);
  }
}

Explanation:
- The dp table has dimensions (m+1) x (n+1), where m and n are the lengths of the two strings X and Y.
- Each cell dp[i][j] stores the length of the LCS of the prefixes X[0...i-1] and Y[0...j-1].
- This results in a quadratic space complexity of .

Examples of Space Operations

Dynamic Programming on Grids: Problems that involve 2D grids, like pathfinding in a matrix.
Pair-Based DP Problems: Problems like LCS or edit distance, where we track values for each combination of positions in two strings.
Graph Algorithms with Adjacency Matrices: Representing a graph with an adjacency matrix uses space for a graph with nodes.

🤖 Don't fully get this? Learn it with Claude

Stuck on Quadratic Space On? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Quadratic Space On** (DSA) and want to truly understand it. Explain Quadratic Space On from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Quadratic Space On** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Quadratic Space On** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Quadratic Space On** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Linear Space On Quiz (2) →