Why is 'break;' not working as expected for an if statement inside a nested loop?

Question

I am trying the Two Sum Question on LeetCode. This is my code -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> output{};
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < nums.size(); j++){
                if (nums[i] + nums[j] == target && i - j != 0){
                    output.push_back(i);
                    output.push_back(j);
                    break;
                }
            }
        }
        return output;
    }
};

For an input of -

[3,2,4]
6

The output is -

[1,2,2,1]

While it should actually be -

[1,2]

which means that the break statement under if in the nested for loop causes the loop to break whenever the if statement is true. But that is not happening here.

Only when I changed the nested for loop's initialization from -

int j = 0;

to

int j = i + 1;

that it works. I understand why it works when j is changed. However, why with j = 0 the code is not working is beyond my understanding. Why is the break statement not working?

P. S. Here is the Python code where break works with a similar logic and for the same input -

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] + nums[j] == target and i - j != 0:
                    return [i, j]
                    break
                else:
                    continue

The `break` only breaks from the innermost loop. That's the way it is specified. — Peter, May 22 '21 at 06:08

score 1 · Answer 1 · answered May 22 '21 at 05:51

1

This is because the break only break the inside for loop but not the outside for loop.

answered May 22 '21 at 05:51

Felix Du

105
6

rawrex · Answer 2 · 2021-05-22T06:14:49.187

1

We can say, that your program is looking for permutations not combinations of two numbers that make up the targeted sum. Note, that nums[1] + nums[2] = target, so as nums[2] + nums[1] = target, which is what you getting in the returned vector.

Yes, this is because the break statement breaks only out of the inner for, while on some next iteration in the outer for you'll get another permutation which sums up to the targeted number.

A quick fix can be addition of a flag variable, like the following:

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        bool flag = 0;
        std::vector<int> output{};
        for(int i = 0; i < nums.size(); i++){
            if (!flag) // if not found yet, iterate further
            for(int j = 0; j < nums.size(); j++){
                if (nums[i] + nums[j] == target && i - j != 0){
                    output.push_back(i);
                    output.push_back(j);
                    flag = 1;
                    break;
                }
            }
            else break; // else break out of the loop
        }
        return output;
    }
};

edited May 22 '21 at 06:14

answered May 22 '21 at 06:01

rawrex

4,044
2
8
24

This works well. Interestingly break for the python nested loop works well (it exists the whole loop), but the same doesn't hold true for C++. – bimbi May 22 '21 at 14:08
@bimbi that should not be the case, because Python's break is totally C-like in its behavior. Maybe there's some other semantic detail in the Python program that leads to such result. Moreover, it would be quite a loss of control if the break statement would terminate all of the loops its in. – rawrex May 22 '21 at 15:52
I have added my Python code as P. S. to the original question. Interestingly, it breaks 'completely' when fed with a similar input so that the output is `[1,2]` instead of `[1,2,2,1]` like with C++ despite the same logic. – bimbi May 22 '21 at 21:05
@bimbi note, that you Python function returns as soon as it finds any compatible combination of two numbers, whereas the Cpp function was only appending found combination of numbers and then proceeding further (just to meet the permutation of these two). So, the break in Python code is dead code, because it stands after return. The break statement there is never executed at all. – rawrex May 23 '21 at 03:24
Gotcha, so it's the return that was causing the execution to stop in Python and not the break function. Thanks, @rawrex. – bimbi May 25 '21 at 05:08
1

@bimbi, yeah, you even can do the same in the Cpp, like `return {i, j}` – rawrex May 25 '21 at 05:27

Why is 'break;' not working as expected for an if statement inside a nested loop?

2 Answers2