CODEWITHSUNDEEP
javascriptalgorithmmath
TechnoCorner
TechnoCorner

Reputation: 5135

Number of possible triangles given an array of numbers question

I'm trying to find the number of possible triangles that can be formed with set of numbers here:

https://www.geeksforgeeks.org/find-number-of-triangles-possible/

I've written the javaScript version of it. however, I don't really understand one part of the solution:

        // Total number of possible triangles that can  
        // be formed with the two fixed elements is 
        //  k - j - 1.  The two fixed elements are arr[i] 
        // and arr[j].  All elements between arr[j+1]/ to  
        // arr[k-1] can form a triangle with arr[i] and arr[j]. 
        // One is subtracted from k because k is incremented  
        // one extra in above while loop. 
        // k will always be greater than j. If j becomes equal 
        // to k, then above loop will increment k, because arr[k] 
        //  + arr[i] is always greater than arr[k]

Problem:

I still don't get this logic. How did k-j come into the picture?

How is that number of triangles that can be formed with arr[i], arr[j] and arr[k] (with arr[i] < arr[j] < arr[k]) give count as k-j I'm kinda unclear on this part.

Can someone enlighten me?

JS solution for the problem:

var triangleNumber = function(arr) {
       let count = 0, n = arr.length;

    //Sort the array in ascending order.
    arr.sort((a,b) => { return a-b; });

    // Set three pointers, i, j = i+1 and k=i+2
    for(let i=0; i<n-2; i++) {
        let k = i+2;
        for(let j=i+1; j<n; j++) {
            // If sum of two sides > third side
            /* Find the rightmost element which is smaller
				than the sum of two fixed elements
				The important thing to note here is, we use
				the previous value of k. If value of arr[i] +
				arr[j-1] was greater than arr[k], then arr[i] +
				arr[j] must be greater than k, because the
			array is sorted. */
            while (k <n && arr[i] + arr[j] > arr[k]) {
                ++k;
            }

            /* Total number of possible triangles that can be
				formed with the two fixed elements is k - j - 1.
				The two fixed elements are arr[i] and arr[j]. All
				elements between arr[j+1] to arr[k-1] can form a
				triangle with arr[i] and arr[j]. One is subtracted
				from k because k is incremented one extra in above
				while loop. k will always be greater than j. If j
				becomes equal to k, then above loop will increment
				k, because arr[k] + arr[i] is always/ greater than
				arr[k] */
            count += k-j-1;
        }
    }

    return count<0? 0: count;
};

const arr = [2,2,3,4];
console.log(triangleNumber(arr));

Upvotes: 0

Views: 1364

Answers (1)

Barmar
Barmar

Reputation: 780843

There are k-j elements starting from the element after j to element k. All of them are valid third sides of the triangle with arr[i] and arr[j] as the first two sides.

E.g. if the first two sides are arr[2] and arr[4], and the highest k where arr[i] + arr[j] > arr[k] is 10, you can make a triangle with k = 5, 6, 7, 8, 9, or 10. There are 6 indexes there, and 10 - 4 = 6.

Upvotes: 1

Related Questions