Multi-dimensional arrays in C++ - Time & Space Complexity

Time Complexity: Multi-dimensional arrays

O(n * m)

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 operations 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[3][4] = {0};
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        matrix[i][j] = i + j;
    }
}
    

This code fills a 3 by 4 matrix with the sum of its indices.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop writes to each element of the matrix.
• How many times: The inner loop runs 4 times for each of the 3 outer loop iterations, totaling 12 times.

How Execution Grows With Input

Imagine the matrix size changes to n rows and m columns. The total operations grow as the product of n and m.

Input Size (n x m)	Approx. Operations
3 x 4	12
10 x 10	100
100 x 100	10,000

Pattern observation: Doubling both dimensions roughly quadruples the operations because you visit every element.

Final Time Complexity

Time Complexity: O(n * m)

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

Common Mistake

[X] Wrong: "The time complexity is O(n) because there is only one loop inside another."

[OK] Correct: Each loop multiplies the work. The inner loop runs completely for every outer loop iteration, so total work is the product, not just one loop's size.

Interview Connect

Understanding how nested loops over multi-dimensional arrays affect time helps you explain and optimize code clearly in interviews.

Self-Check

"What if the inner loop size depends on the outer loop index (e.g., j runs from 0 to i)? How would the time complexity change?"

Practice

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

easy

A. A variable that holds a single number

B. An array that stores only one value

C. A function that returns multiple values

D. An array with more than one index, like rows and columns

Solution

1. Step 1: Understand array dimensions

   A multi-dimensional array uses multiple indexes to access elements, such as row and column in a table.

2. Step 2: Compare options

   Only An array with more than one index, like rows and columns describes an array with more than one index, matching the concept of multi-dimensional arrays.

3. Final Answer:

   An array with more than one index, like rows and columns -> Option D

4. Quick Check:

   Multi-dimensional array = multiple indexes [OK]

Hint: Think of rows and columns in a table for multi-dimensional arrays [OK]

Common Mistakes:

• Confusing arrays with single values
• Thinking functions return multiple values
• Mixing variables with arrays

2. Which of the following is the correct way to declare a 2D array of integers with 3 rows and 4 columns in C++?

easy

A. int arr[3][4];

B. int arr(3,4);

C. int arr[4][3];

D. int arr{3,4};

Solution

1. Step 1: Recall C++ 2D array syntax

   The correct syntax uses square brackets with sizes: int arr[rows][columns];

2. Step 2: Check each option

   int arr[3][4]; uses int arr[3][4]; which means 3 rows and 4 columns, correct syntax. Others are invalid or reversed.

3. Final Answer:

   int arr[3][4]; -> Option A

4. Quick Check:

   Use square brackets for dimensions [OK]

Hint: Use square brackets for rows and columns in declaration [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Swapping row and column sizes
• Using curly braces for declaration

3. What is the output of the following C++ code?

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
std::cout << arr[1][2];

medium

A. 6

B. 3

C. 4

D. 2

Solution

1. Step 1: Understand array initialization

   The array has 2 rows and 3 columns: first row {1,2,3}, second row {4,5,6}.

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

   Row index 1 is second row, column index 2 is third element: value is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   arr[1][2] = 6 [OK]

Hint: Remember indexes start at 0; arr[1][2] is second row, third column [OK]

Common Mistakes:

• Confusing row and column indexes
• Forgetting zero-based indexing
• Reading wrong element from array

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

int matrix[2][2] = {{1, 2}, {3}};
std::cout << matrix[1][1];

medium

A. Missing value in second row initialization

B. Array size mismatch causes compile error

C. No error, code runs and prints 0

D. Incorrect use of std::cout syntax

Solution

1. Step 1: Check array initialization

   The second row has only one value {3}, missing one element for 2 columns.

2. Step 2: Understand C++ behavior for missing elements

   Missing elements are initialized to 0 automatically, so matrix[1][1] is 0.

3. Step 3: Check output statement

   std::cout syntax is correct, so it prints 0 without error.

4. Final Answer:

   No error, code runs and prints 0 -> Option C

5. Quick Check:

   Missing elements default to 0 in arrays [OK]

Hint: Missing elements in array init become zero, no error [OK]

Common Mistakes:

• Assuming missing elements cause errors
• Thinking std::cout syntax is wrong
• Expecting garbage values instead of zero

5. How can you sum all elements of a 3x3 integer array named grid in C++?

hard

A. Use std::accumulate directly on the 2D array

B. Use nested loops to add each element to a sum variable

C. Use a single loop from 0 to 8 to sum elements

D. Add only the first row elements

Solution

1. Step 1: Understand 2D array traversal

   To access all elements in a 3x3 array, use two loops: one for rows, one for columns.

2. Step 2: Sum elements with nested loops

   Inside inner loop, add each element grid[i][j] to a sum variable to get total sum.

3. Final Answer:

   Use nested loops to add each element to a sum variable -> Option B

4. Quick Check:

   Nested loops sum all elements [OK]

Hint: Use two loops: outer for rows, inner for columns [OK]

Common Mistakes:

• Using single loop ignoring 2D structure
• Summing only part of the array
• Trying to use std::accumulate on 2D array directly