Multi-dimensional arrays in C Sharp (C#) - Time & Space Complexity

Time Complexity: Multi-dimensional arrays

O(rows * cols)

Understanding Time Complexity

When working with multi-dimensional arrays, it is important to understand how the time to process them grows as their size increases.

We want to know how the number of steps changes when we access or loop through all elements in these arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[,] matrix = new int[rows, cols];
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        matrix[i, j] = i + j;
    }
}
    

This code fills every element in a two-dimensional array by looping through each row and column.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops accessing each element in the 2D array.
• How many times: The inner loop runs once for each column, and the outer loop runs once for each row, so total operations equal rows x cols.

How Execution Grows With Input

As the number of rows and columns grows, the total steps grow by multiplying these two sizes.

Input Size (rows x cols)	Approx. Operations
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: Doubling both rows and columns causes the total operations to grow by four times, showing a multiplication effect.

Final Time Complexity

Time Complexity: O(rows * cols)

This means the time to complete the task grows proportionally to the total number of elements in the multi-dimensional array.

Common Mistake

[X] Wrong: "The time complexity is O(rows + cols) because there are two loops."

[OK] Correct: The loops are nested, so for each row, all columns are processed, multiplying the work instead of adding it.

Interview Connect

Understanding how nested loops over multi-dimensional arrays affect time helps you explain and optimize code that deals with grids, tables, or images.

Self-Check

"What if we changed the inner loop to only run half the columns? How would the time complexity change?"

Practice

1. What is a multi-dimensional array in C#?

easy

A. An array that can only hold one value

B. An array that stores only strings

C. An array with more than one dimension, like rows and columns

D. A list of unrelated variables

Solution

1. Step 1: Understand array dimensions

   A multi-dimensional array stores data in multiple dimensions, such as rows and columns, unlike a simple one-dimensional array.

2. Step 2: Recognize the definition

   An array with more than one dimension, like rows and columns correctly describes a multi-dimensional array as having more than one dimension, like a table with rows and columns.

3. Final Answer:

   An array with more than one dimension, like rows and columns -> Option C

4. Quick Check:

   Multi-dimensional array = rows and columns [OK]

Hint: Think of a table with rows and columns [OK]

Common Mistakes:

• Confusing multi-dimensional arrays with simple lists
• Thinking arrays can only hold one type of data
• Believing multi-dimensional arrays are unrelated variables

2. Which of the following is the correct way to declare a 2x3 multi-dimensional array of integers in C#?

easy

A. int[,] arr = new int[2,3];

B. int[][] arr = new int[2][3];

C. int arr[2,3];

D. int arr = new int[2,3];

Solution

1. Step 1: Recall C# multi-dimensional array syntax

   In C#, a 2D array is declared with commas inside square brackets: int[,] arr = new int[rows, columns];

2. Step 2: Check each option

   int[,] arr = new int[2,3]; uses correct syntax. int[][] arr = new int[2][3]; is jagged array syntax, not multi-dimensional. Options A and C are invalid syntax.

3. Final Answer:

   int[,] arr = new int[2,3]; -> Option A

4. Quick Check:

   Use comma inside brackets for multi-dimensional arrays [OK]

Hint: Use comma inside brackets for multi-dimensional arrays [OK]

Common Mistakes:

• Using jagged array syntax instead of multi-dimensional
• Missing 'new' keyword or wrong brackets
• Confusing array declaration with other languages

3. What will be the output of the following C# code?

int[,] matrix = { {1, 2, 3}, {4, 5, 6} };
Console.WriteLine(matrix[1, 2]);

medium

A. 3

B. 5

C. Runtime error

D. 6

Solution

1. Step 1: Understand array indexing

   matrix[1, 2] means row 1, column 2. Rows and columns start at 0.

2. Step 2: Locate the value at matrix[1, 2]

   Row 1 is {4, 5, 6}, column 2 is the third element, which is 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   matrix[1,2] = 6 [OK]

Hint: Remember indexing starts at zero for rows and columns [OK]

Common Mistakes:

• Confusing row and column indexes
• Starting count from 1 instead of 0
• Expecting the value 3 or 5 instead of 6

4. Identify the error in this C# code snippet:

int[,] grid = new int[3, 3];
grid[3, 0] = 10;

medium

A. Index out of range error at grid[3, 0]

B. Syntax error in array declaration

C. Missing initialization of array

D. No error, code runs fine

Solution

1. Step 1: Check array size and valid indexes

   The array grid has size 3x3, so valid row indexes are 0, 1, 2.

2. Step 2: Analyze the assignment grid[3, 0]

   Index 3 for row is out of range, causing an IndexOutOfRangeException at runtime.

3. Final Answer:

   Index out of range error at grid[3, 0] -> Option A

4. Quick Check:

   Index 3 invalid for size 3 array [OK]

Hint: Indexes start at 0, max index is size-1 [OK]

Common Mistakes:

• Using index equal to array size
• Confusing syntax error with runtime error
• Assuming arrays auto-expand on invalid index

5. Given a 3x3 multi-dimensional array int[,] board representing a tic-tac-toe game, which code snippet correctly counts how many cells contain the value 1?

int count = 0;
// Which loop is correct?
A) for (int i = 0; i < 3; i++)
   for (int j = 0; j < 3; j++)
       if (board[i, j] == 1) count++;

B) for (int i = 1; i <= 3; i++)
   for (int j = 1; j <= 3; j++)
       if (board[i, j] == 1) count++;

C) for (int i = 0; i < 3; i++)
   for (int j = 0; j < 2; j++)
       if (board[i, j] == 1) count++;

D) for (int i = 0; i < 3; i++)
   for (int j = 0; j < 3; j++)
       if (board[j, i] == 1) count++;

hard

A. rorre egnar fo tuo xedni sesuaC

B. Causes index out of range error

C. Misses last column in counting

D. Counts transposed cells, not original positions

Solution

1. Step 1: Understand array indexing and loop ranges

   Indexes start at 0 and go up to size-1, so loops must run from 0 to less than 3.

2. Step 2: Analyze each option's loops

   Causes index out of range error correctly counts all cells with value 1 loops correctly over all rows and columns. Causes index out of range error causes index out of range error uses 1 to 3, causing out of range. Misses last column in counting misses last column by looping j to 2. Counts transposed cells, not original positions swaps indexes, counting transposed cells.

3. Final Answer:

   Causes index out of range error -> Option B

4. Quick Check:

   Loop from 0 to less than size for rows and columns [OK]

Hint: Loop indexes from 0 to size-1 for all dimensions [OK]

Common Mistakes:

• Starting loops at 1 instead of 0
• Using wrong loop limits causing missed elements
• Swapping row and column indexes accidentally