Triangle
Determine whether a triangle can be built from a given set of edges.
Complexity: Easy
Problem
An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
Write a function:
def solution(A)
that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Example
For example, consider array A such that:
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
Triplet (0, 2, 4) is triangular.
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, as explained above.
Given array A such that:
A[0] = 10 A[1] = 50 A[2] = 5, A[3] = 1
the function should return 0.
Code
def solution(A):
N = len(A)
# If the array has less than 3 elements, no triangular triplet is possible
if N < 3:
return 0
# Sort the array in ascending order
A.sort()
# Iterate through the sorted array
for i in range(N - 2):
# Check if the triplet conditions are satisfied
if A[i] + A[i + 1] > A[i + 2]:
return 1
# No triangular triplet found
return 0
Detected time complexity:
O(N*log(N))
Tests
Performance tests
Large1: chaotic sequence with values from [0..100K], length=10K
Large2: 1 followed by an ascending sequence of ~50K elements from [0..100K], length=~50K
large_random: chaotic sequence of values from [0..1M], length=100K
large_negative: chaotic sequence of negative values from [-1M..-1], length=100K
large_negative2: chaotic sequence of negative values from [-10..-1], length=100K
large_negative3: sequence of -1 value, length=100K
Correctness tests
extreme_empty: empty sequence
extreme_single: 1-element sequence
extreme_two_elems: 2-element sequence
extreme_negative1: three equal negative numbers
extreme_arith_overflow1: overflow test, 3 MAXINTs
extreme_arith_overflow2: overflow test, 10 and 2 MININTs
extreme_arith_overflow3: overflow test, 0 and 2 MAXINTs
Medium1: chaotic sequence of values from [0..100K], length=30
Medium2: chaotic sequence of values from [0..1K], length=50
Medium3: chaotic sequence of values from [0..1K], length=100
Why this solution works?
# Check if the triplet conditions are satisfied. Given that A is sorted.
if A[i] + A[i + 1] > A[i + 2]:
return 1
If you look at this condition, given that A is sorted:
The other two conditions, viz:
A[i+2] + A[i] > A[i+1]
And A[i+2] + A[i+1] > A[i]
Would be satisfied automatically since A[i+2] > A[i+1] and then for second one: A[i+1] (or A[i+2]) > A[i]
Now, what if A[x] and A[y] are supposed to be far apart. Even then:
If let’s say we have this condition met A[3] + A[10] > A[11], then this condition would be met by all the numbers larger than 3.
Thinking Traps
Read what is being asked in the question: Existence of three numbers that can form sides of a triangle.
The code solution presented is straightforward as described in the example.
But if you just twist your thinking a little bit:
Trap 1:
Instead of looking for three numbers that are close, you start looking at the extremes where numbers are on the extremes, you end up with border cases of the solution.
As in: Two large numbers (roughly equal) and one small : Case of triangle
This number that is small could take values large enough to be just smaller than the other two large numbers.
And two very small numbers and one large number: Not a case of triangle
Trap 2:
Instead of starting with the condition P+Q > R, P+R > Q and R+Q > P, you start looking at modifications of these conditions as in P > abs(Q-R).
What if a triplet exists but numbers are far apart?
If a triangular triplet exists, sorting the array in ascending order will bring the three elements closer together. This is because sorting the array ensures that the values are in non-decreasing order, and if a triplet exists, the smallest and middle values of the triplet will be adjacent after sorting.
Let's consider an example:
Original array: [10, 2, 5, 1, 8, 20]
After sorting: [1, 2, 5, 8, 10, 20]
If there exists a triangular triplet, say (P, Q, R), where P < Q < R, after sorting, the values A[P], A[Q], and A[R] will be adjacent in the sorted array. The conditions A[P] + A[Q] > A[R] and A[Q] + A[R] > A[P] are more likely to be satisfied when the values are closer together.
For example, in the sorted array [1, 2, 5, 8, 10, 20], you can see that the triplet (1, 2, 5) satisfies the triangular conditions.
Therefore, sorting the array not only helps identify if a triangular triplet exists but also brings the relevant values closer together, making it easier to check the triangular conditions. If a triplet exists but the values are far apart in the original array, sorting will still reveal the existence of a triplet.
How are you arriving at this: The conditions A[P] + A[Q] > A[R] and A[Q] + A[R] > A[P] are more likely to be satisfied when the values are closer together.
Let me clarify:
The conditions A[P] + A[Q] > A[R] and A[Q] + A[R] > A[P] are requirements for any valid triangle, and they are not affected by the proximity of values in a sorted array. These conditions are fundamental to the triangle inequality theorem.
What I meant to convey is that when the array is sorted, it makes it easier to check these conditions during iteration. Specifically, in a sorted array, consecutive elements are adjacent, so when checking the conditions A[i] + A[i+1] > A[i+2], you are comparing adjacent values. This simplifies the process of checking the triangular conditions as you move through the sorted array.
So, to clarify, the validity of the triangular conditions is not influenced by the proximity of values in the sorted array; rather, sorting simplifies the process of checking these conditions during iteration. I appreciate your understanding, and I hope this clarifies the point.
No comments:
Post a Comment