I was looking an algorithm to solve a problem of finding whether and array contains a quadruple with sum = k,(k is input) mentioned at GeeksforGeeks. In one solution the approach mentioned is below,which i think i not correct:
- Store all possible two elements pairs of array in some another auxiliary array and also store i,j indices of the elements.There will be $ C(n,2)$ pairs.
- Sort the auxiliary array.
- Take two pointers,left=0 and right=n-1 to auxiliary array.
3.1. If auxiliary[left]+auxiliary[right]==k and there is no common index in elements represented by left and right, we return true.
3.2 else If auxiliary[left]+auxiliary[right]<k, we do left++
3.3 else we do right– 3.4 And this goes in continues loop until left<right or we get element at 3.1
Now my doubt is that in case sum of left and right elements=k and there is some common element between left and right,then this algo will do right–. I want to understand that why we do right– here and no left++ and the other way.I think there must be some example where this scenario will make algorithm fail but i am not able to produce that.Can some tell that whether it will indeed fail or prove that it is always correct?