N Stacks In An Array

Hard
0/120
Average time to solve is 20m
profile
Contributed by
301 upvotes
Asked in companies
IntuitBNY MellonAmazon

Problem statement

Design a data structure to implement ‘N’ stacks using a single array of size ‘S’. It should support the following operations:

push(X, M): Pushes an element X into the Mth stack. Returns true if the element is pushed into the stack, otherwise false.

pop(M): Pops the top element from Mth Stack. Returns -1 if the stack is empty, otherwise, returns the popped element.

Two types of queries denote these operations :

Type 1: for push(X, M) operation.
Type 2: for pop(M) operation.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains three space-separated integers ‘N’, ‘S’ and ‘Q’ denoting the number of stacks, the size of the array and number of queries, respectively. 

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure.

Each query contains an integer ‘P’ denoting the type of query.

For query of type 1, the integer ‘P’ is equal to 1 and it is followed by two space-separated integers ‘X’ and ‘M’ denoting the element and stack on which operation is to be performed, respectively.

For query of type 2, the integer ‘P’ is equal to 2 and it is followed by a single integer ‘M’ denoting the stack on which operation is to be performed.
Output format : 
For each query, print the output returned after performing the corresponding operation on the data structure.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given functions.
Constraints : 
1 <= N <= S <= 1000
1 <= Q <= 10^5 
1 <= P <= 2
1 <= X <= 10^5

Time Limit: 1 sec

Where ‘S’ represents the size of the array, ‘N’ represents the number of stacks, ‘Q’ represents the number of queries, ‘P’ represents the type of operation and ‘X’ represents the element.
Sample Input 1 :
3 6 5
1 10 1
1 20 1
1 30 2
2 1
2 2
Sample Output 1 :
True 
True
True
20
30
Explanation 1 :
For the given input, we have the number of stacks, N = 3, size of the array, S = 6 and number of queries, Q = 5.
Operations performed on the stack are as follows:
push(10, 1): Push element ‘10’ into the 1st stack. This returns true.
push(20, 1): Push element ‘20’ into the 1st stack. This returns true.
push(30, 2): Push element ‘30’ into the 2nd stack. This returns true.
pop(1): Pop the top element from the 1st stack. This returns 20.
pop(2): Pop the top element from the 2nd stack. This returns 30.

The following image shows the snapshots of the stack after each operation:

Sample Testcase 1

Sample Input 2 :
1 5 5
1 15 1
1 25 1
2 1
1 30 1
2 1
Sample Output 2 :
True
True
25
True
30
Hint

A simple and intuitive approach could be to divide the array equally into N parts and use each part to implement one stack.

Approaches (2)
Dividing The Array Equally Into N Parts

Note: This approach will give wrong answer on test cases.

  • A brute approach could be to divide the array of size S, into N parts of size S/N each.
  • We use these parts to implement the N number of stacks.
  • For example, if we have an array of size S:
    • The first stack will use the subarray Array[0, S/N - 1].
    • The second stack will use the subarray Array[S/N, 2*S/N - 1].
    • And so one till the Nth stack which will use the subarray Array[(N-1)*S/N, S-1]
  • An important point to note here is that every stack has a maximum size of S/N. Hence, if there are more than S/N push operations for any particular stack it will result in an overflow even if there is space available in the array. So, this approach may not work for all the test cases.

 

Algorithm:

  • Create an array arr of size S, which will be used to implement the stacks.
  • Create another array top of size N, which will be used to keep track of the indices of the top elements of every stack.
  • For every index ‘i’ (0 to N-1) in top, initialise top[i] with one less than the starting index of the subarray which is used for the ith stack i.e, top[i] = i * S / N - 1.

 

Algorithm for Push Operation:

  • If top[m-1] >= ((m * s) / n - 1), then the Mth stack is full. Hence, we cannot insert the element. So, return false.
  • Otherwise,
    • Update the index of the new top element by incrementing top[m-1].
    • Insert X at index top[m-1] in the array.
    • Return true.

 

Algorithm for Pop Operation:

  • If top[m-1] < ((m - 1) * (s / n)), then the Mth stack is empty. So, just return -1.
  • Otherwise,
    • Store the top element of Mth stack, i.e. arr[top[m - 1]], in a temporary variable say, element.
    • Update the index of the new top element by decrementing top[m-1].
    • Return element.
Time Complexity

O(1) for every operation.

 

In the worst case, all the operations can be performed in a constant time.

Space Complexity

O(S + N) where S is the size of the array and N is the number of stacks.

 

O(S) extra space is required for implementing the stacks and O(N) space is required for storing the top pointers. Hence, the overall complexity is O(S+N) 

Code Solution
(100% EXP penalty)
N Stacks In An Array
Full screen
Console