Java O(n^2) Time O(1) Space


  • 63
    public static int triangleNumber(int[] A) {
        Arrays.sort(A);
        int count = 0, n = A.length;
        for (int i=n-1;i>=2;i--) {
            int l = 0, r = i-1;
            while (l < r) {
                if (A[l] + A[r] > A[i]) {
                    count += r-l;
                    r--;
                }
                else l++;
            }
        }
        return count;
    }
    

  • 0
    N

    @compton_scatter Wow this solution is very clever!


  • 1

    I like your elegant solution! Thank you.


  • 0
    T

    @compton_scatter said in Java O(n^2) Time O(1) Space:

    count += r-l;
    

    Can you please explain why is the r-l being added to the count?
    If you use [2,2,4,5], (2(index 0)+4(index 2)) > 5. Why do you increase the count by 2 rather than 1?


  • 2

    @thallam
    r-l keeps track of number of pairs from r to l that forms a valid triplet (follows triangle inequality property) with the third side represented by i
    In this case -> [2,4] and [2,4] are the two pairs (using first 2 and second 2)


  • 2
    W

    @thallam said in Java O(n^2) Time O(1) Space:

    Can you please explain why is the r-l being added to the count?
    If you use [2,2,4,5], (2(index 0)+4(index 2)) > 5. Why do you increase the count by 2 rather than 1?

    1. The array is sorted.
    2. By (1), the elements at the right side of the first 2 are guaranteed to be larger than or equal to the first 2.
    3. By (2), if the sum of the first 2 and 4 is larger than 5, it implies that the sum of 4 and the numbers to the right of the first 2 is larger than 5.
    4. By (3), you can safely include all pairs between r-l to the solution.

  • 1
    D

    @thallam said in Java O(n^2) Time O(1) Space:

    Can you please explain why is the r-l being added to the count?
    If you use [2,2,4,5], (2(index 0)+4(index 2)) > 5. Why do you increase the count by 2 rather than 1?

    I have a similar solution -

    public class Solution {
    public int triangleNumber(int[] nums) {

       if(nums.length < 3) return 0;
        
        Arrays.sort(nums);
        int hi = nums.length-1, count = 0;
               
        for(; hi > 1; hi--){
            int lo = 0, mid = hi - 1;
            while(lo < mid){
                if(nums[lo] + nums[mid] <= nums[hi])
                    lo++;
                else{
                    count+=mid-lo;
                    mid--;
                }
            }
        }
        
        return count;
    }
    

    }

    The idea is that once we find the combination <lo, mid, hi> such that lo+mid > hi, there is no need to increment lo, for this mid and hi combination, all the lo between lo and mid will satisfy the condition. Hence we just add (mid-lo) to our answer count.


  • 2
    A

    @trollwrlord

    1. Remember, the array is sorted
    2. If the sum of two small elements (at left index and right index) is greater than the rightmost element (largest), then it is obvious that the subsequent sum of pairs will be greater than the rightmost element.
      In your case [2,2,4,5], if (2+4 > 5) then keeping the right index at the same position and increasing the left (the second 2+4 is obviously > 5)
    3. The reason for count+=r-l is to find out how many pairs satisfy this property
      In this case, there are two pairs that satisfy this property (2,4) and (2,4). since the right index is decremented, the count becomes r-l which is 2-0 (2 pairs).
      I had the same doubt and I tried to work with different examples to understand.

  • 0
    K

    @wai_ting Thank you. This is a great explanation.


  • 0

    @wai_ting Nicely explained! Appreciate your help! :)


  • 0
    F

    Almost same with the solution of 3 sum smaller. Thx for sharing.


  • 0
    T

    @compton_scatter
    have someone think about traverse the array from 0 to n-1?
    this solution is i from n-1 to 0, just judge a[low]+a[high] > a[i]. When I first thought is from i from 0 to n-1, low = i+1 ,high = n-1; judge [high] -[low] < [i] ,we get combination
    C(2,low-high+1),but when [high] -[low] > [i] ,i cannot think clearly high-1 or low +1 . [high-1]-[low] and [high]-[low+1] , both are possible less than [i], so i think it become more complex.


Log in to reply
 

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