Return inside loops in C++ - Time & Space Complexity

Time Complexity: Return inside loops

O(n)

Understanding Time Complexity

When a return statement is inside a loop, it can stop the loop early. This affects how long the code runs.

We want to know how the running time changes as the input grows when return is inside a loop.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool containsZero(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            return true;
        }
    }
    return false;
}
    

This code checks if an array has a zero. It stops and returns true as soon as it finds one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array elements one by one.
• How many times: Up to n times, but may stop earlier if zero is found.

How Execution Grows With Input

Execution depends on where zero appears. If zero is early, fewer steps; if none, all elements checked.

Input Size (n)	Approx. Operations
10	Between 1 and 10 checks
100	Between 1 and 100 checks
1000	Between 1 and 1000 checks

Pattern observation: The number of steps can vary from very few to all elements, depending on input.

Final Time Complexity

Time Complexity: O(n)

This means in the worst case, the code checks every element once before returning.

Common Mistake

[X] Wrong: "Because of the return inside the loop, the code always runs fast and checks only one element."

[OK] Correct: The return stops the loop early only if the condition is met early. If not, the loop runs through all elements.

Interview Connect

Understanding how early returns affect loops helps you explain code efficiency clearly and shows you think about best and worst cases.

Self-Check

"What if the return statement was replaced by a flag variable and the loop always ran through all elements? How would the time complexity change?"

Practice

1.

What happens when a return statement is executed inside a loop in a C++ function?

easy

A. The loop runs twice before the function stops.

B. Only the current loop iteration stops, and the loop continues.

C. The function immediately stops and returns the value.

D. The loop skips to the next iteration without stopping the function.

Solution

1. Step 1: Understand the role of return in functions

   The return statement immediately ends the function and sends back a value.

2. Step 2: Analyze return inside a loop

   When return is inside a loop, it stops the entire function, not just the loop.

3. Final Answer:

   The function immediately stops and returns the value. -> Option C

4. Quick Check:

   Return inside loop = function stops [OK]

Hint: Return inside loop ends function immediately [OK]

Common Mistakes:

• Thinking return only stops the loop
• Confusing return with continue or break
• Assuming code after return runs

2.

Which of the following is the correct syntax to return the first even number found in a vector nums using a loop?

for (int i = 0; i < nums.size(); i++) {
    if (nums[i] % 2 == 0) {
        // return here
    }
}

easy

A. return nums[i];

B. return i;

C. return nums;

D. return i + 1;

Solution

1. Step 1: Identify what to return

   The question asks to return the first even number, so we return the value at index i.

2. Step 2: Match the correct return statement

   return nums[i]; returns the actual even number found.

3. Final Answer:

   return nums[i]; -> Option A

4. Quick Check:

   Return value, not index [OK]

Hint: Return the value, not the index, when asked for element [OK]

Common Mistakes:

• Returning the index instead of the value
• Returning the whole vector
• Returning incorrect arithmetic on index

3.

What is the output of the following C++ function when called with findFirstPositive({-3, -1, 0, 4, 5})?

int findFirstPositive(std::vector<int> nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0) {
            return nums[i];
        }
    }
    return -1;
}

medium

A. -1

B. 4

C. 0

D. 5

Solution

1. Step 1: Trace the loop to find first positive

   The loop checks each element: -3 (no), -1 (no), 0 (no), 4 (yes, positive).

2. Step 2: Return the first positive number found

   At 4, the function returns immediately with 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   First positive = 4 [OK]

Hint: Return stops at first positive number found [OK]

Common Mistakes:

• Returning -1 instead of first positive
• Confusing 0 as positive
• Returning last positive instead of first

4.

Identify the error in this function that tries to return the first negative number from a vector nums:

int findNegative(std::vector<int> nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] < 0) {
            return nums[i];
        } else {
            return 0;
        }
    }
    return -1;
}

medium

A. The loop condition is incorrect.

B. The function never returns any value.

C. The return type should be void.

D. The function returns 0 too early inside the loop.

Solution

1. Step 1: Analyze the else return inside the loop

   The else block returns 0 immediately if the first element is not negative, stopping the function early.

2. Step 2: Understand why this is wrong

   This prevents checking all elements; function should only return 0 after full loop if no negative found.

3. Final Answer:

   The function returns 0 too early inside the loop. -> Option D

4. Quick Check:

   Return in else inside loop causes early stop [OK]

Hint: Avoid return in else inside loop; return after loop instead [OK]

Common Mistakes:

• Returning inside else causes premature exit
• Thinking loop runs fully before return
• Misunderstanding return type requirements

5.

Write a function that returns the index of the first zero in a vector nums. If no zero is found, return -1. Which of the following implementations is correct?

Option A:
int findZero(std::vector<int> nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 0) {
            return i;
        }
    }
    return -1;
}

Option B:
int findZero(std::vector<int> nums) {
    int index = -1;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 0) {
            index = i;
        }
    }
    return index;
}

Option C:
int findZero(std::vector<int> nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 0) {
            break;
        }
    }
    return i;
}

Option D:
int findZero(std::vector<int> nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 0) {
            return nums[i];
        }
    }
    return -1;
}

hard

A. Option A

B. Option B

C. Option C

D. Option D

Solution

1. Step 1: Verify the correct logic for finding first zero index

   The implementation that returns i immediately when nums[i] == 0 and -1 after the loop is correct.

2. Step 2: Why others fail

   The one setting a variable continues the loop, returning the last zero's index. The break version doesn't return -1 if no zero found and i goes out of scope. The last returns the value 0 instead of index.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Return index immediately on first zero [OK]

Hint: Return index immediately when found, else after loop return -1 [OK]

Common Mistakes:

• Returning value instead of index
• Returning last zero index instead of first
• Using break without returning causes scope errors