Next Biggest Number

Daily Coding Problem 21

Welcome with another problem to solve! Today we are dealing with arrays and array manipulations, to find the next biggest number given a fixed array index. As always, before starting, two disclaimers:

• These problems are provided by the wonderful newsletter Daily Coding Problem, which you can subscribe to here. Check it out and try to solve your challenges too!
• I’m not an expert programmer: just a guy who likes to share his shots! If you happen to have a better or faster solution for an algorithm, please submit it in the comments! I’d love to learn some more about this!

Let’s jump to the problem!

The problem

Today’s problem is pretty straight forward:

Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

For example, given [4, 1, 3, 5, 6] and index 0, you should return 3.

If two distances to larger numbers are the equal, then return any one of them. If the array at i doesn't have a nearest larger integer, then return null.

Follow-up: If you can preprocess the array, can you do this in constant time?

Basically, we are given an array and an index of that array. What we are asked to do is to find the next biggest value from that index. In the example above, the given index is 0, which corresponds to the value 4. So the next biggest number in the array is 5, contained at index 3.

Next, we are asked another question: what would happen if we could preprocess the array? Would it be possible to solve the problem in constant time?

Let’s try solving it first then. We’ll use Python this time!

The code

This time there will be no math, just a big bunch of code which we’ll walk step by step. Here’s the algorithm:

I divided the task in four parts, to keep the algorithm more understandable and readable. As before, I also tried to avoid using Python’s built in function and objects (like the enumerate function, which we could have used basically at each for loop), keeping the code portable to other languages and “bare bones” enough to better follow the logic behind it.

Step 1: Finding values bigger than the index

def findNextBiggest (array, index):
    biggerNumbers = []
    for n in range(len(array)):
        if array[n] > array[index]:
            biggerNumbers.append(n)
    if len(biggerNumbers) == 0:
            return None

The first part, simply focuses on collecting the indices of the values in the array which are greater than the value contained by the given index, storing them in biggerNumbers. This way, we can simply get rid of all the values which are not bigger than the target, simplifying the rest of the process. We collect indices because at the end we must return an index: it would be useless to collect directly the values!

After that, we simply check the length of biggerNumbers : if it is 0, there are no values in the starting array which are greater than the one contained by the starting index. We can return None and the algorithm stops.

Step 2: finding the least bigger number

    minimum = biggerNumbers[0]
    for n in biggerNumbers:
        if array[n] < array[minimum]:
            minimum = n

We now have a variable, biggerNumbers , which contains all the values greater than the starting one. We can now understand which index or indices between these contains the lowest value, which must be the next biggest number after our starting index value. We simply do this by setting a new variable, minimum , to the first value of biggerNumbers , and then looping over the indices of this last one. When we find a value which is smaller than array[minimum] , we swap the value of minimum with this last one found.

After the process, the variable minimum will contain the index or indices of the lowest value between the elements of biggerNumbers.

Step 3: Collecting all the occurrences

occurrences = []
    for n in range(len(array)):
        if array[n] == array[minimum]:
            occurrences.append(n)

If we now call array[minimum] we should correctly obtain the next biggest number after the starting index values. The problem is that there could be more than one occurrence of this number in the array. Since the previous part checks only for array[n] strictly minor of array[minimum] , we are now left with the first occurrence of this value between those in the array.

Luckily, we can easily collect all the other occurrences by checking each index of the starting array: if the value is the same, we append its index in the occurrences variable.

After this process, occurrences will contain all the indices of the values in the staring array which are equal to array[minimum] .

Step 4: Finding the nearest occurrence

    nearest = occurrences[0]
    for n in occurrences:
        if abs(index-n) < abs(index-nearest):
            nearest = n
    return nearest

Finally, we need to check which of the occurrences is the nearest to our target index. This is pretty easy though, since we have an array of indices we can compare with our starting index. We start by creating a new variable, nearest , which will keep track of the nearest occurrence, initially equal to the first index contained by occurrences . Next we loop over occurrences and check the distance between:

• the occurrence we are on and the starting index, with abs(index — n)
• the occurrence we temporary stored as nearest and the starting index, with abs(index-nearest)

The smallest one, will be our new nearest until the end, when we can return nearest as the nearest index of the least big number after the one in the initial array. And that’s it!

Before moving on to time complexity, I’d like to point out that this hardly is the best solution for this algorithm: the code is quite big and messy and I’m pretty sure that there are many ways to improve it. If you want to try out, please let me know how you would solve it!

Time complexity

Even though this is quite a bunch of code for a single algorithm, the time complexity keeps still at O(n), meaning the algorithm will complete in the worst case in linear time. This is because the algorithm revolves around the size of the instance of array given as parameter in the function. After that, that array can only decrease in size, at least to a length equal to its size minus one. Besides that, the algorithm never uses inner loops: this means that no matter how many for loops we run, they will always run on an array size of len(array)-1 , except the first one which runs in a size of len(array) .

Preprocessing the array

What about preprocessing the array then? Would it be possible to solve this in constant time?

Preprocessing the array is another way of saying “manipulating the array”, in a way that we can work easily with the result. For example, reordering the array from the lowest to the biggest number would be a huge help in solving this problem. Take the array given as example: [4, 1, 3, 5, 6] . The result of its reordering would be 1,3,4,5,6 . At that point we simply need to return the index after the given one to obtain our 5, solving it in costant time.

Even if the array contains multiple occurrences, like 4,1,5,3,5,6,5 , by reordering it we would obtain 1,3,4,5,5,5,6 . Then we could jump straight to step 4 to get the nearest occurrence of 5 and we would already solved the problem! Also, if we initially reorder the array and then order the occurrences by their distance, we could return index + 1 as result, solving it in constant time.

Reordering though it’s not a easy operation: there are many ordering algorithms, some more efficient than others, but none of them is trivial enough to briefly explain it on this article. If you want to try applying one of them and try to solve this in O(1) time, please go on and share your result with me!

Conclusions

That’s it! As always, I hope you enjoyed the article and found it useful: if so, please leave a clap or two and share it with someone who could find this interesting too!

As always, a big thanks for reading

Nicola