Powered by
/src$ make
  • Home
  • About
  • Directory
  • Contact
  • Home
  • About
  • Directory
  • Contact

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

3/5/2020

 
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
Picture
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

Comments are closed.

    Author

    Hi, I'm srcmake. I play video games and develop software. 

    Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
    Metamask tip button
    License: All code and instructions are provided under the MIT License.

    Discord

    Chat with me.


    Youtube

    Watch my videos.


    Twitter

    Get the latest news.


    Twitch

    See the me code live.


    Github

    My latest projects.

Powered by Create your own unique website with customizable templates.