Can Make Triangle Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/51b7f8fb8b33d657a857f230361b7dad6565ce62/1
(It is also the problem of the day for 04-03-2022)
Solution:
1.Using Variables:
class Solution
{
int[] canMakeTriangle(int arr[], int n)
{
int arr1[]=new int[n-2];
PriorityQueue<Integer>pq=new PriorityQueue<Integer>(3);
for(int i=0;i<n-2;i++){
pq.add(arr[i]);
pq.add(arr[i+1]);
pq.add(arr[i+2]);
int a=pq.remove();
int b=pq.remove();
int c=pq.remove();
if((a+b)>c){
arr1[i]=1;
}
else{
arr1[i]=0;
}
}
return arr1;
}
}
-----------------------------------------------------------------------------------------------------------------------------
2.Without Using Variables:
class Solution
{
int[] canMakeTriangle(int arr[], int n)
{
int arr1[]=new int[n-2];
PriorityQueue<Integer>pq=new PriorityQueue<Integer>(3);
for(int i=0;i<n-2;i++){
pq.add(arr[i]);
pq.add(arr[i+1]);
pq.add(arr[i+2]);
if((pq.remove()+pq.remove())>pq.remove()){
arr1[i]=1;
}
else{
arr1[i]=0;
}
}
return arr1;
}
}
-----------------------------------------------------------------------------------------------------------------------------
Time Complexity:O(N)[Array Traversal][GFG Time:0.8/6.3]
Space Complexity:O(1)[Array is given]
Auxiliary Space: O(3)[Constant as Priority Queue is fixed for 3 elements only.]
Total Test Cases:6008
Approach :
We need to see whether we can form a triangle with three sides given.
For checking this we need to check if b+c>a && a+b>c && a+c>b. [Where a, b, c are array elements ar index i , i+1,i+2]
Later we have to returen array of size n-2, Let it be arr1.
If triagle condition is satisfied then at index i of arr1[i] we wil store 1 otherwise 0.
Now since we have to check 3 different condition for valid triangle we can minimise this to one condtion only using priority queue.
eq if a=10 b=20 c=15 then
a+b=30 ,b+c=35 and a+c=25
now
a+b>c ->>>>>>>>>>>>>>>>>>>>>>>>>>>>>true as 30>15
b+c>a >>>>>>>>>>>>>>>>>>>>>>>>>>>>>true as 35>30
a+c>b ->>>>>>>>>>>>>>>>>>>>>>>>>>>>>true as 25>20
Since all 3 conditions are valid it will form a triangle.
But if we have used priority queue then we got:
a=10 b=15 and c=20
Now if we check only one condition ie a+b>c we can directly say it is a valid triangle.
ir a+b --->>>>>>>>>>>>>>>>>>>>> 25>20 ie c So valid.
Another Example
a=10 b=3 c=4
a+b=13 ,b+c=7 and a+c=14
now
a+b>c ->>>>>>>>>>>>>>>>>>>>>>>>>>>>>true as 13>4
b+c>a >>>>>>>>>>>>>>>>>>>>>>>>>>>>>false as 07>10
a+c>b ->>>>>>>>>>>>>>>>>>>>>>>>>>>>>true as 14>3
So b+c!>a Hence it wont form a triangle
And if we have use dpriprity queue then
a=3 b=4 and c=10
a+b!>c ie 7!>10 return false
Hence triangle can't be formed.
Question-:Why Priority Queue is used?
Usage of PriorityQueue helps us in a manner it provides us values in ascending order ie minimum value to the maximum value.
So if the sum of two minimum values is more than the maximum value then definitely triangle will be possible
Otherwise whatever the case we take it won't be.
Because in a triangle in which the sum of two minimum sides is more than the third side then definitely it will be valid and even if we replace one minimum side with maximum side it will also be greater than the other 3rd side.
The benefit Of using a PriorityQueue is also that it does automatically sorting which ultimately does not cost us additional logn time for sorting.
Question: Can we use Set also as it also does automatically sort(TreeSet)?
No. Set also does automatically sorting but it also removes duplicates while we can have the same value for 2 sides. So to preserve those cases we go with PriorityQueue.
"Thanks for Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment