How to know that a triangle triple exists in our array?

Question

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?

He is mentioning the index numbers as the answer ... 10 , 5 , 8 — user506710
– user506710, Commented 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. — Ray Suelzer
– Ray Suelzer, Commented Dec 27, 2014 at 2:08
I once saw a variation of this, that is to find the triplet with minimum perimeter, for that, I assume double for loop then binary search for the last is the only optimal option. — PkDrew
– PkDrew, Commented Oct 30, 2024 at 9:45

Vlad · Accepted Answer · 2014-11-26 16:25:19Z

66

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.

edited Nov 26, 2014 at 16:25

answered Mar 22, 2011 at 12:38

Vlad

35.7k7 gold badges82 silver badges205 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

useless Over a year ago

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.

Vlad Over a year ago

@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.

macemers Over a year ago

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)

Vlad Over a year ago

@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?

Chan Le Over a year ago

"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] ...

|

macemers · Accepted Answer · 2014-02-06 13:28:45Z

6

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;

}

answered Feb 6, 2014 at 13:28

macemers

2,2226 gold badges42 silver badges56 bronze badges

3 Comments

Ray Suelzer Over a year ago

This fails the codility test, remember P < Q < R refers to the index number, sorting destroys the index,

async Over a year ago

@RaySuelzer What are you talking about? The n*logn complexity requirement screams at you to sort

Maria Ines Parnisari Over a year ago

@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..

Stphane · Accepted Answer · 2019-07-01 09:52:29Z

4

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

edited Jul 1, 2019 at 9:52

Stphane

3,4765 gold badges36 silver badges49 bronze badges

answered Jul 1, 2019 at 9:34

Amrit Malla

3061 silver badge8 bronze badges

Comments

gd1 · Accepted Answer · 2014-01-08 19:22:43Z

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;

}

answered Jan 8, 2014 at 19:22

gd1

11.4k7 gold badges52 silver badges88 bronze badges

Comments

zs2020 · Accepted Answer · 2011-03-22 12:36:52Z

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).

answered Mar 22, 2011 at 12:36

zs2020

54.6k30 gold badges157 silver badges223 bronze badges

1 Comment

all_by_grace Over a year ago

Yeah, I have tried this previously. And still got a timeout error :-) It expects a better solution than n^2 log(n).

Oleksandr M. · Accepted Answer · 2014-02-19 16:52:25Z

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

answered Feb 19, 2014 at 16:52

Oleksandr M.

6738 silver badges7 bronze badges

1 Comment

Oleksandr M. Over a year ago

and the triangle one: rationalplanet.com/php-related/…

thecheech · Accepted Answer · 2014-04-27 14:04:04Z

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)

answered Apr 27, 2014 at 14:04

thecheech

2,2115 gold badges20 silver badges25 bronze badges

Comments

V Malhi · Accepted Answer · 2015-06-20 07:50:53Z

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

answered Jun 20, 2015 at 7:50

V Malhi

176 bronze badges

1 Comment

V Malhi Over a year ago

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.

Reza Haghighi · Accepted Answer · 2016-01-07 22:51:40Z

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

answered Jan 7, 2016 at 22:51

Reza Haghighi

153 bronze badges

Comments

Andrew · Accepted Answer · 2016-04-10 20:37:21Z

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

edited Apr 10, 2016 at 20:37

answered Apr 10, 2016 at 20:20

Andrew

12 bronze badges

Comments

Maria Ines Parnisari · Accepted Answer · 2016-04-13 21:28:33Z

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

Remario · Accepted Answer · 2017-09-27 00:35:20Z

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.

Nazariy Vlizlo · Accepted Answer · 2024-09-09 18:46:11Z

0

100% Swift solution:

public func solution(_ A : inout [Int]) -> Int {
    guard A.count > 2 else { return 0 }
    A.sort()

    for i in 2..<A.count {
        if A[i - 2] + A[i - 1] > A[i] {
            return 1
        }
    }
    return 0
}

answered Sep 9, 2024 at 18:46

Nazariy Vlizlo

9979 silver badges17 bronze badges

Comments

R Francky · Accepted Answer · 2012-10-22 12:17:28Z

-1

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

answered Oct 22, 2012 at 12:17

R Francky

393 bronze badges

1 Comment

user184968 Over a year ago

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.

Collectives™ on Stack Overflow

How to know that a triangle triple exists in our array?

14 Answers 14

12 Comments

3 Comments

Comments

Comments

1 Comment

1 Comment

Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

14 Answers 14

12 Comments

3 Comments

Comments

Comments

1 Comment

1 Comment

Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related