[Algorithm Tips and Tricks] Encoding Matrix Positions Into A Single Value

To watch the youtube video on this topic, please click here.

Introduction: Matrices

A matrix is a 2-dimensional array. To access an element of a matrix, you look at a row position and a column position. (Ex. matrix[i][j] )

Matrices are useful data structures, but representing elements with two distinct keys (i, j) makes it trickier for using certain algorithms together with matrices. Being able to represent a position in a matrix with one value would be useful for situations like:

• Being able to represent the entire matrix as a 1D array.
• Being able to create a hash map where the key is a position in the matrix. (Hashing a pair (i,j) into a unique value isn't easy.)

Being able to do these things is important in algorithm questions in interviews and competitions.

Encoding Matrix Positions

It's possible to encode a position (i,j) in a matrix into a single value. We can do this because we know the number of columns in the matrix, and can basically think of each cell in the matrix as a number, incrementing while going left to right, continuing for each row (like reading a book).

Encoding a position (i,J) into an encoded value h can be done by multiplying i by the number of columns and adding j.
h = i * num_cols + j

Decoding an encoded value can be done by dividing/modulusing the value h by the number of columns.
i = h / num_cols
​j = h % num_cols

Encoding a position in a matrix (and decoding the encoded value).

We can write some code to test this out.

Bookmark this page to keep this trick available whenever you need it.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake