Algorithm Puzzle: Triplets in Array
Source: Asked to me by Anuj Jain (EE IITB 2010 Graduate, MFE Student at Baruch College NY)
Problem:
Given an array of n integers, find an algorithm to find triplets in the array such that sum of the three numbers is zero.
Problem:
Given an array of n integers, find an algorithm to find triplets in the array such that sum of the three numbers is zero.
What is the order of your algorithm? Make sure its quadratic in size of array. :-)
Solution:
Highlight the part between the * symbols for the answer.
* O(n^2) algorithm: sort the array (O(n log n)). For each i from 1 to n, look for a pair (j, k) with i < j < k and a[j] + a[k] = -a[i] using two pointers: set j = i+1, k = n; if a[j] + a[k] equals the target, record the triplet and move both; if the sum is too small, j++; if too big, k--. Each pair-search is O(n) because the pointers only move toward each other, so the total is O(n^2) plus the one-time sort.
Correctness: when a[j] + a[k] < target, no k' < k can work with this j (the array is sorted, sums only get smaller), so k is never needed again - and symmetrically for j - so no valid pair is skipped.
Solution by Piyush (and independently Abhimanyu Mongandh Ambalath) from the comments. *
Have a solution in quadratic time and linear extra space:
ReplyDeleteStep 1: Sort the array - O(n^2) time
Step 2: Find the largest negative number in the array (there has to be one for such a triplet to exist) - O(log n) time
Step 3: Iterate over the negative numbers like this:
For every negative number k, look for existence of two numbers whose difference is -k.
To do this, subtract n from every integer in array and copy to second array. Now do a pass over both arrays similar to a pass done while merging two sorted arrays.
In this way we can get two numbers whose difference is -k in 0(n) time and O(n) space. And we do this for every negative number. So total order is O(n^2)...
Hence total time is O(n^2) and space is O(n).
Btw we can easily forgo O(n) space as well, just by remembering to add k to numbers in second array while comparing...
sort the array; O(nlogn)
ReplyDeletenow for i = 1,2..N
find a(j) and a(k) (j,k >i) such that a(j)+a(k)=-a(i)
this can be done in O(n) time as follows
let y = -a(i)
j = (i+1)
k = (n)
if y = a(j)+a(k) return (j,k);
if y> a(j)+a(k) j=j+1;
if y< a(j)+a(k) k = k-1;
if j=k return not found; try next i i=i+1;
Create 2 arrays from the input Array
ReplyDeleteA with all elements >= 0
B with all elements < 0 [n]
Sort both the arrays (merge-sort) [WorstCase: 2n.log(n)]
//A is sorted in decending order, B in Asscending
i=0, j=0
while(i < A.length && j < B.length)
{
if (A[i] > -B[j])
{
Let X = -A[i] -B[j]
Search for X in Array B. (binary search, B is sorted) [log(n)]
if (X is found at index k)
print(A[i],B[j],B[k]);
i++;
}
else
{
Let X = -A[i] +B[j]
Search for X in Array A. (binary search, A is sorted) [log(n)]
if (X is found at index k)
print(A[i],B[j],A[k]);
j++;
}
}
//the total complexity of above while loop [n.log(n)]
============================================
time complexity slightly greater than 3n.log(n) + n
Sort the elements,in O(nlogn) time, in increasing order.
ReplyDeleteLet sum be S=0.
For each element in the array A_i (for i from 1 to N)
Compute S' = -A_i.
left = i+1
right = n
while(leftS') \\Means you need to reduce the number.
right--
else
left++
end while
end for
The while loop takes only O(n) time.
This can be seen by understanding that if a certain number can form a triplet, it will NOT be skipped.
and since each step, left and right comes closer by 1 the order is O(n)
setofTriplets = []
ReplyDeletedef findTriplets(array):
global setofTriplets
array.sort()
for i in range(len(array)):
for j in reversed(range(len(array))):
if array[i]<0 and array[j]>=0:
sum = array[i]+array[j]
needToFind = -1 * (array[i] + array[j])
if needToFind in array:
ans = [array[i], array[j], needToFind]
setofTriplets.append(ans)
findTriplets([-9, -4, -3, -1, 0, 1, 2, 6, 7, 8])
print setofTriplets
Correct - and the difference formulation is a nice twist on the standard sum formulation. (Minor: sorting is O(n log n), so your total is O(n^2) dominated by the per-negative-number merge pass.) The more common version is Piyush's below: for each a(i), two-pointer search for a(j) + a(k) = -a(i) in the sorted tail. (replied using AI)
ReplyDeleteThis is the canonical O(n^2) solution - sort, then for each i run the two-pointer scan on the subarray to the right. Correct and optimal for the comparison model. (For finding ALL triplets rather than one, add dedup handling.) (replied using AI)
ReplyDeleteWorks, but the inner binary searches make it O(n^2 log n) overall. You can drop the log factor: replace each binary search by the two-pointer scan of Piyush's comment, keeping O(n) per outer element. The positive/negative split is a fine alternative framing though. (replied using AI)
ReplyDeleteCorrect - the standard solution. The invariant for why skipped elements are safe: on the sorted array, if A[left] + A[right] < -A[i], no partner for A[left] exists at or before right, so left++ loses nothing; symmetric for right--. O(n^2) total. (replied using AI)
ReplyDeleteTwo bugs to fix: (1) `needToFind in array` can reuse one of the two elements you already picked (e.g. array [0, 0, 0] aside, for i and j with needToFind equal to array[i] at a different index it is fine, but if the only occurrence is index i itself, you get a false triplet) - you need an index-aware membership check; (2) the same triplet gets reported many times - sort-and-skip duplicates, or emit sorted triples into a set. Complexity is O(n^2 log n) after the membership check is made binary-search. (replied using AI)
ReplyDelete