Write code to convert a matrix in a specific way without using extra space.
Input:
1 2 3
4 5 6
7 8 9Output:
1 6 7
2 5 8
3 4 9Explanation: At first look, the problem seems similar to finding the transpose of the matrix. But if you look carefully, you will notice that every even column in the output matrix has elements of the corresponding rows in the input matrix in the opposite order.
Approach: The problem can be easily converted to transpose of the matrix by doing some modification to the input matrix. If we invert every even row present in the input matrix, we can use the solution given here to convert the matrix in the desired order, and that too without using any auxiliary memory.
Below is the implementation of the idea.
C++
// C++ Program for convert matrix in specific order
// using in-place matrix transpose
#include <bits/stdc++.h>
#define HASH_SIZE 128
using namespace std;
// Non-square matrix transpose of matrix of size r x c
// and base address A
void transformMatrix(int* A, int r, int c)
{
// Invert even rows
for (int i = 1; i < r; i = i + 2)
for (int j1 = 0, j2 = c - 1; j1 < j2; j1++, j2--)
swap(*(A + i * c + j1), *(A + i * c + j2));
// Rest of the code is from below post
// http://tinyurl.com/j79j445
int size = r * c - 1;
int t; // holds element to be replaced, eventually
// becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
int i = 1; // Note that A[0] and A[size-1] won't move
while (i < size) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix 1
// i_new = (i*r)%(N-1)
next = (i * r) % size;
swap(A[next], t);
b[i] = 1;
i = next;
} while (i != cycleBegin);
// Get Next Move (what about querying
// random location?)
for (i = 1; i < size && b[i]; i++)
;
}
}
// A utility function to print a 2D array of size
// nr x nc and base address A
void Print2DArray(int* A, int nr, int nc)
{
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
cout << setw(4) << *(A + r * nc + c);
}
cout << endl;
}
cout << endl;
}
// Driver program to test above function
int main()
{
int A[][4] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
int r = 3, c = 4;
cout << "Given Matrix:" << endl;
Print2DArray((int*)A, r, c);
transformMatrix((int*)A, r, c);
cout << "Transformed Matrix:" << endl;
Print2DArray((int*)A, c, r);
return 0;
}
C
// Program for convert matrix in specific order
// using in-place matrix transpose
#include <bits/stdc++.h>
#define HASH_SIZE 128
using namespace std;
// Non-square matrix transpose of matrix of size r x c
// and base address A
void transformMatrix(int* A, int r, int c)
{
// Invert even rows
for (int i = 1; i < r; i = i + 2)
for (int j1 = 0, j2 = c - 1; j1 < j2; j1++, j2--)
swap(*(A + i * c + j1), *(A + i * c + j2));
// Rest of the code is from below post
// http://tinyurl.com/j79j445
int size = r * c - 1;
int t; // holds element to be replaced, eventually
// becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
int i = 1; // Note that A[0] and A[size-1] won't move
while (i < size) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix 1
// i_new = (i*r)%(N-1)
next = (i * r) % size;
swap(A[next], t);
b[i] = 1;
i = next;
} while (i != cycleBegin);
// Get Next Move (what about querying
// random location?)
for (i = 1; i < size && b[i]; i++)
;
}
}
// A utility function to print a 2D array of size
// nr x nc and base address A
void Print2DArray(int* A, int nr, int nc)
{
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++)
printf("%4d", *(A + r * nc + c));
printf("\n");
}
printf("\n");
}
// Driver program to test above function
int main(void)
{
int A[][4] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
int r = 3, c = 4;
cout << "Given Matrix:\n";
Print2DArray((int*)A, r, c);
transformMatrix((int*)A, r, c);
cout << "Transformed Matrix:\n";
Print2DArray((int*)A, c, r);
return 0;
}
Java
// Java Program for convert matrix in specific order
// using in-place matrix transpose
import java.util.*;
class gfg2 {
// Non-square matrix transpose of matrix of size r x c
// and base address A
static void transformMatrix(int[] A, int r, int c)
{
// Invert even rows
for (int i1 = 1; i1 < r; i1 = i1 + 2) {
for (int j1 = 0, j2 = c - 1; j1 < j2;
j1++, j2--) {
var temp = A[i1 * c + j2];
A[i1 * c + j2] = A[i1 * c + j1];
A[i1 * c + j1] = temp;
}
}
// Rest of the code is from below post
// http://tinyurl.com/j79j445
int size = r * c - 1;
int t; // holds element to be replaced, eventually
// becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int b = 1; // hash to mark moved elements
b |= (1 << size);
int i
= 1; // Note that A[0] and A[size-1] won't move
while (i < size) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix 1
// i_new = (i*r)%(N-1)
next = (i * r) % size;
var temp = t;
t = A[next];
A[next] = temp;
b |= (1 << i);
i = next;
} while (i != cycleBegin);
// Get Next Move (what about querying
// random location?)
for (i = 1; i < size && ((b & (1 << i)) != 0);
i++)
;
}
}
// A utility function to pra 2D array of size
// nr x nc and base address A
static void Print2DArray(int[] A, int nr, int nc)
{
for (var r = 0; r < nr; r++) {
for (var c = 0; c < nc; c++) {
System.out.print(
String.format("%1$" + 4 + "s",
(A[r * nc + c] + " ")));
; //.replace(' ', '0');
}
System.out.println();
}
System.out.println();
}
// Driver program to test above function
public static void main(String[] args)
{
int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
int r = 3, c = 4;
System.out.println("Given Matrix:");
Print2DArray(A, r, c);
transformMatrix(A, r, c);
System.out.println("Transformed Matrix:");
Print2DArray(A, c, r);
}
}
// This code is contributed by karandeep1234
Python3
# Python3 Program for convert matrix in specific order
# using in-place matrix transpose
# Non-square matrix transpose of matrix of size r x c
# and base address A
def transformMatrix(A, r, c):
# Invert even rows
for i in range(1, r, 2):
j1 = 0
j2 = c - 1
while j1 < j2:
temp = A[i*c + j2]
A[i*c + j2] = A[i*c + j1]
A[i*c + j1] = temp
j1 += 1
j2 -= 1
# Rest of the code is from below post
# http:#tinyurl.com/j79j445
size = r*c - 1
b = 1 # hash to mark moved elements
b |= (1 << size)
i = 1 # Note that A[0] and A[size-1] won't move
while (i < size):
cycleBegin = i
t = A[i]
while True:
# Input matrix [r x c]
# Output matrix 1
# i_new = (i*r)%(N-1)
next1 = (i*r) % size
temp = t
t = A[next1]
A[next1] = temp
b |= (1 << i)
i = next1
if i != cycleBegin:
break
# Get next Move (what about querying
# random location?)
i = 1
while i < size and (b & (1 << i)):
i += 1
# A utility function to pra 2D array of size
# nr x nc and base address A
def Print2DArray(A, nr, nc):
for r in range(nr):
for c in range(nc):
print(str(A[r * nc + c]).rjust(4, ' '), end="")
print()
print()
# Driver program to test above function
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
r = 3
c = 4
print("Given Matrix:")
Print2DArray(A, r, c)
transformMatrix(A, r, c)
print("Transformed Matrix:")
Print2DArray(A, c, r)
# This code is contributed by phasing17.
C#
// C# Program for convert matrix in specific order
// using in-place matrix transpose
using System;
using System.Collections.Generic;
class GFG {
// Non-square matrix transpose of matrix of size r x c
// and base address A
static void transformMatrix(int[] A, int r, int c)
{
// Invert even rows
for (int i1 = 1; i1 < r; i1 = i1 + 2) {
for (int j1 = 0, j2 = c - 1; j1 < j2;
j1++, j2--) {
var temp = A[i1 * c + j2];
A[i1 * c + j2] = A[i1 * c + j1];
A[i1 * c + j1] = temp;
}
}
// Rest of the code is from below post
// http://tinyurl.com/j79j445
int size = r * c - 1;
int t; // holds element to be replaced, eventually
// becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int b = 1; // hash to mark moved elements
b |= (1 << size);
int i
= 1; // Note that A[0] and A[size-1] won't move
while (i < size) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix 1
// i_new = (i*r)%(N-1)
next = (i * r) % size;
var temp = t;
t = A[next];
A[next] = temp;
b |= (1 << i);
i = next;
} while (i != cycleBegin);
// Get Next Move (what about querying
// random location?)
for (i = 1; i < size && ((b & (1 << i)) != 0);
i++)
;
}
}
// A utility function to pra 2D array of size
// nr x nc and base address A
static void Print2DArray(int[] A, int nr, int nc)
{
for (var r = 0; r < nr; r++) {
for (var c = 0; c < nc; c++) {
Console.Write(
Convert.ToString(A[r * nc + c])
.PadLeft(4));
}
Console.WriteLine();
}
Console.WriteLine();
}
// Driver program to test above function
public static void Main(string[] args)
{
int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
int r = 3, c = 4;
Console.WriteLine("Given Matrix:");
Print2DArray(A, r, c);
transformMatrix(A, r, c);
Console.WriteLine("Transformed Matrix:");
Print2DArray(A, c, r);
}
}
// This code is contributed by phasing17.
Javascript
// JS Program for convert matrix in specific order
// using in-place matrix transpose
// Non-square matrix transpose of matrix of size r x c
// and base address A
function transformMatrix(A, r, c)
{
// Invert even rows
for (let i = 1; i < r; i = i + 2)
{
for (var j1 = 0, j2 = c - 1; j1 < j2; j1++, j2--)
{
let temp = A[i*c + j2]
A[i*c + j2] = A[i*c + j1]
A[i*c + j1] = temp
}
}
// Rest of the code is from below post
// http://tinyurl.com/j79j445
let size = r*c - 1;
let t; // holds element to be replaced, eventually
// becomes next element to move
let next; // location of 't' to be moved
let cycleBegin; // holds start of cycle
let b = 1; // hash to mark moved elements
b |= (1 << size)
let i = 1; // Note that A[0] and A[size-1] won't move
while (i < size)
{
cycleBegin = i;
t = A[i];
do
{
// Input matrix [r x c]
// Output matrix 1
// i_new = (i*r)%(N-1)
next = (i*r)%size;
let temp = t;
t = A[next]
A[next] = temp
b |= (1 << i);
i = next;
} while (i != cycleBegin);
// Get Next Move (what about querying
// random location?)
for (i = 1; i < size && (b & (1 << i)); i++)
;
}
}
// A utility function to pra 2D array of size
// nr x nc and base address A
function Print2DArray(A, nr, nc)
{
for (var r = 0; r < nr; r++)
{
for (var c = 0; c < nc; c++)
{
process.stdout.write(String(A[r * nc + c]).padStart(4))
}
console.log()
}
console.log()
}
// Driver program to test above function
let A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
let r = 3, c = 4;
console.log("Given Matrix:");
Print2DArray(A, r, c);
transformMatrix(A, r, c);
console.log("Transformed Matrix:");
Print2DArray(A, c, r);
// This code is contributed by phasing17.
Output
Given Matrix: 1 2 3 4 5 6 7 8 9 10 11 12 Transformed Matrix: 1 8 9 2 7 10 3 6 11 4 5 12
Time Complexity: O(r×c), where r is the number of rows, and c is the number of columns.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
