Array
Array is one kind of linear list which data is store/access randomly. Another typical linear is Linked List which store/access data in a chained list. Array is foundation of almost all other data structure and algorithm.
From dimensional perspective, there are one-dimensional array, multi-dimensional array, and one special multi-dimensional array type in C# which is jagged array.
matrix is rectangular array of mathematical concept, ti could be represented by 2D array.
Initialize Array, fill array, get length of array dimension
int[] arr = new int[10];
int[] arr = new int[]{1,2,3}; //init with value
var len = arr.Length;
// two-dimensional array
int[,] arr = new int[2,3];
int[,] arr = new int[,] { {1,1,1}, {2,2,2}}; // init with value
var rows = arr.GetLength(0);
var cols = arr.GetLength(1);
var len = arr.Length;// rows * cols;
// multi-dimensional jagged array
int[][] arr = new int[2][];
int[][] arr = new int[][] {new[]{1,1}, new[]{2,2,2}};
int[][][] arr = new int[][] {new[]{Enumerable.Range(1, 10).ToArray()}, new[]{Enumerable.Range(1, 2).ToArray()}};
var rows = arr.Length;
int col0 = arr[0].Length // jagged array don't have fixed lens of columns
Traversal
1D Array Forward, Backward
var arr = Enumerable.Range(1, 10).ToArray();
// use foreach to iterate from head to end
foreach(var i in arr)
{
Console.WriteLine(i);
}
// use for to forward interate
for(var i=0;i<arr.Length;i++)
{
Console.WriteLine(arr[i]); // array index is zero base.
}
// use for to backward interate
for(var i=arr.Length-1;i>=0;i--)
{
Console.WriteLine(arr[i]);
}
Common mistake:
- forget array is zero based
- use a wrong upper bound, cause array index out of bound
- forget to increase/decrease the loop variable
2D Array scan top down, bottom up
var arr = new int[,]{ {1,2,3}, {4,5,6}, {7,8,9}};
/*
123
456
789
*/
for(var i=0;i<arr.GetLength(0);i++)
{
for(var j=0;j<arr.GetLength(1);j++)
{
Console.Write(arr[i,j]);
}
Console.WriteLine();
}
/*
987
654
321
*/
for(var i=arr.GetLength(0)-1;i>=0;i--)
{
for(var j=arr.GetLength(1)-1;j>=0;j--)
{
Console.Write(arr[i,j]);
}
Console.WriteLine();
}
2D matrix scan diagonal, anti-diagonal
Why this concern me, because some of 2d dynamic programming may scan the matrix this way.
var arr = new int[,]{ {1,2,3}, {4,5,6}, {7,8,9}};
/*
123
56
9
*/
for(var i=0;i<arr.GetLength(0);i++)
{
for(var j=i;j<arr.GetLength(1);j++;)
{
Console.Write(arr[i,j]);
}
Console.WriteLine();
}
//anti-diagonal top-left side
/*
123
45
7
*/
for(var i=0;i<arr.GetLength(0);i++)
{
for(var j=0;j<arr.GetLength(1)-i;j++;)
{
Console.Write(arr[i,j]);
}
Console.WriteLine();
}
//anti-diagonal bottom-right side
/*
3
56
789
*/
for(var i=0;i<arr.GetLength(0);i++)
{
//for(var j=arr.GetLength(1)-1-i;j>=i;j--;)
for(var j=arr.GetLength(1)-1-i;j<arr.GetLength(1);j++)
{
Console.Write(arr[i,j]);
}
Console.WriteLine();
}
2D matrix spiral scan
This is a really interview question, have fun
void MatrixSpiralScan()
{
var arr = new int[,] { {1,2,3,4}, {10,11,12,5 }, {9,8,7,6 }};
/*
1 2 3 4
(10)(11) (12) 5
9 8 7 6
*/
int left = 0, right = arr.GetLength(1);
int top = 0, bottom = arr.GetLength(0)-1;
int left = 0, right = arr.GetLength(1)-1;
while(top<=bottom && left<=right)
{
for(var i=left;i<=right;i++) Console.Write(arr[top, i]);
top++;
for(var i=top;i<=bottom;i++) Console.Write(arr[i, right]);
right--;
if(top<=bottom) // handle one line case
{
for(var i=right;i>=left;i--) Console.Write(arr[bottom, i]);
bottom--;
}
if(left<=right) // handle one column case
{
for(var i=bottom;i>=top;i--) Console.Write(arr[i, left];
left++;
}
}
}
Matrix Rotation
A typical usage is rotate image, see leetcode problem 48. Rotate Image
public void Rotate(int[,] matrix) {
var n = matrix.GetLength(0);
for(var i=0;i<n;++i){ // diagonal rotate
for(var j=i;j<n;j++){ // j must start from i , otherwise, after double rotate, matrix will be restore as same as orignal
var temp = matrix[i,j];
matrix[i,j] = matrix[j,i];
matrix[j,i] = temp;
}
}
for(var j=0;j<n/2;++j){ // reverse according to middle of columns
for(var i=0;i<n;++i){
var temp = matrix[i,j];
matrix[i,j] = matrix[i,n-1-j];
matrix[i,n-1-j] = temp;
}
}
}
More practice
Tips:
When think about clockwise rotate, write down a 3x3 matrix. either horizontal or vertical flip it. After that, you will be able to find ether main diagonal or minor diagonal is as same as what it should be in clockwise rotated matrix, then you will be find the pattern for flip, rotation.
public class MatrixRotation
{
public static T[,] HorizontalFlip<T>(T[,] source)
{
//scan col by col, reverse each column
for (var i = 0; i < source.GetLength(1); i++)
{
int t = 0, b = source.GetLength(0) - 1;
while (t < b)
{
var x = source[t, i];
source[t, i] = source[b, i];
source[b, i] = x;
t++;b--; // don't forget to change loop variable
}
}
return source;
}
public static T[,] VerticalFlip<T>(T[,] source)
{
//scan row by row, reverse each row
for (var i = 0; i < source.GetLength(0); i++)
{
int l = 0, r = source.GetLength(1) - 1;
while (l < r)
{
var t = source[i, l];
source[i, l] = source[i, r];
source[i, r] = t;
l++;r--;
}
}
return source;
}
public static T[,] SquareDiagnoalFlip<T>(T[,] source)
{
// main diagonal = clockwise rotate + vertical flip
// top left to bottom right
int rows = source.GetLength(0);
int cols = source.GetLength(1);
if (rows != cols) throw new InvalidOperationException("Cannot use this algorithm to flip rectangle, must be square!");
for (var i = 0; i < rows; i++)
{
for (var j = 0; j <= i; j++)
{
var x = source[i, j];
source[i, j] = source[j, i];
source[j, i] = x;
}
}
return source;
}
///
public static T[,] DiagnoalFlip<T>(T[,] source)
{
// main diagonal
// top left to bottom right
var res = new T[source.GetLength(1), source.GetLength(0)];
// scan left side main diagnoal, swap with right side
for (var i = 0; i < source.GetLength(0); i++)
{
for (var j = 0; j < source.GetLength(1); j++)
{
res[j, i] = source[i, j];
}
}
return res;
}
public static T[,] AntiDiagnoalFlip<T>(T[,] source)
{
// minor diagnoal or antidiagnoal,for a square it equivalent to clockwise rotate + horizontal flip
// bottom left to top right
int rows = source.GetLength(0);
int cols = source.GetLength(1);
var res = new T[cols, rows];
for (var i = 0; i < rows; i++)
{
for (var j = 0; j < cols; j++)
{
res[cols - j, rows - i] = source[i, j];
}
}
return source;
}
public static T[,] ClockwiseRotate90Degree<T>(T[,] source)
{
// horizontal flip + diagnoal flip
// or vertical flip + anti-diagnoal flip
var res = HorizontalFlip(source);
res = DiagnoalFlip(res);
return res;
}
public static T[,] CounterClockwiseRotate90Degree<T>(T[,] source)
{
// vertical flip + diagnoal flip
var res = VerticalFlip(source);
res = DiagnoalFlip(source);
return res;
}
}
Matrix BFS/DFS Traversal
There are quite a lot of matrix problems which require to traversal matrix in certain direction rules. E.g. only allow go 1 step to four directions, up, down, left, right. or even more direction include diagonal and anti-diagonal directions.
in that case, we use a direction array to manage the increment step for next; we could use either 2D array or 2D jagged array
//4 direction
var directions = new [,] {{0,1},{0,-1},{1,0},{-1,0}}; // right, left, down, up
//8 direction
var directions = new [,] {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
below are leetcode question may use above approach
Trapping Rain Water, Word Search II, Largest Island, Longest Increasing Path In Matrix
Array Sort
var arr = new[]{7,2,4,3,1,6,0,5,9,8};
Array.Sort(arr, (a,b=> b-a)); // Ascending sort
Array.Sort(arr, (a,b=> a.CompareTo(b)) ; Ascending sort
Array.Sort(arr, (a,b=> a-b)); // Descending sort