Two-dimensional arrays in Java - Time & Space Complexity

Time Complexity: Two-dimensional arrays

O(n * m)

Understanding Time Complexity

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

We want to know how the number of operations changes when we loop through all elements in a 2D array.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[][] matrix = new int[n][m];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        matrix[i][j] = i + j;
    }
}
    

This code fills every element in a two-dimensional array with the sum of its row and column indices.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Assigning a value to each element in the 2D array.
• How many times: The inner loop runs m times for each of the n iterations of the outer loop, so n x m times in total.

How Execution Grows With Input

As the number of rows (n) and columns (m) increase, the total operations grow by multiplying these two sizes.

Input Size (n x m)	Approx. Operations
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: Doubling both dimensions causes the operations to increase by four times, showing a growth proportional to the product of n and m.

Final Time Complexity

Time Complexity: O(n * m)

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

Common Mistake

[X] Wrong: "The time complexity is O(n) because there is an outer loop running n times."

[OK] Correct: The inner loop also runs m times for each outer loop iteration, so the total work depends on both n and m multiplied together, not just n.

Interview Connect

Understanding how nested loops over two-dimensional arrays affect time helps you explain and reason about performance clearly in interviews.

Self-Check

"What if the inner loop only ran up to a fixed number instead of m? How would the time complexity change?"

Practice

1. What does a two-dimensional array in Java represent?

easy

A. A collection of unrelated variables

B. A single list of elements

C. A table with rows and columns

D. A method to sort numbers

Solution

1. Step 1: Understand the structure of two-dimensional arrays

   Two-dimensional arrays store data in rows and columns, like a grid or table.

2. Step 2: Compare options with the definition

   Only A table with rows and columns correctly describes this as a table with rows and columns.

3. Final Answer:

   A table with rows and columns -> Option C

4. Quick Check:

   Two-dimensional array = table [OK]

Hint: Think of it as a spreadsheet with rows and columns [OK]

Common Mistakes:

• Confusing with one-dimensional arrays
• Thinking it's a list of unrelated variables
• Mixing arrays with methods

2. Which of the following is the correct way to declare a two-dimensional array of integers in Java?

easy

A. int matrix[3][4];

B. int[][] matrix = new int[3][4];

C. int matrix = new int[3,4];

D. int[] matrix = new int[3][4];

Solution

1. Step 1: Recall Java syntax for 2D array declaration

   Java uses int[][] name = new int[rows][columns]; to declare 2D arrays.

2. Step 2: Check each option

   int[][] matrix = new int[3][4]; matches correct syntax. int matrix[3][4]; is C-style, invalid in Java. int matrix = new int[3,4]; uses comma, invalid. int[] matrix = new int[3][4]; declares a 1D array incorrectly.

3. Final Answer:

   int[][] matrix = new int[3][4]; -> Option B

4. Quick Check:

   Correct 2D array syntax = int[][] matrix = new int[3][4]; [OK]

Hint: Use double brackets [][] and new with sizes [OK]

Common Mistakes:

• Using commas instead of separate brackets
• Trying C-style declarations
• Mixing 1D and 2D array syntax

3. What is the output of the following Java code?

int[][] arr = {{1, 2}, {3, 4}, {5, 6}};
System.out.println(arr[1][0]);

medium

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Identify the element at arr[1][0]

   arr[1] is the second row: {3, 4}. The element at index 0 in this row is 3.

2. Step 2: Confirm the printed value

   System.out.println prints arr[1][0], 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 indices
• Starting count at 1 instead of 0
• Mixing up elements in nested arrays

4. Find the error in the following code snippet:

int[][] grid = new int[2][3];
grid[2][1] = 5;

medium

A. Array index out of bounds error

B. Syntax error in declaration

C. Missing initialization of array

D. No error, code runs fine

Solution

1. Step 1: Check array size and indices used

   Array grid has 2 rows (indices 0 and 1) and 3 columns (indices 0 to 2). Accessing grid[2][1] uses row index 2 which is out of bounds.

2. Step 2: Identify the error type

   Accessing an invalid index causes ArrayIndexOutOfBoundsException at runtime.

3. Final Answer:

   Array index out of bounds error -> Option A

4. Quick Check:

   Index 2 invalid for 2-row array [OK]

Hint: Check array size before accessing indices [OK]

Common Mistakes:

• Using indices equal to array length
• Confusing rows and columns sizes
• Assuming arrays auto-expand

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

hard

A. int sum = 0;
for(int i=0; i

B. int sum = 0;
for(int i=0; i

C. int sum = 0;
for(int i=0; i

D. int sum = 0;
for(int i=0; i

Solution

1. Step 1: Understand array dimensions and iteration

   data.length is number of rows (3). data[i].length is number of columns (2). Nested loops must iterate rows then columns.

2. Step 2: Analyze each option's loop structure

   int sum = 0; for(int i=0; i

3. Final Answer:

   The nested loops with outer loop on data.length and inner on data[i].length -> Option D

4. Quick Check:

   Correct nested loops sum all elements [OK]

Hint: Outer loop rows, inner loop columns for 2D arrays [OK]

Common Mistakes:

• Swapping row and column loops
• Adding arrays directly to int
• Using wrong indices in loops