Check if stack elements are pairwise consecutive

Difficulty Level Easy
Frequently asked in Delhivery Factset Fourkites
StackViews 3058

Problem Statement

“Check if stack elements are pairwise consecutive” problem states that you are given a stack data structure of integer type. Create a function to check if all the given elements are pairwise consecutive ( either in increasing or decreasing order ) or not. If the number of elements given in the stack is even, check all the pairs else leave the element at the top of the given stack. Also, retain the elements of the given stack during the program and print them with the result.

Check if stack elements are pairwise consecutive

Example

s = [4, 5, -2, -3, 11, 10, 5, 6, 20]
Yes

Explanation: Stack content (from top) after the function call [20 6 5 10 11 -3 -2 5 4]. The number of elements in the stack is odd. Thus 20 doesn’t get paired with any element. But other elements are paired and they are consecutive pairwise.

s = [4, 6, 6, 7, 4, 3]
No

Explanation: Stack content (from top) after the function call [3 4 7 6 6 4]. And since the 4 and 6 have a difference of 2, they are not consecutive. Thus the result is No.

Algorithm to Check if stack elements are pairwise consecutive

1. Create a stack data structure of the integer type and insert/push the elements in it.
2. Create another auxiliary stack data structure of the integer type.
3. Traverse while the original stack is not empty and push the element at top of  the auxiliary stack and pop the element from the top of the original stack.
4. Create a variable result of the boolean type and set its value as true.
5. Traverse through the auxiliary stack and pop the top 2 elements in the auxiliary stack and store them in 2 integer variables.
6. Check if the absolute difference of both the integer variables is not equal to 1, update the boolean variable result as false. Push / insert both the integer variables in the original stack.
7. Check if the size of the auxiliary stack is equal to 1, Push/insert the element at the top of the auxiliary stack in the original stack.
8. Return the boolean variable result.
9. Check if the returned value is equal to true, print "Yes" else print "No".
10. Print the original stack.

In this problem, we are given an initial original stack that needs to be checked. So, we create an auxiliary stack that is made just because we do not want to lose the original stack. If we did not want to store the initial stack and can modify the initial stack we could have simply taken out the elements from the original stack. So auxiliary stack serves as the stack copy. Now when we have an auxiliary stack, we can remove 2 elements from the top and then we check for connectivity.

Code

C++ Program to Check if stack elements are pairwise consecutive

#include <bits/stdc++.h> 
using namespace std; 
  
bool isConsecutive(stack<int> s){ 
    stack<int> aux; 
    
    while(!s.empty()){ 
        aux.push(s.top()); 
        s.pop(); 
    } 
  
    bool result = true; 
    
    while(aux.empty() > 1){ 
        int x = aux.top(); 
        aux.pop(); 
        int y = aux.top(); 
        aux.pop(); 
        
        if(abs(x - y) != 1){ 
            result = false; 
        }
  
        s.push(x); 
        s.push(y); 
    } 
  
    if(aux.size() == 1){ 
        s.push(aux.top());
    }
  
    return result; 
} 
  
int main(){ 
    stack<int> s;
    
    s.push(4); 
    s.push(5); 
    s.push(-2); 
    s.push(-3); 
    s.push(11); 
    s.push(10); 
    s.push(5); 
    s.push(6); 
    s.push(20); 
  
    if(isConsecutive(s)){ 
        cout << "Yes" << endl; 
    }
    
    else{
        cout << "No" << endl;
    }
  
    cout << "Stack content (from top)"
          " after function call\n"; 
    
    while(s.empty() == false){ 
       cout << s.top() << " "; 
       s.pop(); 
    } 
  
    return 0; 
}
Yes
Stack content (from top) after function call
20 6 5 10 11 -3 -2 5 4

Java Program to Check if stack elements are pairwise consecutive

import java.util.*; 

class CheckPair{ 
    
    static boolean isConsecutive(Stack<Integer> s){  
        Stack<Integer> aux = new Stack<Integer> ();  
        
        while(!s.isEmpty()){  
            aux.push(s.peek());  
            s.pop();  
        }  
      
        boolean result = true;  
        
        while(aux.size() > 1){  
            int x = aux.peek();  
            aux.pop();  
            int y = aux.peek();  
            aux.pop();  
            
            if(Math.abs(x - y) != 1){  
                result = false;  
            }
      
            s.push(x);  
            s.push(y);  
        }  
      
        if(aux.size() == 1){  
            s.push(aux.peek());
        }
      
        return result;  
    }  
      
    public static void main(String[] args){  
        Stack<Integer> s = new Stack<Integer> ();
        
        s.push(4);  
        s.push(5);  
        s.push(-2);  
        s.push(-3);  
        s.push(11);  
        s.push(10);  
        s.push(5);  
        s.push(6);  
        s.push(20);  
      
        if(isConsecutive(s)){  
            System.out.println("Yes");
        }
        
        else{
            System.out.println("No");  
        }
      
        System.out.println("Stack content (from top) after function call");  
        
        while(s.isEmpty() == false){  
            System.out.print(s.peek() + " ");  
            s.pop();  
        }  
      
    }  
}
Yes
Stack content (from top) after function call
20 6 5 10 11 -3 -2 5 4

Complexity Analysis

Time Complexity

O(N), where N is the number of elements in the stack.

Space Complexity

O(N), we have used a stack to store N elements. Thus a linear space complexity is achieved.

Translate »