Matrix Problems
Reverse / Reflect a matrix
vector<vector<int>> matrix = { {1, 2, 3},
{4, 5, 6},
{7, 8, 9} };
for (int row = 0; row < matrix.size(); row++)
{
for (int col = 0, colLast = matrix.size() - 1; col < matrix.size() / 2; col++, colLast--)
{
// ROW remains same
swap(matrix[row][col], matrix[row][colLast]); /* COL from first and COL from last are swapped */
/* here col from first is 'col' & col from last is 'colLast' */
}
}
/* Output: reversed matrix is
3 2 1
6 5 4
9 8 7
*/
Rotate a matrix
To do in order: ↴
- Marix to its Transpose
- Reverse/reflect the matrix [only after matrix is transposed]
vector<vector<int>> v = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
// 1️⃣ transpose ... swapping the main diagonal elements
for (int row = 0; row < v.size(); row++)
{
for (int col = row; col < v.size(); col++) /* "col = row " bcoz, so that the previous row's elements will not be swapped again */
{
swap(v[row][col], v[col][row]); /* [1,2] ⇔ [2,1] ... */
}
}
// 2️⃣ revese the matrix
for (int row = 0; row < v.size(); row++)
{
for (int col = 0, colLast = v.size() - 1; col < v.size() / 2; col++, colLast--) /* "col < v.size()/2", to stop after half of the row is reversed otherwise again the reversed elements will get back to original positions */
{
// ROW remains same
swap(v[row][col], v[row][colLast]); /* COL from first and COL from last are swapped */
/* here col from first is 'col' & col from last is 'colLast' */
}
}
/* Rotated matrix:
7 4 1
8 5 2
9 6 3
*/
if first reversed and then transpose the matrix will look like this:
3 6 9
2 5 8
1 4 7
If you're not too confident with matrices and linear algebra, get some more practice by also coding a method that transposes the matrix on the other diagonal, and another that reflects from top to bottom. You can test your functions by printing out the matrix before and after each operation. Finally, use your functions to find three more solutions to this problem. Each solution uses two matrix operations.
Direction Matrix .. use to solve matrix problems
caution
TO DO
references:
sort a matrix / 2D vector
Matrix can be sorted by adding an extra parameter Comparison functionwhich is a user-defined explicit function in the sort():
caution
make the compareFunction function as
static, assort()only takes static function pointer as an argument
sort(..begin(), ..end(), comparisonFunction);
using (compareFunction) for sorting in Descending order of column[0]
static bool compareFunction(vector<int> v1, vector<int> v2)
{
return v1[0] > v2[0];
}
main()
{
vector<vector<int>> ans = {{1, 2}, {2, 3}, {99, 100}};
sort(ans.begin(), ans.end(), compareFunction);
// ...........
}
/* Output:
99 100
2 3
1 2
*/
return v1[0] > v2[0];... Descending orderreturn v1[0] < v2[0];... Ascending order
the matrix can be sorted on basis of a particular column as conditions like: 1st column in Ascending order, 1st column in Descending order, 3rd column in Descending order, and so on.
Spiral Matrix
rFirst, rLast and others as condition in tp while loop
vector<int> spiralOrder(vector<vector<int>> &v)
{
vector<int> sol;
int rFirst = 0, rLast = v.size() - 1, cFirst = 0, cLast = v[0].size() - 1;
int r = rFirst, c = cFirst;
int count = v.size() * v[0].size();
while (rFirst <= rLast && cFirst <= cLast)
{
// right
if (r == rFirst)
{
while (c <= cLast)
{
sol.emplace_back(v[r][c]);
++c;
--count;
if (count <= 0)
{
return sol;
}
}
++rFirst, c = cLast;
}
r = rFirst;
// down
if (c == cLast)
{
while (r <= rLast)
{
sol.emplace_back(v[r][c]);
++r;
--count;
if (count <= 0)
{
return sol;
}
}
--cLast, r = rLast;
}
c = cLast;
// left
if (r == rLast)
{
while (c >= cFirst)
{
sol.emplace_back(v[r][c]);
--c;
--count;
if (count <= 0)
{
return sol;
}
}
--rLast, c = cFirst;
}
r = rLast;
// up
if (c == cFirst)
{
while (r >= rFirst)
{
sol.emplace_back(v[r][c]);
--r;
--count;
if (count <= 0)
{
return sol;
}
}
++cFirst, r = rFirst;
}
c = cFirst;
}
return sol;
}
count as condition in tp while loop
vector<int> spiralOrder(vector<vector<int>> &v)
{
vector<int> sol;
int rFirst = 0, rLast = v.size() - 1, cFirst = 0, cLast = v[0].size() - 1;
int r = rFirst, c = cFirst;
int count = v.size() * v[0].size();
while (rFirst <= rLast && cFirst <= cLast)
{
// right
if (r == rFirst)
{
while (c <= cLast)
{
sol.emplace_back(v[r][c]);
++c;
--count;
if (count <= 0)
{
return sol;
}
}
++rFirst, c = cLast;
}
r = rFirst;
// down
if (c == cLast)
{
while (r <= rLast)
{
sol.emplace_back(v[r][c]);
++r;
--count;
if (count <= 0)
{
return sol;
}
}
--cLast, r = rLast;
}
c = cLast;
// left
if (r == rLast)
{
while (c >= cFirst)
{
sol.emplace_back(v[r][c]);
--c;
--count;
if (count <= 0)
{
return sol;
}
}
--rLast, c = cFirst;
}
r = rLast;
// up
if (c == cFirst)
{
while (r >= rFirst)
{
sol.emplace_back(v[r][c]);
--r;
--count;
if (count <= 0)
{
return sol;
}
}
++cFirst, r = rFirst;
}
c = cFirst;
}
return sol;
}