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; } }