Java 22ms O(n^2) Time O(1) Space with explanation


  • 0
    R
    • In this situation, if the smallest value + the middle one > the largest one ,then it's a triangle, (because a triangle requires the sum of each two sides must be greater than the other one, s+m is the smallest sum in the three sums, if this > the largest side, it'll surely be a triangle), so this problem is equal to three sum problem (find the combinations which sum is larger than a given number)
    • The main idea is to sort the array first(with O(nlogn) time complexity) to decrease the time complexity and go trough the array with two loops in O(n^2) ,so the final is O(n^2), otherwise three loops is O(n^3) which is more than this.
    public class Solution {
        public int triangleNumber(int[] nums) {
            if (nums.length < 3) {
                return 0;
            }
            int count = 0;
            Arrays.sort(nums); // O(nlogn) time
            for (int k = nums.length - 1; k > 1; k--) { // O(n)
                int begin = 0;
                int end = k - 1;
                while (begin < end) { // O(n), O(n^2) in total
                    if (isTriangle(nums[begin], nums[end], nums[k])) { 
                        // if 'begin' match, then all the nums from begin to end match, so there is no need to go through all the numbers
                        count += (to - from);
                        to--;
                    }
                    else {
                        from++;
                    }
                }
            }
            return count;
        }
        
        public boolean isTriangle(int a, int b, int c) {
            return (a + b) > c && (a + c) > b && (b + c) > a;
        }
    }
    

Log in to reply
 

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