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