Daily Coding Problem: Next Biggest Number

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 straightforward:

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 that we’ll walk step by step. Here’s the algorithm:

I divided the task into 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 that 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 that are not bigger than the target, simplifying the rest of the process. We collect indices because, in 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 that 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 contain 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 the 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 to 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 temporarily stored as the nearest and the starting index, with abs(index-nearest)

The smallest one will be our new nearest until the end, when we can return the 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 it out, please let me know how you would solve it!

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 constant 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 solve 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, is not an easy operation: there are many ordering algorithms, some more efficient than others, but none of them is trivial enough to briefly explain it in 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 share it with someone who could find this interesting, too!

As always, a big thanks for reading

Nicola

Also published here.