CODEWITHSUNDEEP
javaalgorithmtime-complexity
david
david

Reputation: 3218

Difference using for and while in solving the total number of possible triangles

I have encountered this problem in Codility. See this link. I managed to solved this problem. However, this leaves me some question.

Here is the code using three for.

public int solution(int[] A) {
    Arrays.sort(A);
    int k, count = 0;
    for (int i = 0; i < A.length - 2; i++){
        for (int j = i + 1; j < A.length - 1; j++){
            for (k = j + 1; k < A.length; k++){
                if (A[i] + A[j] > A[k]) break;
            count += k - j - 1;
        }
    }
    return count;
}

This is the code using while in the innermost for.

public int solution(int[] A) {
    // write your code in Java SE 8
    Arrays.sort(A);
    int k, count = 0;
    for (int i = 0; i < A.length - 2; i++){
        k = i + 2;
        for (int j = i + 1; j < A.length; j++){
            while (k < A.length && A[i] + A[j] > A[k]) {
                k++;
            }
            count += k - j - 1;
        }
    }
    return count;
}

The first solution above doesn't give me perfect score in Codility because it takes so much time to compile in large test case. However, in the second solution using while, I get perfect score. Why this is the case even though I put the triangle checking in both of these two codes above? Does for and while have something to do with these?

I also did read about the time complexity from the second solution. Here is the link. There is a difference in how the k variable is initialized. Does this difference make a huge impact of these two codes' performance?

I am trying to figure out exactly what makes the difference between these two codes.

Upvotes: 1

Views: 114

Answers (2)

BishalG
BishalG

Reputation: 1424

The for loop and while loop have nothing to do with these above solutions. In fact, we can modify second solution to make while loop as for loop like below:

 public int solution(int[] A) {
        Arrays.sort(A);
        int k, count = 0;
        for (int i = 0; i < A.length - 2; i++) {
            k = i + 2;
            for (int j = i + 1; j < A.length; j++) {
                for( ; k < A.length; k++) {
                    if ( (A[i] + A[j]) <= A[k]) break;
                }
                count += k - j - 1;
            }
        }
        return count;
    }

Actually, The main logic behind your two solutions are totally different.

In first solution:
We are fixing every possible triples using three for loops and breaking third loop as soon as the summation of first two smallest length pairs are less than or equal to that of third one i.e it should be "if (A[i] + A[j] <= A[k]) break;". So, overall time complexity will be O(n^3).

In second solution:
We are only fixing two for loops and performing calculations. The while loop in your code runs only once for every for loop using i. Since the array was sorted once, the idea behind this solution is that if we pair up two values using first two for loops, and summation of values at index i and j is sum i.e sum = A[i] + A[j] and if it encounters a value at index k which is greater than or equal to sum then for next pair i and j + 1, the third index will be definitely greater than previous k since value at index j + 1 is larger than value at index j i.e A[j] <= A[j + 1]. So, the third index should be definitely in right side than that of previous k. So, overall complexity of second solution is O(n^2).

Upvotes: 1

vxst
vxst

Reputation: 79

In the second solution, the k will never reduce in the second layer of loop.

So the first solution's time complexity is O(n^3), while the second solution's time complexity is O(n^2),

Upvotes: 0

Related Questions