Matrix-Compression-Decompression-Problem

This repository contains the solution code for Matrix Compression Decompression problem.

Problem Statement:

1. Given a 100x100 matrix.
2. For compression, reduce NxN to (N-c)x(N-c)
   e.g. if input N=100, c=50, reduce matrix to 50x50.
3. For decompression, expand NxN to (N+d)x(N+d)
   e.g. if input N=50, d=20, expand matrix to 70x70.

Approach:

1. Generate a 100x100 random 'matrix' by using vector of vectors.
2. Make a reference matrix to store the values matrix(i, j). Update this matrix whenever a new random matrix is generated.
3. For compression, if c=x, delete last x rows i.e. last x vectors in the vector 'matrix'. Then delete last x elements in each vector of 'matrix'.
4. For decompression, if d=x, pushback x elements in each vectors in 'matrix' fetching values from the reference matrix and also pushback x vectors in 'matrix'.
5. Always run a check to see if the matrix order goes out of bound.

Complexity:

1. Time complexity:
   a. for compression- O(n^2)
   b. for decompression- O(n^2)
2. Space complexity: n^2 auxiliary space