Triangle: Determine if an array includes a triangular triplet (Codility)

My solution in Java with 100/100 and time complexity of O(N*log(N))

With comments explaining the logic

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

    int N = A.length;
    if (N < 3) return 0;
    Arrays.sort(A);

    for (int i = 0; i < N - 2; i++) {

        /**
         * Since the array is sorted A[i + 2] is always greater or equal to previous values
         * So A[i + 2] + A[i] > A[i + 1] ALWAYS
         * As well ass A[i + 2] + A[i + 1] > A[i] ALWAYS
         * Therefore no need to check those. We only need to check if A[i] + A[i + 1] > A[i + 2]?
         * Since in case of A[i] + A[i + 1] > MAXINT the code would strike an overflow (ie the result will be greater than allowed integer limit)
         * We'll modify the formula to an equivalent A[i] > A[i + 2] - A[i + 1]
         * And inspect it there
         */
        if (A[i] >= 0 && A[i] > A[i + 2] - A[i + 1]) {

            return 1;
        }
    }

    return 0;
}

Basically when you check X + Y value of integers, that is greater than integer limit the code will fail on overflow. so instead of checking if X + Y > Z, we can simply check the equivalent statement if X > Z - Y (simple math isn't it?). Alternatively you could always use long but it will be a worse solution memory wise.

Also make sure you skip the negatives as a triangle cannot have a negative side value.

Cheers

Here's my clean solution in Python. I got a 100% in Codility. This logic can be adapted to any other programming language.

Note: If the array is sorted, you only have to check that the sum of two consecutive elements is greater than the next element (A[i] + A[i+1] > A[i+2]), because in that case, the other two conditions (A[i+1]+A[i+2] > A[i], A[i]+A[i+2] > A[i+1]) will always be true.

I hope it helps.

def solution(A):

    #edge case check
    if len(A) < 3:
        return 0

    A.sort()
    for i in range(len(A)-2):
        if A[i]+A[i+1] > A[i+2]:
            return 1
    return 0

I have used 3 for loop here( without sorting the array) to solve this problem.

public static int solution(int[] A) {

    for (int p = 0; p < A.length; p++) {
        for (int q = p + 1; q < A.length; q++) {
            for (int r = q + 1; r < A.length; r++) {

                if ((A[p] + A[q] > A[r]) && (A[q] + A[r] > A[p]) && (A[r] + A[p] > A[q])) {
                    System.out.println(A[p] + "  " + A[q] + " " + A[r]);
                    return 1;
                }
            }
        }
    }
    return 0;
}

the trick is to find a number on the array that is less the sum of the other two on the array so sorting the array then searching for that number will solve it. casting to long that on sometimes the value of summation wil exceed the allowed integer

public int solution(int[] A) {
       int n = A.length;
       if(n<3){
           return 0;
       }
       Arrays.sort(A);
       for(int i=2; i<n; i++){
           if(A[i]<(long)A[i-1]+(long)A[i-2])
           return 1;
       }
       return 0;
    }

My solution in C# with 100 score.

    using System;
    
    class Solution {
        public int solution(int[] A) {
            // write your code in C# 6.0 with .NET 4.5 (Mono)
            if(A.Length) <3)
               return 0;

            Array.Sort(A);
            int p,q,r;
            for(int i=A.Length-1;i>1; i--){
                p = A[i];
                q = A[i-1];
                r = A[i-2];
                if(p+q>r && q+r > p && r+p > q)
                    return 1;
            }
            return 0;
        }
    }

Straightforward solution in JavaScript.

Note: I excluded the options where any side could be 0 or less. The rest is the same.

function solution(A) {
    if (A.length < 3) return 0;

    A.sort((a, b) => (a - b));

    for (i = A.length - 1; i >= 0; i--) {
        if (A[i - 2] <= 0) return 0;

        if (
            A[i] + A[i - 1] > A[i - 2] &&
            A[i] + A[i - 2] > A[i - 1] &&
            A[i - 1] + A[i - 2] > A[i]
            ) return 1;
    }
    return 0;
}

javascript 100% on codility

function solution(a) {
if (a.length < 3) {
    return 0;
}

a.sort((a, b) => a - b);

for (let i = 0; i < a.length - 2; i++) {
    if (a[i] + a[i + 1] > a[i + 2]) {
        return 1;
    }
}

return 0;
}

My solution to this problem, written in Swift.

public func Triangle(_ A : inout [Int]) -> Int {

    A.sort()

    for i in 1..<A.count-1 {
        if(A[i] + A[i-1] > A[i+1]) {
            print("Triangle has edges: \(A[i-1]), \(A[i]), \(A[i+1])")
            return 1
        }
    }
    return 0
}

A = [10,2,5,1,8,20]
print("Triangle: ", Triangle(&A))

Or you can change the if clause, like below

if(A[i]>A[i+2]-A[i+1] && A[i+1]>A[i]-A[i+2] && A[i+2]>A[i+1]-A[i])

using subtraction instead of addition.

Works 100%, tested with different scenario's.

I think all the possibilities are not covered above solution Combination with P,Q,R

A[0] = 10, A[1] = 2, A[2] = 5, A[3] = 1, A[4] = 8, A[5] = 20

index combination

0+1>2, 1+2>0, 2+0>1

1+2>3, 2+3>1, 3+1>2

....

These are combinations needed to achieve this problem.

//Triangle
    /**
     * A[P] + A[Q] > A[R],
       A[Q] + A[R] > A[P],
       A[R] + A[P] > A[Q]
     */
    public int triangleSolution(int[] A) {
    int status = 0;
    for(int i=0; i<A.length; i++) {
        int[] B = removeTheElement(A, i);
        for(int j=0; j<B.length; j++) {
            int[] C = removeTheElement(B, j);
            for(int k=0; k<C.length; k++) {
                if((A[i] + B[j] > C[k]) &&
                   (B[j] + C[k] > A[i]) &&
                   (C[k] + A[i] > B[j])) {
                    return 1;
                }
            }
        }
    }
    return status;
}

    // Function to remove the element 
    public int[] removeTheElement(int[] arr, int index) 
    { 
        // Create another array of size one less 
        int[] anotherArray = new int[arr.length - 1]; 

        // Copy the elements except the index 
        // from original array to the other array 
        for (int i = 0, k = 0; i < arr.length; i++) { 

            // if the index is 
            // the removal element index 
            if (i == index) { 
                continue; 
            } 

            // if the index is not 
            // the removal element index 
            anotherArray[k++] = arr[i]; 
        } 

        //Java >8
        //IntStream.range(0, arr.length).filter(i -> i != index).map(i -> arr[i]).toArray();

        return anotherArray;
    }

//My solution in C++ it avoid overflow

inline int Triangle(vector<int> &A) {

    if(A.size() < 3) return 0;
    sort(A.begin(), A.end());
    for(int i = 0; i < (int)A.size() - 2; ++i){
        int P = A[i], Q = A[i + 1], R =A[i + 2];
        if(( R - P - Q < 0) && ( P - Q - R < 0) && (Q - R - P < 0))
           return 1;
    }
    return 0;
}

Ruby 100% solution

def solution(a)
  arr = a.select{|x| x >=0 }.sort
  arr.each_with_index do |p, pi|
    arr[(pi+1)..-1].each_with_index do |q, qi|
      arr[(qi+pi+2)..-1].each do |r|
        break if p+q <=r
        break if p+r <=q
        break if r+q <=p
        return 1
      end
    end
  end
  0
end

It's javascript solution(TC: O(N*log(N)) though, in case you guys want :).

function solution(A) {
    if(A.length<3) return 0;

    A.sort((a,b)=>b - a);

    for(let i = 0,j = i+1;j < A.length-1;j++){
        let p = A[j],q = A[j+1],r = A[i]

        if(r - p > q) i++;
        else if(r - p < q) return 1;
    }

    return 0;
}

Sorting does not work now, It was a bug it was fixed by Codility. Now, I am using this piece of code to get 93%

You can see the results below:

Codility test Results

0 <= P < Q < R < N

 public static int solution(int[] unfilteredArray) {
    int[] array = filterLessThanOneElements(unfilteredArray);

    for(int i = 0; i <= (array.length - 3) ; i++) {
        long p = array[i];
        for(int j = i+1; j <= (array.length - 2); j++) {
            long q = array[j];
            for(int k = j+1; k <= (array.length - 1); k++) {
                long r = array[k];
                if((p + q > r) && (q + r > p) && (r + p > q)) {
                    return 1;
                }
            }
        }
    }

    return 0;
}

// The mose efficient way to remove duplicates
// TIME COMPLEXITY : O(N)
private static int[] filterLessThanOneElements(int[] unfilteredArray) {
    int k = 0;
    for(int i = 0; i < unfilteredArray.length; i++) {
        if(unfilteredArray[i] > 0) {
            unfilteredArray[k++] = unfilteredArray[i];
        }
    }
    return Arrays.copyOfRange(unfilteredArray, 0, k);
}

Simple change: First, you observe that negative integers cannot be part of a triangular triplet. That means you can cast all ints to unsigned int, and there can’t be any overflow anymore.

100/100 JavaScript solution

function solution(A) {
    let l = A.length;
    if (l < 3) {
        return 0;
    }
    A.sort((a, b) => a - b);
    for (let i = 0; i < l - 2; i++) {
        let [p, q, r] = [A[i], A[i + 1], A[i + 2]];
        if (p + q > r && q + r > p && r + p > q) {
            return 1;
        }
    }
    return 0;
}

If you don't want to use Array.sort, the following works with 100% correctness and 100% performance with a complexity that codility detects at O(N*log(N)).

class Solution {
public int solution(int[] A) {
    int ans = 0;
    int p1 = -1;
    int p2 = -1;
    int p1Pos = 0;
    int p2Pos = 1;
    int cur = -1;

    if(A.length > 2){
        p1 = A[0];
        p2 = A[1];

        for(int i = p2Pos + 1; i < A.length; i++){
            if(p1 > p2){
                p2 = A[p1Pos];
                p1 = A[p2Pos];
                A[p2Pos] = p2;
                A[p1Pos] = p1;
            }
            cur = A[i];
            //System.out.println(p1 + " " + p2 + " " + cur);
            if(p1 > -1 && p2 > -1){
                //the test for a triangle
                if (cur > -1 && 
                    ((p1 == p2 && p2 == cur) || 
                    ((p1 + p2 > cur) && (p1 + cur > p2) && ( cur + p2 > p1)))){
                    return 1;
                //bubble sort...sort of
                }else if (p2 > cur){
                    A[p2Pos] = cur;
                    A[i] = p2;
                    if(p1 < cur){
                        p1 = cur;
                        p1Pos = p2Pos;
                    }

                    p2Pos = i;
                
                } else if(cur > -1 
                    &&(p1 + p2 <= cur) ){
                        p2Pos++;
                        p1Pos++;

                        p1=p2;
                        p2=cur;
                }
            }else{
                //find the first two positive numbers
                if((p2 < 0 || p1 < 0) && cur > -1){
                    if(p1 < 0){
                        p1 = cur;
                        p1Pos = i;
                    }else{
                        p2 = A[i];
                        p2Pos = i;
                    }
                }
            }
        }
    }

    return ans;
  }
}

When I was making this I thought that maybe I could solve this while doing a modified Bubble sort. I chose two pivots (p1 and p2), while making sure p2 > p1. As I iterated through the array, I made sure that p2 would bubble up if p2 > cur and that p1 would additionally bubble up if p1 > cur. I Furthermore, I noticed that any combination of three points that have a negative number cannot be a triangle. So I ignored negatives. I also realized that if the array happened to hold three and only maximal integers that I would have an issue. To solve this I tested for p1 == p2 == cur. Admittingly, it might be better to use BigInteger to solve it.

My 100% JavaScript solution with O(N*log(N)) time complexity:

function solution(A) {

    A.sort((a, b) => a - b);
  
    for (let i = 0, len = A.length - 2; i < len; i++) {
        const [P, Q, R] = [A[i], A[i + 1], A[i + 2]];
        if (P + Q > R && Q + R > P && R + P > Q) {
            return 1;
        }
    }
    
    return 0;

}

One would think that sorting the array first will violate the condition 0<=P<Q<R. But the question is does such a triple exist. For the example we find [10,2,5,1,8,20]. After sorting we still find the values 10, 5, and 8 as the triple, but in a different order. A Python 3 solution with 100% score at Codility:

def triangle(A):
n = len(A)
if n < 3:
    return 0
a = list(A)
if 0 not in a:
    a.append(0)
a.sort()
#print(a)
n = len(a)
p_a = a[a.index(0)+1:n]
#print(p_a)
n = len(p_a)
for i in range(n-2):
    p = p_a[i]
    q = p_a[i+1]
    r = p_a[i+2]
    if (p+q>r):
        return (1)
return 0

My java Solution 100/100 Instead of comparing the Addition we compare the subtraction as we can have an Integer.MAX_VALUE an we will be getting corrupted data.

 public static int solution(int[] A) {
    int isATriangle = 0;
    Arrays.sort(A);
    if (A.length >= 3) {
        for (int i = 0; i < A.length - 2; i++) {
            if (A[i] > A[i + 2] - A[i + 1]
                    && A[i + 2] > A[i] - A[i + 1]
                    && A[i + 2] > A[i + 1] - A[i])
                isATriangle = 1;
        }
    }
    return isATriangle;
}