Reduce array to a single element by repeatedly removing an element from any increasing pair

Algorithm

• Check if the first element is greater than last element print “no” if the first element is smaller than last element print “Yes” and call the order function
• Make a queue data structure which  Stores all those indices whose values are greater  then the element at first index
• Queue Stores the index of the closest elements from index 0
• Start pushing the indices in the queue whose values is greater than the first element
• Now start a iteration in the updated queue
• In every iteration the front element of queue will give the value of index which is having value grater than input[0] in closest from 0th index
• Now simply print the index because this is going to be the index which we want to make as 0 
• At last update the previous index with the current index

Code:

#include <bits/stdc++.h>
using namespace std;

//reduce the array to a single non-zero element 
void order(int input[], int size)
{

    /* 
        Queue here Stores all those indices whose values
        are greater than the element at first index
    */
    queue<int> greater_element_indices;

    int first_element = input[0];
 
    // Stores the index of the closest number to index 0
    int previous_index = 0;
 
    // Pushing the indices in queue
    for (int i = 1; i < size; i++) {
        if (input[i] > first_element)
            greater_element_indices.push(i);
    }
 
    // Traversing in the updated queue
    while (greater_element_indices.size() > 0) {
 
        // Stores the index of the closest number > input[0]
        int index = greater_element_indices.front();
 
        greater_element_indices.pop();
        
 
        // Now since this is greater element than oth index we have to remove it
        int to_remove_index = index;
 
        // Remove all those elements present in indices [1, to_remove - 1]
        while (--to_remove_index > previous_index)
        cout << to_remove_index << " "<< index << " "<< to_remove_index << endl;
 
        cout << 0 << " " << index << " "<< index << endl;
 
        // Update the previous_index to current index
        previous_index = index;
    }
}

//reduce the array to a single non-zero element 
void if_reduce(int input[], int size)
{

    /*
       Checking first and last element if first element
       is greater than last there is no chance to reduce
       the array in a singleton nonzero element
   */
    if (input[0] > input[size - 1]) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;

        /*
            Finding the order in which we can reduce
            the array to a singleton nonzero element
       */
        order(input, size);
    }
}


int main()
{

    // Given input array and the size of the array
    int input[] = { 12,14,16,11,13,15 };
    int size = 6;

    // Function which check if we can reduce the array to a single non-zero element 
    if_reduce(input,size);
    return 0;
}

Output:

Yes
0 1 1
0 2 2
3 4 3
0 4 4
0 5 5

Time Complexity 

O(N)
The time complexity for the problem “Reduce the array to a single non-zero element by repeatedly removing an element from any increasing pair ” is O(N) where ‘N’ is the total size of the input array. To check whether we can reduce the array will cost O(1) time complexity while printing the order will take O(N) time since we are iterating on every element once. So the total time complexity will be linear.

Space Complexity 

O(N)
The space complexity for the problem “Reduce the array to a single non-zero element by repeatedly removing an element from any increasing pair ” is O(N) where ‘N’ is the total size of the input array.

Since we are using a queue of integers to store those indices whose value is greater than the first element so in the worst case, if the input array is completely sorted in that situation queue will store all the indices of the input array and it will approximately cost O(N) space complexity 

Frequently Asked Questions

1.What is a queue?

A data structure that stores elements in linear fashion and element can be inserted from the backside and deleted from the front side 

2.What are different operations in the queue?

The most commonly used operations in a queue are as follow:

Enqueue: Adding an element at the end of queue

Dequeue: removing an element at the end of queue  

IsEmpty: checks whether the queue is empty or not

IsFull: for checking whether the queue is full or not 

Peek: print the front element of the queue without removing it

3.Is there any other way to Reduce the array to a single non-zero element?

Yes instead of the queue we can use a vector to store the indices whose values are greater than the first index element but while pushing and popping the element we have to maintain the two variables which will keep a track of it

and that will make a process little complex the time complexity for the above solution will be again O(N) and space complexity will also be O(N).

Key Takeaways

In this blog, we solved the problem to Reduce the array to a single non-zero element by repeatedly removing an element from any increasing pair.

Check out the following problems - 

• Sum Of Two Arrays.
• Merge K Sorted Arrays.
• Intersection Of Two Arrays.

If you want to learn more about arrays and want to practice some questions which require you to take your basic knowledge on arrays a notch higher, then you can visit our Guided Path for arrays on  Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

By Apoorv