Matrix

Classical Questions and Solutions for Matrix

1. Matrix Manipulation

   1. Example questions:

      1. 311_Sparse Matrix Multiplication

2. Search in Matrix

   1. Start from top-right, eliminate one row or one column a time.

   2. Example questions:

      1. 240_Search a 2D Matrix II

3. Traverse in Matrix

   1. There are various traverse types. But we can always learn from examples.

   2. Need to take care of the direction, and corner cases on each border.

   3. Sometimes we could use sorting.

   4. Useful facts: for elements on the same row, their row index are the same; for elements on the same column, their column index are the same; for elements on the same diagonal, the sum of row index and column index are the same.

   5. Example questions:

      1. 54_Spiral Matrix

      2. 498_Diagonal Traverse

Notes:

1. Construct 2D array/matrix

   1. When construct 2*3 matrix of zeros, don't write [[0] * 3 ] * 2, the correct way is [[0] * 3 for _ in range(2)]. Although it look like that they return the same matrix. A big difference is the first code generate all rows referring to the first row. Thus when one row changes, every row changes. The second code doesn't have this reference problem.