Count how many iterations of deletion until array is ordered

Question

I'm trying to write a program whose input is an array of integers, and its size. This code has to delete each element which is smaller than the element to the left. We want to find number of times that we can process the array this way, until we can no longer delete any more elements.

The contents of the array after we return are unimportant - only the return value is of interest.

For example: given the array {10, 9, 7, 8, 6, 5, 3, 4, 2, 1}, the function should return 2, because [10,9,7,8,6,5,3,4,2,1] → [10,8,4] → [10].

int numberOfTimes(int array[] , int n) { int count = 0; int flag = 0; int sizeCounter = 0; while (true){ for (int i = 0; i < n-1; ++i) { if (array[i]<= array[i+1]){ sizeCounter++; array[sizeCounter] = array[i+1]; } else{ flag = 1; } } if (flag == 0) return count; count++; flag = 0; n = (sizeCounter+1); sizeCounter = 0; } } 

My code works but I want it to be faster.

Do you have any idea to make this code faster, or another way that is faster than this?

Answer 1

Cannot tell about how to make your solution run faster, but I have some suggestions for the cosmetic issues in your code:

size_t for counting stuff

Instead of using int values for counting, it is more customary to use size_t instead.

Reducing scope

int numberOfTimes(int array[], int n) { int count = 0; int flag = 0; int sizeCounter = 0; while (true) { ... 

Above, you could move both flag and sizeCounter inside the while loop:

while (true) { int sizeCounter = 0; int flag = 0; ... 

Use bool for flag

C++ provides the bool data type; it accepts only two values: true and false. Use it.

Summa summarum

All in all, I had the following rewrite:

// Modifies array! size_t numberOfTimes2(int array[], size_t n) { size_t count = 0; while (true) { size_t sizeCounter = 0; bool flag = false; for (size_t i = 0; i < n - 1; ++i) { if (array[i] <= array[i + 1]) { array[++sizeCounter] = array[i + 1]; } else { flag = true; } } if (!flag) { return count; } count++; n = sizeCounter + 1; } } 

(See this gist for demo.)

Answer 2

In addition to the issues coderodde pointed out,

• ⧺I.13 Do not pass an array as a single pointer (includes pointer and count parameters in the discussion)

• ⧺R.14 Avoid [] parameters, prefer span

• ⧺F.24 Use a span<T> or a span_p<T> to designate a half-open sequence

Real reusable code would allow any kind of sequential container of values to be passed in. The caller will most likely have a vector, not a plain C array! If you look at anything in the standard library, you'll see that algorithms take a pair of iterators or a range to work on.

Answer 3

It would be good to include some tests with the code, so that we can confirm it returns the correct results.

It's very hard to read, because it is written like a C program, and fails to take advantage of the rich standard library provided with C++. We've reimplemented std::remove_if(), but we could just use that algorithm directly, for much simpler code. Look how a more idiomatic C++ function looks, and see that it doesn't need to do any actual arithmetic other than the comparison:

#include <algorithm> #include <climits> #include <utility> #include <span> std::size_t count_peak_iterations(std::span<int> array) { auto a = array.rbegin(); auto z = array.rend(); auto one_pass = [a, &z](){ auto prev = INT_MAX; auto new_z = std::remove_if(a, z,[&prev](int n){ return n > std::exchange(prev,n); }); return new_z != std::exchange(z, new_z); }; std::size_t count = 0; while (one_pass()) { ++count; } return count; } 

(If the use of std::exchange() looks a little tricky to follow, it just saves us having to introduce new short-term variables to store return values.)

---

Given that we don't care about the results in the array, we can avoid rewriting it, if we think a little about what happens during the process. I find it helps to visualise this graphically by looking at values as the y values on a chart like this:

5| · 4| · 3| · 2| · 1|· |------ 

We can write in the iteration at which each element is deleted. For the simplest case, all of the elements are already in ascending order, and there are no deletions at all (function returns 0):

 · · · · · 

When the array is in descending order, all elements except the first will be deleted in the first pass:

 · 1 1 1 1 

For several runs of descending elements, we see that they will all be dealt with in the first pass, and the "lead" element of the run may be deleted in a subsequent pass:

 · · 1 1 1 1 1 1 1 1 

 · 1 2 1 1 1 1 1 1 

When we have runs of increasing/equal values that are lower than some previous peak, we only delete the first of the run in each pass, so the counts increase quickly:

 · · · 5 4 · 4 3 · 3 2 · 2 1 · 1 

 · · 1234 12 

If we stare at these graphs for a while, we see that it's possible to compute the number of iterations by examining each element in turn, just once:

• We'll want to track the highest value previously seen; any value greater or equal to this will remain in the output.
• We need to count how many values we've seen in the current non-descending run less than the peak.
• Then we simply return the longest of those runs that we've seen (so we'll need a variable to track the maximum).

An implementation of that looks like this, and passes the tests that correspond to what I've drawn above:

#include <climits> #include <span> std::size_t count_peak_iterations(std::span<const int> array) { int peak = INT_MIN; int prev = INT_MIN; std::size_t max_iter = 0; std::size_t current_iter = 0; for (auto const value: array) { if (value < prev) { current_iter = 1; } else if (value < peak) { ++current_iter; } else { peak = value; } if (current_iter > max_iter) { max_iter = current_iter; } prev = value; } return max_iter; } 

This version scales much better than the original (it's O(n) rather than O(m ✕ n), where n is the input size and m is the result value).