Given a target (say, 10) and an array of numbers, we are asked to find if any two numbers in the array add up to 10.

Most beginner programmers (me) would come up with an algorithm that involves a nested loop. We start with the array’s first number, then check it against each successive array element to test whether they add up to 10. If none do, we then take the second array element and perform the same checks. This process continues — first loop establishes an anchor number, second loop checks the anchor against all possibilities — until we’ve either found a match and returned true or we’ve checked and rejected all the possibilities and returned false.

In code:

This nested loop would be considered Big-O of n squared — efficient and therefore undesirable.

So how can we make this more efficient?

Well, if we knew the given array of numbers was sorted we can (potentially, depending on the array elements) achieve Big-O of n by eliminating the need for the nested forloop. Like this:

Line-by-line breakdown:

  • Line 2: initialize pointer variable j to the array length — we will use j to reference array elements starting from the back, or highest numbers.
  • Lines 3–11: for loop starting at the beginning of the array and continuing until the for loop’s counter meets j.
  • Line 4: initialize variable match — the number which, when added to the current array element, equals the given target.
  • Lines 5–10: while loop — when array element pointed to by j(initially set to the array’s highest number) is greater or equal to match
  • Lines 6–8: check if we have a match. If yes return true.
  • Line 9: decrement j.
  • Line 12: for loop has completed with no result, return false.

Overall explanation:

The trick in the more efficient approach is to use a pointer variable then decrement it using a nested while loop rather than nested for loop. Using this approach, we can eliminate the need to check against array elements that are mathematically impossible.

Let’s walk through the execution:

j is set to the amount of array elements so that when we reference j using movieDurations[j] we get the last element in the array, or the highest number since it's a sorted array. On the for loop’s first iteration match equals 9 (10 minus 1, where 1 is the initial array element referenced by movieDurations[i] ) and movieDurations[j] equals 11. 11 satisfies the while condition so we enter the while loop. 11 is not 9, so we don’t return true. Then we decrement j and start from the beginning of the while loop. This time, movieDurations[j] references the next highest element in the array, 8. 8 does not satisfy the while loop’s condition, so we return to the beginning of the for loop. i is incremented to 1, so movieDurations[i] now references 3 and match now equals 7. Moving to the while loop — movieDurations[j] still references 8, which is greater than 7, so we enter the while loop. 8 is not 7, so we decrement j and return to the beginning of the while loop. Now, movieDurations[j] references 7, which satisfies the while loop and is also equal to match, so we return true and finish executing.

So, the while loop helps us determine whether there’s a potential match. If there is a match, great we’re done. If not, we can skip right along to the next for loop iteration without checking array elements we know wont work.

Using this approach, we’ve avoided the need to execute nested for loops which would check each successive array element. Rather, we can target the potential matches by matching up the lowest/earliest elements with the highest/latest elements. Basically, this speeds things up.

If you compare the actual runtimes of the two approaches the difference seems negligible. And it is, given our small array. But what if that array contained 1000s, or 100000s of elements? Then we are talking some serious time-saving.