educative.io

Is the outer loop required for brute force?

Courses
,
#1

Hello.
I’m looking the brute-force solution, and can’t realise why do we need to use outer loop(line 7):
We could use just a variable and one loop, like here:
private static int[] findSum(int[] arr1, int n) {
int i = 0;
for (int j = i + 1; j < arr1.length; j++) {
if (arr1[i] + arr1[j] == n) {
return new int[]{arr1[i], arr1[j]};
}
}
return new int[0];
}

Is it change the time complexity?

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5724822843686912
Lesson: https://www.educative.io/collection/page/5642554087309312/5724822843686912/5747933660053504

#3

Hi @Eug_Tor ,
This approach is based on a brute-force solution that’s why the time complexity is O(n^2). While solution #1 is very intuitive, it is not very time efficient. So in the second solution, there is an efficient approach used by doing sorting first, which gives O(nlogn).