Delete middle element from stack

Easy
0/40
Average time to solve is 15m
profile
Contributed by
215 upvotes
Asked in companies
Wells FargoAmazonTech Mahindra

Problem statement

You are having a stack "ARR" of size 'N+1', your task is to delete the middlemost element so that the size of resulting stack is 'N'.

A stack is a linear data structure where both insertion and deletion of elements take place at the top. It follows FILO (First In Last Out) or LIFO (Last In First Out) approaches. Books piled on top of each other is an example of a stack, where you can only remove a single book at a time, which is at the top of the stack. Likewise, you can only add a single book at a time, on the top of the stack only.

Example :- 
INPUT : ARR [ ] = [ 1 , 2 , 3 , 4 , 5 ] , N = 4
OUTPUT: ARR [ ] = [ 1 , 2 , 4,  5 ]

The above example contains an odd number of elements, hence the middle element is clearly the (N+1) / 2th element, which is removed from the stack in the output.

INPUT : ARR [ ] = [ 5, 6, 7, 8 ] , N = 3
OUTPUT: ARR [ ] = [ 5, 7, 8 ]

The above example contains an even number of elements, so out of the two middle elements, we consider the one which occurs first. Hence, the middle element would be ((N+1) / 2 - 1) element, which is 6 and is removed from the stack in the output.
Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains an integer 'N', where 'N+1' denotes the number of elements in the stack initially.

The second line of each test case contains 'N+1' space-separated integers, denoting the elements of the stack.

Output Format:

For every test case, print 'N' space-separated integer, denoting the elements in the stack after removing the middle element from the input stack. 
The output of every test case will be printed in a separate line.
Note: 
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100    
1 <= N+1 <= 3000
0 <= data <= 10^9

Where ‘T’ is the number of test cases, ‘N+1’ is the number of elements in the input Stack. ‘data’ is the value of each element in the stack.

Time limit: 1 second
Sample Input 1:
2
4
1 2 3 4 5
7
83 74 67 49 94 8 11 1
Sample Output 1:
1 2 4 5
83 74 67 94 8 11 1

Explanation for Sample 1:

In the 1st testcase, there are an odd number of elements, hence the middle element is clearly the (N+1) / 2th element which is 3, and is removed from the stack in the output.

In the 2nd testcase, there are an odd number of elements, hence the middle element is clearly the (N+1) / 2th element which is 49, and is removed from the stack in the output.
Sample Input 2:
3
1
5 10    
4
1 3 4 2 7
5
9 5 2 7 8 6
Sample Output 2:
10
1 3 2 7
9 5 7 8 6
Hint

Can we do it recursively?

Approaches (2)
Recursive approach

The idea is to use recursive calls. We first remove all items one by one, then we recur. After recursive calls, we push all items back except for the middle item.

 

  1. We have an input stack as “INPUTSTACK”, ‘N’ denotes the number of elements in the stack.
  2. We define a function "DELETEMIDDLE" that accepts, a stack of integers "STACK" and an integer “COUNT” (initially 0) as input parameters.
  3. Now we define the base condition. If the stack is empty or, if all the elements are traversed (COUNT == N), we return.
  4. Now we create a new integer variable, say “TOP”, and we store the top of the "STACK" in "TOP", simultaneously pop out the top element of the stack.
  5. Call the recursive function “DELETEMIDDLE”  by incrementing the value of "COUNT" by 1.
  6. Add "TOP" back to “STACK”, if COUNT != N / 2.
  7. At the end of recursive calls, our stack will contain “N - 1” elements, after removing the middle element of the input stack.

 

Algorithm:

 

  • Initialise “DELETEMIDDLE"( STACK, N, COUNT = 0)
  • IF "STACK" is empty OR “COUNT” is equal to ‘N’:
    • Return
  • If “TOP” is equal to the top element of "STACK"
  • Pop the top element of "STACK"
  • Recursively call “DELETEMIDDLE”( STACK, N, COUNT+1 )
  • STACK.push(TOP) if COUNT != N / 2
Time Complexity

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

 

We are doing recursive calls at most N times and every call is doing a linear amount of work. Hence the worst-case time complexity is O(N).

Space Complexity

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

 

We are storing a total of N number of elements in the recursion stack. Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
Delete middle element from stack
Full screen
Console