Array traversal in Java - Time & Space Complexity

Time Complexity: Array traversal

O(n)

Understanding Time Complexity

When we look at array traversal, we want to know how the time to run the code changes as the array gets bigger.

We ask: How many steps does it take to go through all the items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}
    

This code goes through each item in the array and prints it out one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that visits each element in the array.
• How many times: Exactly once for each element, so as many times as the array length.

How Execution Grows With Input

As the array gets bigger, the number of steps grows in a straight line with the size.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: Doubling the array size doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the number of items in the array.

Common Mistake

[X] Wrong: "The loop runs faster because it just prints items quickly."

[OK] Correct: The speed of printing does not change how many times the loop runs; it still visits every item once.

Interview Connect

Understanding how array traversal scales helps you explain simple but important code clearly in interviews.

Self-Check

"What if we nested another loop inside to compare each element with every other? How would the time complexity change?"

Practice

1. What does array traversal mean in Java?
int[] arr = {1, 2, 3};

easy

A. Creating a new array with the same elements

B. Visiting each element of the array one by one using a loop

C. Sorting the array elements in ascending order

D. Deleting elements from the array

Solution

1. Step 1: Understand array traversal meaning

   Array traversal means going through each element in the array one by one.

2. Step 2: Match with given options

   Only Visiting each element of the array one by one using a loop describes visiting each element using a loop, which is traversal.

3. Final Answer:

   Visiting each element of the array one by one using a loop -> Option B

4. Quick Check:

   Array traversal = visiting elements one by one [OK]

Hint: Traversal means visiting all elements step-by-step [OK]

Common Mistakes:

• Confusing traversal with sorting
• Thinking traversal means deleting elements
• Mixing traversal with creating new arrays

2. Which of the following is the correct syntax to traverse an array int[] nums in Java?

easy

A. for(int i = 0; i < nums.length; i++) { System.out.println(nums[i]); }

B. for(int i = 1; i <= nums.length; i++) { System.out.println(nums[i]); }

C. for(int i = 0; i <= nums.length; i++) { System.out.println(nums[i]); }

D. for(int i = 0; i < nums.length - 1; i++) { System.out.println(nums[i]); }

Solution

1. Step 1: Check loop start and end conditions

   The loop should start at 0 and run while i is less than nums.length to cover all indices.

2. Step 2: Validate array access inside loop

   Accessing nums[i] is correct if i is within 0 to length-1. for(int i = 0; i < nums.length; i++) { System.out.println(nums[i]); } satisfies this.

3. Final Answer:

   for(int i = 0; i < nums.length; i++) { System.out.println(nums[i]); } -> Option A

4. Quick Check:

   Loop from 0 to length-1 = correct traversal [OK]

Hint: Loop from 0 to less than length for full traversal [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= length causing index out of bounds
• Stopping loop early at length - 1

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

int[] arr = {5, 10, 15};
for(int i = 0; i < arr.length; i++) {
  System.out.print(arr[i] + " ");
}

medium

A. 5 10 15

B. 15 10 5

C. 5 10 15 0

D. Error: ArrayIndexOutOfBoundsException

Solution

1. Step 1: Understand the loop iteration

   The loop runs from i=0 to i=2 (arr.length=3), printing arr[i] each time.

2. Step 2: Check printed values

   Values printed are arr[0]=5, arr[1]=10, arr[2]=15, each followed by a space.

3. Final Answer:

   5 10 15 -> Option A

4. Quick Check:

   Print elements in order = 5 10 15 [OK]

Hint: Prints elements in order from index 0 to length-1 [OK]

Common Mistakes:

• Assuming reverse order output
• Expecting extra zero at end
• Thinking loop causes index error

4. Identify the error in this array traversal code:

int[] data = {2, 4, 6};
for(int i = 0; i <= data.length; i++) {
  System.out.println(data[i]);
}

medium

A. System.out.println should be outside the loop

B. Array declaration is incorrect

C. Loop condition should be i < data.length, not <= data.length

D. No error, code runs fine

Solution

1. Step 1: Analyze loop condition

   The loop runs while i <= data.length, which means i can be equal to data.length (3).

2. Step 2: Check array index access

   Accessing data[3] causes ArrayIndexOutOfBoundsException because valid indices are 0 to 2.

3. Final Answer:

   Loop condition should be i < data.length, not <= data.length -> Option C

4. Quick Check:

   Index must be less than length to avoid error [OK]

Hint: Use i < length, not i <= length in loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring array index limits
• Thinking loop runs without error

5. Given an array int[] nums = {3, 6, 9, 12, 15};, write code to print only the even numbers by traversing the array.

hard

A. for(int i = 0; i < nums.length - 1; i++) { System.out.print(nums[i] + " "); }

B. for(int i = 1; i <= nums.length; i++) { if(nums[i] % 2 == 0) System.out.print(nums[i] + " "); }

C. for(int i = 0; i < nums.length; i++) { if(nums[i] % 2 != 0) System.out.print(nums[i] + " "); }

D. for(int i = 0; i < nums.length; i++) { if(nums[i] % 2 == 0) System.out.print(nums[i] + " "); }

Solution

1. Step 1: Traverse the array correctly

   Loop from i=0 to i < nums.length to visit all elements safely.

2. Step 2: Check condition for even numbers

   Use nums[i] % 2 == 0 to find even numbers and print them.

3. Final Answer:

   for(int i = 0; i < nums.length; i++) { if(nums[i] % 2 == 0) System.out.print(nums[i] + " "); } -> Option D

4. Quick Check:

   Traverse all and print only even numbers [OK]

Hint: Check nums[i] % 2 == 0 inside loop to print evens [OK]

Common Mistakes:

• Using wrong loop bounds causing errors
• Printing odd numbers instead of even
• Missing condition inside loop