Mapping 1D Array to 2D Array¶
Consider a 1D array that represents a 2D array:
[ 00, 01, 02, 11, 12, 13 ] # Row-major order
0 1 2 3 4 5
This could represent the following 2D array:
[
[00, 01, 02],
[11, 12, 13]
]
Row-Major Order¶
To convert a 1D array index back to 2D array coordinates in row-major order, use these formulas:
\[
\text{row_index} = \left\lfloor\frac{\text{index}}{\text{number_of_cols}}\right\rfloor
\]
\[
\text{col_index} = \text{index} \bmod \text{number_of_cols}
\]
Explanation:
- Integer division (⌊index/cols⌋) gives the row number because each row contains
number_of_colselements - Remainder (modulo) gives the position within that row
For example, given index 4 with number_of_cols = 3:
- row_index = ⌊4/3⌋ = 1
- col_index = 4 mod 3 = 1
- Therefore, index 4 maps to position (1,1)
Column-Major Order¶
For a 1D array in column-major order:
[ 00, 11, 01, 12, 02, 13 ] # Column-major order
0 1 2 3 4 5
The formulas are:
\[
\text{row_index} = \text{index} \bmod \text{number_of_rows}
\]
\[
\text{col_index} = \left\lfloor\frac{\text{index}}{\text{number_of_rows}}\right\rfloor
\]
Explanation:
- Remainder (modulo) gives position within the current column
- Integer division gives which column we're in
For example, given index 3 with number_of_rows = 2:
- row_index = 3 mod 2 = 1
- col_index = ⌊3/2⌋ = 1
- Therefore, index 3 maps to position (1,1)
Practice¶
Search in a 2D Matrix
"""
Solution for : https://leetcode.com/problems/search-a-2d-matrix/description/
If you look at the examples, the data in the 2d matrix is sorted in row-major order.
You can use a 1D index to binary search (bisect left) over the range of the entire array.
The range of the 1D index will be :
lo =0 , hi = num_rows*num_cols
To get the value at any 1D index :
matrix[1d_index//num_cols][1d_index%num_cols]
"""
class Solution:
@staticmethod
def get_val_at_sn(sn: int, matrix : List[List[int]]) -> int :
"""Given a 1D index into 2D Matrix, Return the corresponding Value."""
num_rows,num_cols = len(matrix), len(matrix[0])
return matrix[sn//num_cols][sn%num_cols ]
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
"""
00 - 0 01 -1 02 -2
10 - 3 11 -4 12 -5
21 - 6 22 -7 23 -8
3 - 3
r = 1 , c = 0
r = sn // num_cols , c = sn % num_columns
"""
num_rows,num_cols = len(matrix), len(matrix[0])
lo,hi = 0 , num_rows*num_cols
while lo < hi :
mid = (lo + hi) // 2
val = self.get_val_at_sn(mid,matrix)
if val < target :
lo = mid + 1
else :
hi = mid
if lo == num_rows*num_cols :
return False
if self.get_val_at_sn(lo,matrix) == target :
return True
return False
Reshape Matrix
"""
Solution for: https://leetcode.com/problems/reshape-the-matrix/
Allocate the target array.
Use 1D indexing to read and write values from the source matrix to the target matrix.
"""
class Solution:
@staticmethod
def read_val(linear_index, matrix) :
num_cols = len(matrix[0])
return matrix[linear_index//num_cols][linear_index%num_cols]
@staticmethod
def write_val(linear_index, matrix,val) :
"""
write val at linear index into matrix
"""
num_cols = len(matrix[0])
matrix[linear_index//num_cols][linear_index%num_cols] = val
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
#Quote :"If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix."
if not len(mat)*len(mat[0]) == r*c :
return mat
# Allocate target Matrix
target = [ [0]*c for _ in range(r) ]
#read from source matrix and write into target matrix
for i in range(len(mat) * len(mat[0])) :
val = self.read_val(i,mat)
self.write_val(i,target,val)
return target