A Linear Solution

What follows is another implementation of the has_duplicate_value function that doesn’t rely on nested loops. It’s a bit clever, so let’s first look at how it works and then we’ll see if it’s any more efficient than our first implementation.

Here’s what this function does. It creates an array called existing_numbers, which starts out as an array containing eleven zeroes. We’re ensuring that our array has at least eleven slots so we can keep track of the eleven possible ratings users can leave (0 to 10).

Then we use a loop to check each number in the array. As it encounters each number, it places an arbitrary value (we’ve chosen to use a 1) in the existing_numbers array at the index of the number we’re encountering.

For example, let’s say our input array is [3, 5, 8]. When we encounter the 3, we place a 1 at index 3 of existing_numbers. So the existing_numbers array will now be the rough equivalent of this:

There’s now a 1 at index 3 of existing_numbers, to indicate and remember for the future that we’ve already encountered a 3 in our given array.

When our loop then encounters the 5 from the given array, it adds a 1 to index 5 of existing_numbers:

Finally, when we reach the 8, existing_numbers will now look like this:

Essentially, we’re using the indexes of existing_numbers to remember which numbers from the array we’ve seen so far.

Now, here’s the real trick. Before the code stores a 1 in the appropriate index, it first checks to see whether that index already has a 1 as its value. If it does, this means we’ve already encountered that number, meaning we found a duplicate. If this is the case, we simply return True and cut the function short. If we get to the end of the loop without having returned True, it means there are no duplicates and we return False.

To determine the efficiency of this new algorithm in terms of Big O, we once again need to determine the number of steps the algorithm takes in a worst-case scenario.

Here, the significant type of step is looking at each number and checking whether the value of its index in existing_numbers is a 1:

(In addition to the comparisons, we also make insertions into the existing_numbers array, but we’re considering that kind of step trivial in this analysis. More on this in the next chapter.)

In terms of the worst-case scenario, such a scenario would occur when the array contains no duplicates, in which case our function must complete the entire loop.

This new algorithm appears to make N comparisons for N data elements. This is because there’s only one loop, and it simply iterates for as many numbers as there are in the array. We can test out this theory by tracking the steps in the Python console:

If we run has_duplicate_value([1, 4, 5, 2, 9]) now, we’ll see that the output in the Python console is 5, which is the same as the size of our array. We’d find this to be true across arrays of all sizes. This algorithm, then, is O(N).

We know that O(N) is much faster than O(N²), so by using this second approach, we’ve optimized our has_duplicate_value function significantly. This is a huge speed boost.

(One disadvantage with this new implementation is that this approach will consume more memory than the first approach. Don’t worry about this for now; we’ll discuss this at length in Chapter 19, .)