Two-dimensional arrays in C - Time & Space Complexity

Time Complexity: Two-dimensional arrays

O(rows * cols)

Understanding Time Complexity

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

We want to know how the number of operations changes when we access or loop through all elements.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        process(array[i][j]);
    }
}
    

This code goes through every element in a two-dimensional array and processes it once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop processes each element in a row.
• How many times: The inner loop runs cols times for each of the rows iterations of the outer loop.

How Execution Grows With Input

As the number of rows and columns grow, the total operations 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 multiplies the work by four, showing a growth proportional to the product of rows and columns.

Final Time Complexity

Time Complexity: O(rows * cols)

This means the time to complete grows directly with the total number of elements in the two-dimensional array.

Common Mistake

[X] Wrong: "The time complexity is just O(rows) or O(cols) because there are two loops but only one matters."

[OK] Correct: Both loops run fully and multiply the total work, so the total time depends on both dimensions together, not just one.

Interview Connect

Understanding how nested loops over two-dimensional arrays affect time helps you explain and optimize code that works with grids, tables, or matrices in real projects.

Self-Check

"What if we only looped through half the columns in each row? How would the time complexity change?"

Practice

1. What is a two-dimensional array in C?

easy

A. An array of arrays, storing data in rows and columns

B. A single list of numbers stored in a line

C. A function that returns multiple values

D. A variable that holds only one value

Solution

1. Step 1: Understand array structure

   A two-dimensional array stores data in a grid format with rows and columns.

2. Step 2: Compare options

   Only An array of arrays, storing data in rows and columns describes this structure as an array of arrays.

3. Final Answer:

   An array of arrays, storing data in rows and columns -> Option A

4. Quick Check:

   2D array = array of arrays [OK]

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

Common Mistakes:

• Confusing 2D arrays with single arrays
• Thinking 2D arrays are functions
• Assuming 2D arrays hold only one value

2. Which of the following is the correct way to declare a 3x3 integer two-dimensional array in C?

easy

A. int arr(3,3);

B. int arr[3][3];

C. int arr[3,3];

D. int arr{3}{3};

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays use square brackets with sizes inside, like arr[rows][columns].

2. Step 2: Check each option

   Only int arr[3][3]; uses correct syntax: int arr[3][3];

3. Final Answer:

   int arr[3][3]; -> Option B

4. Quick Check:

   Use square brackets for array sizes [OK]

Hint: Use square brackets for array sizes, not parentheses [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Using commas inside brackets
• Using curly braces for declaration

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

int arr[2][2] = {{1, 2}, {3, 4}};
printf("%d", arr[1][0]);

medium

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Understand array initialization

   The array arr has two rows: first row {1, 2}, second row {3, 4}.

2. Step 2: Access element arr[1][0]

   Row index 1 is second row, column index 0 is first element in that row, which is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   arr[1][0] = 3 [OK]

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

Common Mistakes:

• Confusing row and column indexes
• Starting index at 1 instead of 0
• Mixing up elements in initialization

4. Identify the error in the following C code snippet:

int matrix[2][3];
matrix[2][1] = 5;

medium

A. Wrong data type for matrix

B. No error, code is correct

C. Syntax error due to missing semicolon

D. Index out of bounds error on matrix[2][1]

Solution

1. Step 1: Check array size and valid indexes

   matrix is declared with 2 rows (0 and 1) and 3 columns (0 to 2).

2. Step 2: Analyze matrix[2][1]

   Row index 2 is invalid because valid rows are 0 and 1 only, causing out of bounds error.

3. Final Answer:

   Index out of bounds error on matrix[2][1] -> Option D

4. Quick Check:

   Row index must be less than 2 [OK]

Hint: Array indexes start at 0 and go to size-1 [OK]

Common Mistakes:

• Using index equal to array size
• Ignoring zero-based indexing
• Assuming no error for out-of-range access

5. Given the 2D array declaration int grid[3][3] = {{1,2,3},{4,5,6},{7,8,9}};, which code snippet correctly calculates the sum of all elements?

hard

A. int sum=0; for(int i=1;i<3;i++) for(int j=1;j<3;j++) sum += grid[i][j]; printf("%d", sum);

B. int sum=0; for(int i=0;i<=3;i++) for(int j=0;j<=3;j++) sum += grid[i][j]; printf("%d", sum);

C. int sum=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) sum += grid[i][j]; printf("%d", sum);

D. int sum=0; for(int i=0;i<3;i++) sum += grid[i]; printf("%d", sum);

Solution

1. Step 1: Understand array size and loops

   grid has 3 rows and 3 columns, so indexes go from 0 to 2.

2. Step 2: Check loop bounds and summation

   int sum=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) sum += grid[i][j]; printf("%d", sum); uses correct loop bounds (i<3, j<3) and sums all elements correctly.

3. Step 3: Analyze other options

   int sum=0; for(int i=0;i<=3;i++) for(int j=0;j<=3;j++) sum += grid[i][j]; printf("%d", sum); uses <=3 causing out-of-bounds access; the option starting loops at 1 misses first row and column elements; the option trying sum += grid[i] is invalid for 2D arrays.

4. Final Answer:

   int sum=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) sum += grid[i][j]; printf("%d", sum); -> Option C

5. Quick Check:

   Use correct loop bounds and access grid[i][j] [OK]

Hint: Loop from 0 to size-1 for both rows and columns [OK]

Common Mistakes:

• Using <= instead of < in loops
• Starting loops at 1 instead of 0
• Trying to add entire row instead of elements