29

I was stuck in solving the following interview practice question:
I have to write a function:

int triangle(int[] A);

that given a zero-indexed array A consisting of N integers returns 1 if there exists a triple (P, Q, R) such that 0 < P < Q < R < N.

A[P] + A[Q] > A[R],  
A[Q] + A[R] > A[P],  
A[R] + A[P] > A[Q].

The function should return 0 if such triple does not exist. Assume that 0 < N < 100,000. Assume that each element of the array is an integer in range [-1,000,000..1,000,000].

For example, given array A such that

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

the function should return 1, because the triple (0, 2, 4) fulfills all of the required conditions.

For array A such that

A[0]=10, A[1]=50, A[2]=5, A[3]=1

the function should return 0.

If I do a triple loop, this would be very very slow (complexity: O(n^3)). I am thinking maybe to use to store an extra copy of the array and sort it, and use a binary search for a particular number. But I don't know how to break down this problem.
Any ideas?

4
  • 2
    (0, 2, 4) doesn't fit: 0 + 2 is not > 4.
    – Vlad
    Mar 22, 2011 at 12:32
  • 8
    He is mentioning the index numbers as the answer ... 10 , 5 , 8
    – user506710
    Mar 22, 2011 at 12:33
  • Does the first condition refer to the values of P R Q or the Index? Because, if P < Q < R, than two elements would fail to satisfy this condition. However, on codility, an array of two elements can be a triplet. This does not make sense to me. Dec 27, 2014 at 2:08
  • 1
    How can this be mark as painless?
    – jacktrades
    Nov 19, 2015 at 19:36

13 Answers 13

63

First of all, you can sort your sequence. For the sorted sequence it's enough to check that A[i] + A[j] > A[k] for i < j < k, because A[i] + A[k] > A[k] > A[j] etc., so the other 2 inequalities are automatically true.

(From now on, i < j < k.)

Next, it's enough to check that A[i] + A[j] > A[j+1], because other A[k] are even bigger (so if the inequality holds for some k, it holds for k = j + 1 as well).

Next, it's enough to check that A[j-1] + A[j] > A[j+1], because other A[i] are even smaller (so if inequality holds for some i, it holds for i = j - 1 as well).

So, you have just a linear check: you need to check whether for at least one j A[j-1] + A[j] > A[j+1] holds true.

Altogether O(N log N) {sorting} + O(N) {check} = O(N log N).


Addressing the comment about negative numbers: indeed, this is what I didn't consider in the original solution. Considering the negative numbers doesn't change the solution much, since no negative number can be a part of triangle triple. Indeed, if A[i], A[j] and A[k] form a triangle triple, then A[i] + A[j] > A[k], A[i] + A[k] > A[j], which implies 2 * A[i] + A[j] + A[k] > A[k] + A[j], hence 2 * A[i] > 0, so A[i] > 0 and by symmetry A[j] > 0, A[k] > 0.

This means that we can safely remove negative numbers and zeroes from the sequence, which is done in O(log n) after sorting.

12
  • this is completely wrong. You are supposed to check if a triplet of indexes p, q, r exists for the given array, not an array that you re-sorted.
    – useless
    Mar 30, 2013 at 2:24
  • 4
    @useless: Nope. Obviously if a triple exists in the sorted array, it must exist in the original array (just map the indices back and sort them). You can see that the problem is symmetric w.r.t. index swapping.
    – Vlad
    Apr 17, 2013 at 10:11
  • I don't think it's just O(NlogN). Would you please provide codes to see whether it's O(NlogN) or O(N^3)
    – macemers
    Oct 9, 2013 at 4:03
  • @user838204: sorting is O(N log N), clearly. Linear scan of an array with accessing to the data exactly 3 items on each iteration is clearly O(n). Which part of the algorithm seems suspicious to you?
    – Vlad
    Oct 9, 2013 at 10:18
  • 1
    "it's enough to check that A[i] + A[j] > A[k] for i < j < k, because A[i] + A[k] > A[k]" If A[i] is negative, A[i] + A[k] < A[k] ...
    – Chan Le
    Feb 26, 2014 at 15:14
5

In Java:

public int triangle2(int[] A) {

    if (null == A)
        return 0;
    if (A.length < 3)
        return 0;

    Arrays.sort(A);

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

    return 0;

}
3
  • 2
    This fails the codility test, remember P < Q < R refers to the index number, sorting destroys the index, Dec 27, 2014 at 2:15
  • 3
    @RaySuelzer What are you talking about? The n*logn complexity requirement screams at you to sort
    – async
    Aug 26, 2015 at 17:54
  • 1
    @async Yes, but read the condition again...A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and... etc. When you wrote Arrays.sort(A) you just lost the original indexes.. Apr 13, 2016 at 21:22
2

Here is an implementation of the algorithm proposed by Vlad. The question now requires to avoid overflows, therefore the casts to long long.

#include <algorithm>
#include <vector>

int solution(vector<int>& A) {

    if (A.size() < 3u) return 0;

    sort(A.begin(), A.end());

    for (size_t i = 2; i < A.size(); i++) {
        const long long sum = (long long) A[i - 2] + (long long) A[i - 1];
        if (sum > A[i]) return 1;
    }

    return 0;

}
2

Here's simple solution in java with 100/100 score

class Solution {
  public int solution(int[] A) {
    // write your code in Java SE 8
    Arrays.sort(A);
    for (int i = 0; i < A.length - 2; ++i) {
      long a = A[i] + (long) A[i + 1];
      long b = A[i + 2];
      if (a > b) {
        return 1;
      }
    }
    return 0;
  }
}
1

Do a quick sort first, this will generally take nlogn. And you can omit the third loop by binary search, which can take log(n). So altogether, the complexity is reduced to n^2log(n).

1
  • Yeah, I have tried this previously. And still got a timeout error :-) It expects a better solution than n^2 log(n). Mar 22, 2011 at 12:38
0

In ruby what about

def check_triangle (_array)
  for p in 0 .. _array.length-1
    for q in p .. _array.length-1
      for r in q .. _array.length-1
        return true if _array[p] + _array[q] > _array[r] && _array[p] + _array[r] > _array[q] && _array[r] + _array[q] > _array[p]
      end
    end
  end

  return false
end

Just port it in the language of your choice

1
  • 4
    In the question time complexity is not mentioned but in a real quiestion on Codility there is a requirement that a solution must be O(NlogN) so your solution is not suitable.
    – user184968
    Nov 13, 2013 at 17:20
0

A 100/100 php solution: http://www.rationalplanet.com/php-related/maxproductofthree-demo-task-at-codility-com.html

function solution($A) {
    $cnt = count($A);
    sort($A, SORT_NUMERIC);
    return max($A[0]*$A[1]*$A[$cnt-1], $A[$cnt-1]*$A[$cnt-2]*$A[$cnt-3]);
}
1
0

Python:

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

Sorting: Loglinear complexity O(N log N)

0

I have got another solution to count triangles. Its time complexity is O(N**3) and takes long time to process long arrays.

Private Function solution(A As Integer()) As Integer
    ' write your code in VB.NET 4.0
    Dim result, size, i, j, k As Integer
        size = A.Length
        Array.Sort(A)
        For i = 0 To Size - 3
            j = i + 1
            While j < size
                k = j + 1
                While k < size
                    If A(i) + A(j) > A(k) Then
                        result += 1
                    End If
                    k += 1
                End While
                j += 1
            End While
        Next
        Return result
End Function
1
  • Please have a look on the code above. It gives 100% correctness but 25% performance on codility see at the link : codility.com/demo/results/demoA8XYRV-2ET. Can anyone please suggest me the changes to get 100% performance. Thank you in Advance.
    – V Malhi
    Jun 20, 2015 at 7:52
0

PHP Solution :

function solution($x){
    sort($x);
    if (count($x) < 3) return 0; 
    for($i = 2; $i < count($x); $i++){
        if($x[$i] < $x[$i-1] + $x[$i-2]){
            return 1;
        }
    }

    return 0;
}
0

Reversing the loop from Vlad solution for me seems to be easier to understand.

The equation A[j-1] + A[j] > A[j+1] could be changed to A[k-2]+A[k-1]>A[k]. Explained in words, the sum of the last two largest numbers should be bigger than current largest value being checked (A[k]). If the result of adding the last two largest numbers(A[k-2] and A[k-1]) is not bigger than A[k], we can go to the next iteration of the loop.

In addition, we can add the check for negative numbers that Vlad mentioned, and stop the loop earlier.

int solution(vector<int> &A) {
    sort(A.begin(),A.end());
    for (int k = A.size()-1; k >= 2 && A[k-2] > 0 ; --k) {
        if ( A[k-2]+A[k-1] > A[k] )
            return 1;
    }
    return 0;
}
0

Here's my solution in C#, which gets 90% correctness (the wrong answer is returned for test extreme_arith_overflow1 -overflow test, 3 MAXINTs-) and 100% performance.

private struct Pair
{
    public int Value;
    public int OriginalIndex;
}

private static bool IsTriplet(Pair a, Pair b, Pair c)
{
    if (a.OriginalIndex < b.OriginalIndex && b.OriginalIndex < c.OriginalIndex)
    {
        return ((long)(a.Value + b.Value) > c.Value
                && (long)(b.Value + c.Value) > a.Value
                && (long)(c.Value + a.Value) > b.Value);
    }
    else if (b.OriginalIndex < c.OriginalIndex && c.OriginalIndex < a.OriginalIndex)
    {
        return ((long)(b.Value + c.Value) > a.Value
                    &&(long)(c.Value + a.Value) > b.Value
                    && (long)(a.Value + b.Value) > c.Value);
    }
    // c.OriginalIndex < a.OriginalIndex && a.OriginalIndex < b.OriginalIndex
    return ((long)(c.Value + a.Value) > b.Value
                && (long)(a.Value + b.Value) > c.Value
                && (long)(b.Value + c.Value) > a.Value);
}

public static int Triplets(int[] A)
{
    const int IS_TRIPLET = 1;
    const int IS_NOT_TRIPLET = 0;

    Pair[] copy = new Pair[A.Length];

    // O (N)
    for (var i = 0; i < copy.Length; i++)
    {
        copy[i].Value = A[i];
        copy[i].OriginalIndex = i;
    }

    // O (N log N)
    Array.Sort(copy, (a, b) => a.Value > b.Value ? 1 : (a.Value == b.Value) ? 0 : -1);

    // O (N)
    for (var i = 0; i < copy.Length - 2; i++)
    {
        if (IsTriplet(copy[i], copy[i + 1], copy[i + 2]))
        {
            return IS_TRIPLET;
        }
    }

    return IS_NOT_TRIPLET;
}
0
public static int solution(int[] A) {
    // write your code in Java SE 8
    long p, q, r;
    int isTriangle = 0;

    Arrays.sort(A);
    for (int i = 0; i < A.length; i += 1) {

        if (i + 2 < A.length) {
            p = A[i];
            q = A[i + 1];
            r = A[i + 2];
            if (p >= 0) {
                if (Math.abs(p) + Math.abs(q) > Math.abs(r) && Math.abs(q) + Math.abs(r) > Math.abs(p) && Math.abs(r) + Math.abs(p) > Math.abs(q))
                    return 1;
            }
        } else return 0;


    }

    return isTriangle;

}

The above implementation is Linear in time complexity. The concept is simple use the formaula they gave extracting a series of triplets of sorted elements.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.