Iterating over arrays in Go - Time & Space Complexity

Time Complexity: Iterating over arrays

O(n)

Understanding Time Complexity

When we go through each item in an array one by one, it takes some time. We want to understand how this time grows as the array gets bigger.

The question is: How does the work change when the array size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func sumArray(arr []int) int {
    total := 0
    for _, value := range arr {
        total += value
    }
    return total
}

This code adds up all numbers in an array by visiting each element once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each element to total inside the loop.
• How many times: Once for every element in the array.

How Execution Grows With Input

As the array gets bigger, the number of additions grows at the same pace.

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

Pattern observation: The work grows directly with the number of items. Double the items, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Since the loop is simple, it must be constant time."

[OK] Correct: Even a simple loop does more work as the array grows. The time depends on how many elements there are.

Interview Connect

Understanding how loops over arrays scale is a key skill. It helps you explain your code clearly and shows you know how programs behave with bigger data.

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 the range keyword do when used with an array in Go?

easy

A. It creates a new array with copied elements.

B. It changes the size of the array during iteration.

C. It lets you loop over each element and get its index and value.

D. It sorts the array elements automatically.

Solution

1. Step 1: Understand the role of range in loops

   The range keyword in Go is used to iterate over elements in arrays, slices, maps, and more, providing both the index and the value of each element.

2. Step 2: Identify what range does with arrays

   When used with an array, range returns the index and the value of each element one by one, allowing you to process or read each item.

3. Final Answer:

   It lets you loop over each element and get its index and value. -> Option C

4. Quick Check:

   range loops with index and value [OK]

Hint: Remember: range gives index and value for each element [OK]

Common Mistakes:

• Thinking range changes array size
• Assuming range sorts elements
• Believing range copies the array

2. Which of the following is the correct syntax to iterate over an array named nums in Go?

easy

A. for i, v := range nums { fmt.Println(i, v) }

B. for i in nums { fmt.Println(i) }

C. foreach i, v in nums { fmt.Println(i, v) }

D. for (i, v) in nums { fmt.Println(i, v) }

Solution

1. Step 1: Recall Go's for-range loop syntax

   In Go, the correct way to iterate over arrays or slices is using for index, value := range array syntax.

2. Step 2: Match the syntax with the options

   for i, v := range nums { fmt.Println(i, v) } uses for i, v := range nums, which is the correct Go syntax. Other options use invalid or non-Go syntax.

3. Final Answer:

   for i, v := range nums { fmt.Println(i, v) } -> Option A

4. Quick Check:

   Go uses for i, v := range array [OK]

Hint: Use 'for i, v := range array' for Go array loops [OK]

Common Mistakes:

• Using 'for i in nums' like Python
• Using 'foreach' which is not Go syntax
• Using parentheses in for loop header

3. What will be the output of this Go code?

nums := [3]int{10, 20, 30}
for i, v := range nums {
    fmt.Println(i, v)
}

medium

A. 0 0
1 1
2 2

B. 10 0
20 1
30 2

C. Syntax error

D. 0 10
1 20
2 30

Solution

1. Step 1: Understand the array and loop

   The array nums has 3 elements: 10 at index 0, 20 at index 1, and 30 at index 2. The loop uses range to get index and value.

2. Step 2: Trace the loop output

   Each iteration prints the index and the value: first line prints "0 10", second "1 20", third "2 30".

3. Final Answer:

   0 10 1 20 2 30 -> Option D

4. Quick Check:

   Index and value printed in order [OK]

Hint: range returns index then value in order [OK]

Common Mistakes:

• Swapping index and value in print
• Expecting values as indexes
• Thinking code has syntax error

4. Identify the error in this Go code snippet:

nums := [3]int{1, 2, 3}
for i, v = range nums {
    fmt.Println(i, v)
}

medium

A. Missing colon in 'for i, v = range nums' should be ':='

B. Using '=' instead of '==' in loop condition

C. Array declaration syntax is wrong

D. fmt.Println cannot print two variables

Solution

1. Step 1: Check the for loop variable declaration

   In Go, when declaring variables in a for-range loop, you must use ':=' to declare and assign variables, not '='.

2. Step 2: Identify the syntax error

   The code uses '=' instead of ':=' in for i, v = range nums, which causes a syntax error.

3. Final Answer:

   Missing colon in 'for i, v = range nums' should be ':=' -> Option A

4. Quick Check:

   Use ':=' to declare variables in for-range loops [OK]

Hint: Use ':=' not '=' in for-range variable declaration [OK]

Common Mistakes:

• Using '=' instead of ':=' in for loop
• Confusing assignment with comparison
• Incorrect array syntax blamed

5. Given an array nums := [5]int{1, 2, 3, 4, 5}, how can you create a new slice containing only the even numbers using iteration?

hard

A. Use a for loop to change the array size and remove odd numbers.

B. Use a for-range loop to check each value and append even numbers to a slice.

C. Use range to multiply all numbers by 2 and store in a new array.

D. Use a for loop with index only and ignore values.

Solution

1. Step 1: Understand the goal and array

   The goal is to create a new slice with only even numbers from the array nums. Arrays have fixed size, so we cannot remove elements from it.

2. Step 2: Use for-range loop and append even values

   We iterate over nums using for _, v := range nums, check if v % 2 == 0, and append those values to a new slice.

3. Final Answer:

   Use a for-range loop to check each value and append even numbers to a slice. -> Option B

4. Quick Check:

   Filter with for-range and append even numbers [OK]

Hint: Filter with for-range and append to slice [OK]

Common Mistakes:

• Trying to change array size directly
• Ignoring values in loop
• Multiplying instead of filtering