typo: the "for" loop is for (int i : vec) {

To elaborate on vsp's solution. I believe they are looking for the matching pairs in the array that sum to n. Ex: 5,0 4,1 2,3 6,-1 I'd suggest dumping the vector into a hash O(n). Then walk the vector getting i and check the hash for the j where j = sum - i;. When j is in the hash, then you have an ij pair.

Working Answer ... import java.util.ArrayList ; import java.util.HashMap ; public class findpair { public static void main (String [] args) { int [] array = new int [] { 1,6,4,2,6,2,3,4,5,1,6,7,8,3,4 } ; for ( int ii : array) { System.out.print( ii+" " ); } System.out.println(); pairPrint( array, 10 ) ; } private static void pairPrint ( int [] array , int value) { HashMap > map = new HashMap > ( array.length ) ; int counter = 0; for ( int ii : array ) { /// If we find a match we add it and print the pairs if ( map.containsKey(ii) ) { for ( Integer jj : map.get(ii) ) { System.out.println( " Pair at " + counter + " + " + jj ) ; }} // Add it to the map if ( map.containsKey(value-ii) ) { map.get(value-ii).add(counter) ; } else { ArrayList list = new ArrayList(); list.add(counter ); map.put(value-ii , list) ; } counter++ ; } } }

hashtable provide a O(l) time and O(n) memory algorithm which l is length of array

Saw the video on youtube. That example is sorted array. If we solve the problem using unsorted array. It needs some kind of probabilistic model to evaluate the complexity. So I am not going to try that. Let's use a general Quicksort to sort it first. Which average O(n log n) Then we can try to find a pair from the result. There is an extra piece of information which is the specific number "n". Think of the sorted array like a stair shape block. Pseudo Algo: 0. input array X 1. look for the number closest to n/2. 2. Cut this array into two arrays (fold it in half). W[] and Q[] 3. Loop(i=0;i++;i

Sort the array using quick sort. Start from the highest value on top, say x, and binary search the array to see if there exists n-x. If not, remove top element and shrink array by 1 and repeat. If found, there's your solution.