DEV Community: Anmol Jindal

C++ Matrix Compression: Reduce Memory Usage by 90% with Smart 1D Storage

Anmol Jindal — Sun, 13 Jul 2025 16:02:42 +0000

Photo by HarrisonBroadbent on Unsplash

The majority of matrices in the real world contain more than just random numbers. They contain repeated values or big blocks of zeros. However, a lot of people store them as full 2D arrays, which wastes CPU cache and RAM and degrades performance, particularly when used on a large scale.

For example , even though only 100 integers are truly important, an int mat[100][100] allocates 10,000. This results in the waste of speed and memory.

The solution? Storing only the meaningful elements in a 1D array using smart indexing. This increases the speed of your code and compresses memory by up to 90%+.

Here is the complete working code → MatrixOptimizedADT GitHub Repo

Matrix Types & How to Compress Them

Here are common matrix types and the strategies to store them efficiently.

1. Diagonal Matrix

Structure: Non-zero elements exist only on the main diagonal (where row index i equals column index j).
Storage Size: n
Compression Idea: Since only n diagonal elements matter, just store those n elements in a 1D array.

2. Lower Triangular Matrix

Structure: Non-zero elements are on and below the main diagonal (where i >= j).
Storage Size: n(n+1)/2
Compression Idea: Store the elements row-by-row (row-major order).

3. Upper Triangular Matrix

Structure: Non-zero elements are on and above the main diagonal (where i <= j).
Storage Size: n(n+1)/2
Compression Idea: Store the elements column-by-column (column-major order).

4. Symmetric Matrix

Structure: The element at A[i][j] is equal to the element at A[j][i].
Storage Size: n(n+1)/2
Compression Idea: You only need to store either the lower or upper triangular part. The other half can be derived.

5. Tridiagonal Matrix

Structure: Non-zero elements are only on the main diagonal, the one above it, and the one below it.
Storage Size: 3n - 2
Compression Idea: Store these three diagonals as three separate sections within one array.

6. Toeplitz Matrix

Structure: Elements are constant along each descending diagonal (A[i][j] depends on i - j).
Storage Size: 2n - 1
Compression Idea: You only need to store the first row and the first column to reconstruct the entire matrix.

The Math Behind Compression: Why These Indexing Formulas Work

Let’s break down the logic behind the formulas that let you store only what matters in 1D arrays:

1. Diagonal Matrix

Only n elements matter , the diagonal entries where i == j. So store them in a 1D array of size n, and index with arr[i-1].

2. Lower Triangular Matrix

Non-zero elements lie where i >= j. The number of such elements is the sum of the first n natural numbers: n(n+1)/2.

Indexing formula:

// Lower Triangular Matrix indexing
int index = (i * (i - 1)) / 2 + (j - 1);

This counts how many elements are in all rows before i plus the position in the current row.

3. Upper Triangular Matrix

Here non-zero elements lie where i <= j. We store column-wise:

// Upper Triangular Matrix indexing
int index = (j * (j - 1)) / 2 + (i - 1);

Same logic but transposed.

4. Symmetric Matrix

Since A[i][j] =A[j][i] , we will only store the lower triangle (or upper). If i < j, swap indices to access the stored half:

// Symmetric Matrix indexing (store lower triangle only)
if (i < j) std::swap(i, j);
int index = (i * (i - 1)) / 2 + (j - 1);

5. Tridiagonal Matrix

Non-zero elements are on main diagonal, plus one above and one below. We can store three arrays concatenated in one:

Lower diagonal: indices 0 to n-2
Main diagonal: indices n-1 to 2n-2
Upper diagonal: indices 2n-1 to 3n-3

// Tridiagonal Matrix indexing
if (i == j)
    index = (n - 1) + (i - 1);
else if (i == j + 1)
    index = i - 2;
else if (i == j - 1)
    index = (2 * n - 1) + (i - 1);
else
    index = -1; // invalid

Indexing adjusts to which diagonal you’re accessing.

6. Toeplitz Matrix

Each descending diagonal has the same value, So store the first row and first column without duplicating the [1][1] element.

// Toeplitz Matrix indexing
int index = (i <= j) ? (j - i) : (n + i - j - 1);

Memory Efficiency : Navie vs Compressed

Matrix Type	Naive Storage	Compressed Storage	Memory Reduction
Diagonal	n^2	n	~99%
Lower/Upper Triangular	n^2	n(n+1)/2	~50%
Symmetric	n^2	n(n+1)/2	~50%
Tridiagonal	n^2	3n - 2	~97%
Toeplitz	n^2	2n - 1	~98%

C++ Implementation

Instead of showing you repeated code, here’s the full Diagonal class implementation and an example for Lower Triangular focusing on the indexing difference:

class Diagonal {
private:
    int n;
    int* arr;
public:
    Diagonal(int n) : n(n), arr(new int[n]()) {}
    void set(int i, int j, int val) {
        if (i == j) arr[i - 1] = val;
    }
    int get(int i, int j) {
        return (i == j) ? arr[i - 1] : 0;
    }
    void display() {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                std::cout << get(i, j) << (j == n ? "\n" : " ");
            }
        }
    }
    ~Diagonal() { delete[] arr; }
};

Lower Triangular indexing formula difference:

int index(int i, int j) {
    return (i * (i - 1)) / 2 + (j - 1);
}

Final Words

If your codebase still stores full 2D arrays for structured matrices, you’re wasting memory and CPU cycles unnecessarily. Matrix compression is a foundational skill for system design, competitive programming, and interviews.

Clone the MatrixOptimizedADT GitHub Repo, experiment with the code, and contribute new matrix types or features.

About the Author

Hey, I’m Anmol aka TimelessRecall

Follow me here:

Why Your Recursive Fibonacci Is a Time-Consuming Monster (And How DP Saves Your Day)

Anmol Jindal — Fri, 06 Jun 2025 09:26:22 +0000

In this blog, I’ll explain why naive recursion is a terrible idea for Fibonacci, how dynamic programming (DP) can fix it, and how you can write efficient Fibonacci code that’s easy to understand

What is Fibonacci?

Image by Gerd Altmann from Pixabay

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.

The Fibonacci sequence, denoted as fib(n), starts like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The nth Fibonacci number is the sum of (n-1)th and (n-2)th Fibonacci numbers. Simple, right?

The Naive Recursive Approach: Welcome to Exponential Hell

The first instinct of everyone is to write this beautiful but deadly code:

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

At first glance, this function looks simple and neat. But don’t be fooled , it ends up recalculating the same values so many times, it might as well be stuck in an infinite loop of inefficiency.

Dynamic Programming to the Rescue

Dynamic programming is basically caching the results of expensive function calls and reusing them when needed by using a concept called memoization.

Here’s how you can do it:

int fib_memo(int n, int memo[]) {
    if (n <= 1)
        return n;
    if (memo[n] != -1)
        return memo[n];
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

You just need to initialize the memo array with -1 and call fib_memo(n, memo). This cuts the time complexity down to O(n), which is a massive improvement.

Tabulation: The Bottom-Up Approach

If recursion isn’t your thing, try tabulation. It’s a bottom-up method that builds the solution from the ground up:

int fib_tab(int n) {
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

This method also runs in O(n) time and uses O(n) space.

Real-Life Analogy: Climbing Stairs

Picture yourself climbing a staircase where you can take either 1 or 2 steps at a time. The total number of distinct ways to reach the nth step corresponds exactly to the nth Fibonacci number.

Dynamic Programming (DP) comes in handy by remembering how many ways you’ve already counted for each step, saving your code from doing the same calculation over and over again.

Bonus Challenge: Space Optimization

Try implementing Fibonacci using just two variables and a loop, which brings space complexity down to O(1):

int fib_optimized(int n) {
    if (n <= 1)
        return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Conclusion

Dynamic programming is your secret weapon against inefficient recursive hell. Whether you choose memoization or tabulation, mastering DP will elevate your coding game and prepare you for tougher algorithmic challenges.

If you found this blog helpful, hit that clap button, share it with your friends, and follow me for more tips on DSA, and coding challenges.

Connect with me on LinkedIn and check out my repos on GitHub for code snippets and more.