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

Time Complexity: Jagged arrays

O(n)

Understanding Time Complexity

When working with jagged arrays, it is important to understand how the time to process them grows as their size changes.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[][] jagged = new int[3][];
jagged[0] = new int[2] {1, 2};
jagged[1] = new int[3] {3, 4, 5};
jagged[2] = new int[1] {6};

for (int i = 0; i < jagged.Length; i++) {
    for (int j = 0; j < jagged[i].Length; j++) {
        Console.WriteLine(jagged[i][j]);
    }
}
    

This code loops through each sub-array inside a jagged array and prints every element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and printing each element inside the nested loops.
• How many times: Once for every element in all sub-arrays combined.

How Execution Grows With Input

As the total number of elements in all sub-arrays grows, the number of operations grows roughly the same way.

Input Size (total elements)	Approx. Operations
10	About 10 prints
100	About 100 prints
1000	About 1000 prints

Pattern observation: The time grows directly with the total number of elements across all sub-arrays.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the loops grows in direct proportion to the total number of elements in the jagged array.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity must be O(n²)."

[OK] Correct: The inner loop runs a different number of times depending on each sub-array's length, so total operations add up to the total elements, not their square.

Interview Connect

Understanding how nested loops over jagged arrays behave helps you explain and analyze real code that handles uneven data structures, a common task in programming.

Self-Check

"What if all sub-arrays had the same length? How would the time complexity change, if at all?"

Practice

1. What is a jagged array in C#?

easy

A. An array of arrays where inner arrays can have different lengths

B. A two-dimensional array with fixed rows and columns

C. An array that stores only integers

D. A single-dimensional array with fixed size

Solution

1. Step 1: Understand array types in C#

   A jagged array is an array whose elements are arrays themselves, allowing different lengths for each inner array.

2. Step 2: Compare with other array types

   Unlike two-dimensional arrays, jagged arrays do not require all inner arrays to have the same size.

3. Final Answer:

   An array of arrays where inner arrays can have different lengths -> Option A

4. Quick Check:

   Jagged array = array of arrays with varying lengths [OK]

Hint: Jagged arrays hold arrays inside arrays with different sizes [OK]

Common Mistakes:

• Confusing jagged arrays with 2D arrays
• Thinking all inner arrays must be same length
• Assuming jagged arrays store only one data type

2. Which of the following is the correct way to declare a jagged array of integers in C#?

easy

A. int[][] jaggedArray = new int[3][];

B. int[] jaggedArray = new int[3,3];

C. int[] jaggedArray = new int[3][];

D. int jaggedArray[][] = new int[3][];

Solution

1. Step 1: Recall jagged array declaration syntax

   Jagged arrays use double square brackets: int[][] to declare an array of arrays.

2. Step 2: Check each option

   int[][] jaggedArray = new int[3][]; correctly declares a jagged array with 3 inner arrays uninitialized. int[] jaggedArray = new int[3,3]; is a 2D array, not jagged. int[] jaggedArray = new int[3][]; has wrong type on left side. int jaggedArray[][] = new int[3][]; has invalid syntax.

3. Final Answer:

   int[][] jaggedArray = new int[3][]; -> Option A

4. Quick Check:

   Use int[][] for jagged arrays [OK]

Hint: Use double brackets [][] to declare jagged arrays [OK]

Common Mistakes:

• Using single brackets for jagged arrays
• Confusing jagged arrays with 2D arrays
• Incorrect syntax like int jaggedArray[][]

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

int[][] jagged = new int[2][];
jagged[0] = new int[] {1, 2};
jagged[1] = new int[] {3, 4, 5};
Console.WriteLine(jagged[1][2]);

medium

A. 3

B. IndexOutOfRangeException

C. 2

D. 5

Solution

1. Step 1: Understand jagged array initialization

   The jagged array has two inner arrays: jagged[0] = {1, 2} and jagged[1] = {3, 4, 5}.

2. Step 2: Access jagged[1][2]

   jagged[1] is {3, 4, 5}, so index 2 is the third element, which is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   jagged[1][2] = 5 [OK]

Hint: Remember zero-based indexing for inner arrays [OK]

Common Mistakes:

• Confusing indices and picking wrong element
• Assuming all inner arrays have same length
• Expecting runtime error for valid index

4. Identify the error in the following jagged array code:

int[][] jagged = new int[2][];
jagged[0] = new int[2] {1, 2};
Console.WriteLine(jagged[1][0]);

medium

A. Cannot use Console.WriteLine with jagged arrays

B. jagged[1] is not initialized before accessing

C. Inner arrays must have same length

D. Syntax error in jagged array declaration

Solution

1. Step 1: Check initialization of inner arrays

   jagged[0] is initialized, but jagged[1] is not assigned any array.

2. Step 2: Accessing uninitialized inner array

   Accessing jagged[1][0] causes a NullReferenceException because jagged[1] is null.

3. Final Answer:

   jagged[1] is not initialized before accessing -> Option B

4. Quick Check:

   Initialize all inner arrays before access [OK]

Hint: Always initialize each inner array before use [OK]

Common Mistakes:

• Assuming inner arrays auto-initialize
• Ignoring NullReferenceException possibility
• Thinking jagged arrays require equal inner lengths

5. Given a jagged array int[][] data where each inner array represents scores of students in different subjects, how would you calculate the total sum of all scores?

hard

A. Use a single loop over data.Length and sum data[i][0] only

B. Sum only the first inner array elements

C. Use nested loops to iterate each inner array and sum all elements

D. Use jaggedArray.Sum() directly without loops

Solution

1. Step 1: Understand jagged array structure

   Each inner array has varying length representing scores per student.

2. Step 2: Use nested loops to sum all elements

   Outer loop iterates each inner array; inner loop sums elements inside each inner array.

3. Step 3: Avoid incorrect approaches

   Summing only first inner array or first element misses data; jaggedArray.Sum() won't work directly as it's an array of arrays.

4. Final Answer:

   Use nested loops to iterate each inner array and sum all elements -> Option C

5. Quick Check:

   Nested loops sum all jagged array elements [OK]

Hint: Sum jagged arrays with nested loops over all inner arrays [OK]

Common Mistakes:

• Summing only one inner array
• Using single loop ignoring inner arrays
• Expecting built-in sum on jagged array