Java solution with explanation


  • 0

    Instead of going via brute-force to check every triple for the triangle property (which will be O(n^3)), we first sort the array in ascending order.
    We take two nos in the triple from left to right and then iterate over the other nos from left to right, counting each third no. We stop the iteration as soon as we encounter a no that becomes >= the sum of the first two taken.

    public class Solution {
        public int triangleNumber(int[] nums) {
            int count = 0;
            Arrays.sort(nums);
            for(int i = 0; i <= nums.length - 3; i++) {
                for(int j = i + 1; j <= nums.length - 2; j++) {
                    for(int k = j + 1; k <= nums.length - 1 && nums[i] + nums[j] > nums[k]; k++) {
                        count++;
                    }
                }
            }
            return count;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.