Python – Matrix data structure


A simple 2 dimensional array allows swapping rows (or columns) in a matrix in O(1) time. Is there an efficient data structure that would allow swapping both rows and columns of a matrix in O(1) time?

Best Solution

You have to store your matrix either as a list of rows or list of columns. Which gives either swapping of rows or swapping of columns in O(1).

However, you can add another layer on top of it to handle column order so that you can reorder columns in O(1).

So for every access you need to do:

x = data[row][colorder[col]] 

Swap rows as:

data[row1], data[row2] = data[row2], data[row1]

And swap columns as:

colorder[col1], colorder[col2] = colorder[c2], colorder[c1]