Leetcode 611 Valid Triangle Number - March 9, 2018 mock interview code review as an interviewer, the time complexity is O(n^2).

Leetcode611_ValidTriangleNumber_March9CodeReview.java

import java.io.*;
import java.util.*;

/* 
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


[2,2,3,4]
 i   j k
 
set = {(2,3,4),}  
i = 0
j = 2
k = 3

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

 */

class Solution {
  
  public static void main(String[] args) {
    // int[] arr = new int[]{2, 2, 3, 4};   // 1, 1, 1, 2, 
    // System.out.println(String.format("Expected=%d, found=%d", 3, findCombinations(arr)));
    
    int[] arr = new int[]{1, 1, 1, 2};   // 1, 1, 1, 2, 3, 4
    // 1, 2,   2,   3, 4  2, - Julia explained the two pointer technique alternative design. 
    //   left         right
    //   
    System.out.println(String.format("Expected=%d, found=%d", 1, findCombinations(arr)));    
  }
  
  private static Integer findCombinations(int[] arr) {
  
    if (arr == null || arr.length == 0) return 0;
    
    int num = 0;
    Arrays.sort(arr);
    for (int i = 0; i < arr.length - 2; i++) {
      int j = i + 1;
      int k = arr.length - 1;      
      num += findCombinations(arr, i, j, k);      
    }
    
    return num;
  }
  
  private static int findCombinations(int[] arr, int i, int j, int k) {
    if (j >= k) return 0;
    int num = 0;
    if (arr[i] + arr[j] > arr[k]) {
      System.out.println(String.format("Found combination i=%d, j=%d, k=%d", i, j, k));
          num++;  // design has defect -> not efficient -> n^2 increment -> add range of number/
    } else {
      
    }
    
    num += findCombinations(arr, i, j + 1, k);
    num += findCombinations(arr, i, j, k - 1);
    return num;                          
  }  
}