explained java solutions
upvote if it helped\nask any query if u got\n--------------from naive to best solution---------------------------------\n\nNaive approach\n\n check for all comb
**upvote if it helped**\nask any query if u got\n**--------------from naive to best solution---------------------------------**\n\n**Naive approach**\n\n* check for all combinations of 3 elements, whether it forms a triangle or not, and update the maximum perimeter if it forms a triangle. The complexity of the naive solution is O(n3). Below is the code for it. *\n\n**------------------------------------------------------------------------------------------CODE------------------------------------------------------------------------------------**\n```\nclass Solution {\n    public int largestPerimeter(int[] nums) {\n        if(nums.length==3){\n            if(nums[0]<nums[1]+nums[2] && nums[1]<nums[0]+nums[2] && nums[2]<nums[1]+nums[0])\n                return nums[0]+nums[1]+nums[2];\n            else\n                return 0;\n        }\n        int n = nums.length;\n        int max = 0;\n        for (int i = 0; i < n - 2; i++)\n        {\n            for (int j = i + 1; j < n - 1; j++)\n            {\n                for (int k = j + 1; k < n; k++)\n                {\n                    int a = nums[i];\n                    int b = nums[j];\n                    int c = nums[k];\n                    if (a < b+c && b < c+a && c < a+b)\n                        max = Math.max(max, a+b+c);\n                }\n            }\n        }\n        if(max>0)\n            return max;\n        return 0;\n    }\n}\n```\n\n**Approach for the efficient solution**\n\n*First, we can sort the array in non-increasing order. So, the first element will be the maximum and the last will be the minimum. Now if the first 3 elements of this sorted array form a triangle, then it will be the maximum perimeter triangle, as for all other combinations the sum of elements(i.e. the perimeter of that triangle) will be = b >= c). a, b,c can not form a triangle, so a >= b + c. As, b and c = c+d (if we drop b and take d) or a >= b+d (if we drop c and take d). So, we have to drop a and pick up d. \n\nAgain, the same set of analysis for b, c, and d. We can continue this till end and whenever we find a triangle forming a triple, then we can stop checking, as this triple gives a maximum perimeter. \n\nHence, if arr[i] < arr[i+1] + arr[i+2] (0 <= i <= n-3)in the sorted array, then arr[i], arr[i+1] and arr[i+2] form a triangle. *\n\n**------------------------------------------------------------------------------------------CODE------------------------------------------------------------------------------------**\n\n```\nclass Solution {\n    public int largestPerimeter(int[] nums) {\n\tif(nums.length==3){\n            if(nums[0]<nums[1]+nums[2] && nums[1]<nums[0]+nums[2] && nums[2]<nums[1]+nums[0])\n                return nums[0]+nums[1]+nums[2];\n            else\n                return 0;\n        }\n        Arrays.sort(nums);\n        int max = 0;\n        for(int i=nums.length-1;i>=2;i--){\n            if(nums[i]<nums[i-1]+nums[i-2]){\n                max = Math.max(max, nums[i]+nums[i-1]+nums[i-2]);\n                break;\n            }\n        }\n        if(max>0)\n            return max;\n        return 0;\n    }\n}\n```\n\nTime complexity: O(n*log(n)). This much time is required to sort the array.\nSpace complexity: O(1) since constant space is used.\n\n**Even better solution(1ms solution)**\n*Without explicit sorting, we can do it this way too*\n\n```\nclass Solution {\n    public int largestPerimeter(int[] nums) {\n        //if array has only 3 elements\n        if(nums.length==3){\n            if(nums[0]<nums[1]+nums[2] && nums[1]<nums[0]+nums[2] && nums[2]<nums[1]+nums[0])\n                return nums[0]+nums[1]+nums[2];\n            else\n                return 0;\n        }\n        //for more than 3 elements, without doing explicit sorting\n        int n = nums.length;\n        //here we are putting max element at last index\n        swapToGetMax(nums, n-1);\n        //here we are putting max element at second last index\n        swapToGetMax(nums, n-2);\n        //here we are putting max element at third last index\n        swapToGetMax(nums, n-3);\n        //in loop checking if nums[i]<nums[i-1]+nums[i-2] which this triplet will form the max perimeter\n        for(int i=n-1;i>=2;i--){\n            if(nums[i]<nums[i-1]+nums[i-2])\n                return nums[i]+nums[i-1]+nums[i-2];\n            //if not then will find max element as (i-3)th largest element\n            else if(i>2)\n                swapToGetMax(nums, i-3);\n        }\n        return 0;\n    }\n    \n    //utility method to get max element at given index\n    private void swapToGetMax(int[] nums, int index){\n        int max=0, maxIndex=-1;\n        for(int i=0;i<=index;i++)\n            if(max<nums[i]){\n                max=nums[i];\n                maxIndex=i;\n            }\n        //actual awapping after finding max element in given range\n        int temp = nums[index];\n        nums[index] = max;\n        nums[maxIndex] = temp;\n    }\n}\n```
['Java']