Apex Coding Challenge for Iterating Lists

Here is the problem statement:

Given an expectedSum value find the sum (n+ (n+1) = expectedValue) from a list that equals the expectedSum. I am using the following list

1,3,4,4,5,9

and looking for the sum to be 8 (3+5, 4+4)

*Note the list is sorted

Solution 1:

        Integer expectedSum = 8;
		List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);
		for (Integer k=0; k<listInts.size();k++){
			for (Integer j=k+1; j<listInts.size();j++){
				if (listInts.get(k)+listInts.get(j)==expectedSum){
					System.debug(listInts.get(k) + ' + ' + listInts.get(j));
				}
			}
		}	

The above time complexity for a nested for loop is O(n^2)

Solution 2:

Do a binary search to search if the diff is contained in the list

		Integer expectedSum = 8;
		List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);
		for (Integer listInt : listInts){ 
			Integer diffInt = expectedSum-listInt;
			if (binarySearch(listInts, diffInt)!=null){
				System.debug(listInt + " + " + diffInt);
			}
		}
	public static Integer binarySearch(List<Integer> listInts, Integer searchInt){
		Integer startPos = 0;
		Integer listSize = listInts.size() - 1;
		Integer mid;
		while(startPos <= listSize){
			mid=(startPos+listSize)/2;
			if(listInts.get(mid) == searchInt){
				 return listInts.get(mid);
			}     
			else if(searchInt < listInts.get(mid)){
				listSize = mid - 1;
			}    
			else{
				startPos = mid + 1;
			}
		}
		return null;	 
	}

the above time complexity for binary search is for each element in the array O(n log n) Returning null is not a good practice try to return another number or throw an exception.

Solution 3:

Check if the diff is contained in the list by using the .contains method

		Integer expectedSum = 8;
		List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);
		for (Integer listInt : listInts){
			Integer diffInt =expectedSum-listInt;
			if (listInts.contains(diffInt)){
				System.debug(listInt + ' + ' + diffInt);
			}
		}

the above time complexity for loop is O(n)

Option 4

Start on either end of the array and move inwards when you find a solution, if the sum of the outer and inner element is bigger that the expectedSum move the maxPointer inwards, if it is smaller move the minPointer inwards.

        Integer expectedSum = 1;
		List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);
		Integer maxPointer = listInts.size()-1;
		Integer minPointer = 0;
		for (Integer k=0; k<listInts.size();k++){
			if (expectedSum < listInts.get(maxPointer)){
				maxPointer-=1;
			} else if (minPointer!=maxPointer){
				Integer sumPair =listInts.get(minPointer) + listInts.get(maxPointer);
				if ( sumPair == expectedSum){
					System.debug(listInts.get(minPointer) + " + " + listInts.get(maxPointer));
					minPointer +=1;
					maxPointer-=1;
				} else if (sumPair < expectedSum){
					minPointer +=1;
				} else {
					maxPointer-=1;;
				}
			}
		}

the above time complexity for loop is O(n)

Output:

4 + 4
5 + 3
3 + 5

Bonus:

How to do it with an unsorted list:

Iterate through the list and add the integer to the list, if the diff of the expected sum and integer is contained in the set then print it

		Integer expectedSum = 8;
		List<Integer> listInts = Arrays.asList(7,4,6,1,5,2,3);
		Set<Integer> intSetWithDiff = new HashSet<>();
		for (Integer listInt : listInts){
			Integer sumDiff = expectedSum - listInt;
			if (intSetWithDiff.contains(sumDiff)){
				System.debug(listInt + " + " + sumDiff);
			}
			intSetWithDiff.add(listInt);		
		}

Output:

1 + 7
2 + 6
3 + 5