Saturday, February 6, 2021

611. Valid Triangle Number

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

  1. The length of the given array won't exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

My answer: thought of backtrack in the beginning, didn't think about sorting


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
    private int result = 0;
    public int triangleNumber(int[] nums) {
        // backtrack -- O(n^3) [,aka Cn3]
        // time limit exceeded.
        // List<Integer> singleCombination = new ArrayList<Integer>();
        // helper(nums, 0, singleCombination);
        // return result;
        
        // Solution 2: O(n^2 lg(n))
        // sort, then start with left/right most value,
        // get expected threshold value for triangle,
        // use bs to find the smallest bigger element than threshold

//         int count = 0;
//         Arrays.sort(nums);

//         int l = 0;
//         int r = nums.length - 1;
        
//         for (int i = 0; i < nums.length - 2; i ++) {
//             for (int j = nums.length - 1; j >= i + 2; j --) {
//                 int threshold = nums[j] - nums[i];
//                 // find index of smallest element bigger than threshold
//                 int idx = bs(nums, i, j, threshold);
//                 // if idx == i, meaning threshold is smaller than num[i]
//                 count += idx == i ? j - idx - 1 : j - idx;
//             }
//         }

//         return count;
        
        //Solution 3:
        //sort, start from end, fix it as largest side,
        //find the other 2 sides fromt left elements of end value
        int count = 0;
        Arrays.sort(nums);
        
        for (int k = nums.length - 1; k >= 2; k --) {
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    // count options when j,k is fixed
                    count += j - i;
                    j --;
                } else {
                    i ++;
                }
            }
        }
        return count;
    }
    
    private int bs (int[] nums, int l, int r, int threshold) {
        while (l < r) {
            int m = (l + r)/2;
            if (nums[m] > threshold) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
    
    private void helper(int[] nums, int start, List<Integer> singleCombination) {
        if (singleCombination.size() == 3) {
            if (isValid(singleCombination)) {
                result += 1;
            }
            return;
        }
        
        for (int i = start; i < nums.length; i ++) {
            singleCombination.add(nums[i]);
            helper(nums, i + 1, singleCombination);
            singleCombination.remove(singleCombination.size() - 1);
        }
    }
    
    private boolean isValid(List<Integer> combination) {
        int v0 = combination.get(0);
        int v1 = combination.get(1);
        int v2 = combination.get(2);
        
        if ((v2 + v1 <= v0) || (v2 + v0 <= v1) || (v0 + v1 <= v2) ) {
            return false;
        }
        return true;
    }
}


at

No comments:

Post a Comment