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]

For example: given the array [1,2,3,4], the function should return 0, because No element is larger than the element to its right

I want each element to remove the right element if it is more than its right element. We get a smaller array. Then we repeat this operation again. Until we get to an array in which no element can delete another element. I want to calculate the number of steps performed.

int Mafia(int n, vector <int> input_array)
{
    int ptr = n;
    int last_ptr = n;
    int night_Count = 0;
    do
    {
        last_ptr = ptr;
        ptr = 1;
        for (int i = 1; i < last_ptr; i++)
        {
            if (input_array[i] >= input_array[i - 1])
            {
                input_array[ptr++] = input_array[i];
            }
        }
        night_Count++;
    } while (last_ptr > ptr);


    return night_Count - 1;
}

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

Here is a O(NlogN) solution.

The idea is to iterate over the array and keep tracking candidateKillers which could kill unvisited numbers. Then we find the killer for the current number by using binary search and update the maximum iterations if needed.

Since we iterate over the array which has N numbers and apply log(N) binary search for each number, the overall time complexity is O(NlogN).

Alogrithm

• If the current number is greater or equal than the number before it, it could be a killer for numbers after it.

• For each killer, we keep tracking its index idx, the number of it num and the iterations needed to reach that killer iters.

• The numbers in the candidateKillers by its nature are non-increasing (see next point). Therefore we can apply binary search to find the killer of the current number, which is the one that is a) the closest to the current number b) greater than the current number. This is implemented in searchKiller.

• If the current number will be killed by a number in candidateKillers with killerPos, then all candidate killers after killerPos are outdated, because those outdated killers will be killed before the numbers after the current number reach them. If the current number is greater than all candidateKillers, then all the candidateKillers can be discarded.

• When we find the killer of the current number, we increase the iters of the killer by one. Because from now on, one more iteration is needed to reach that killer where the current number need to be killed first.

class Solution {
public:
    int countIterations(vector<int>& array) {
        if (array.size() <= 1) {
            return 0;
        }
        int ans = 0;
        vector<Killer> candidateKillers = {Killer(0, array[0], 1)};

        for (auto i = 1; i < array.size(); i++) {
            int curNum = array[i];
  
            int killerPos = searchKiller(candidateKillers, curNum);
            if (killerPos == -1) {
                // current one is the largest so far and all candidateKillers before are outdated
                candidateKillers = {Killer(i, curNum, 1)};
                continue;
            }
            
            // get rid of outdated killers
            int popCount = candidateKillers.size() - 1 - killerPos;
            for (auto j = 0; j < popCount; j++) {
                candidateKillers.pop_back();
            }
            
            Killer killer = candidateKillers[killerPos];
            ans = max(killer.iters, ans);
            
            if (curNum < array[i-1]) {
                // since the killer of the current one may not even be in the list e.g., if current is 4 in [6,5,4] 
                if (killer.idx == i - 1) {
                    candidateKillers[killerPos].iters += 1;
                }
            } else {
                candidateKillers[killerPos].iters += 1;
                candidateKillers.push_back(Killer(i, curNum, 1));   
            }

        }
        return ans;
    }
private:
    struct Killer {
        Killer(int idx, int num, int iters) 
            : idx(idx), num(num), iters(iters) {};
        int idx;
        int num;
        int iters;
    };
    
    int searchKiller(vector<Killer>& candidateKillers, int n) {
        int lo = 0;
        int hi = candidateKillers.size() - 1;
        if (candidateKillers[0].num < n) {
            return -1;
        }
        int ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (candidateKillers[mid].num > n) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }
};


int main() {
    vector<int> array1 = {10, 9, 7, 8, 6, 5, 3, 4, 2, 1};
    vector<int> array2 = {1, 2, 3, 4};
    vector<int> array3 = {4, 2, 1, 2, 3, 3};



    cout << Solution().countIterations(array1) << endl; // 2
    cout << Solution().countIterations(array2) << endl; // 0
    cout << Solution().countIterations(array3) << endl; // 4
}

Answer 2

You can iterate in reverse, keeping two iterators or indices and moving elements in place. You don't need to allocate a new vector or even resize existing vector. Also a minor, but can replace recursion with loop or write the code the way compiler likely to do it.

This approach is still O(n^2) worst case but it would be faster in run time.