{"id":"94541ea7-ac6e-44b4-a902-b9f0ebb072db","name":"Validate Stack Sequences","description":"1: Given two sequences pushed and popped with distinct values.\r\n2: You have to return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1: pushed is a permutation of popped\r\n2: pushed and popped have distinct values","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<vector>\n#include<stack>\nusing namespace std;\n\nbool validateStackSequences(vector<int> pushed , vector<int> popped){\n // write your code here\n}\n\nint main(){\n string s1;\n getline(cin, s1);\n vector<int> pushed;\n for(int i=0; i<s1.size(); i++){\n if(isdigit(s1[i])){\n int val = 0;\n while(isdigit(s1[i])){\n val = val*10 + (s1[i]-'0');\n i++;\n }\n i--;\n pushed.push_back(val);\n }\n }\n string s2;\n getline(cin, s2);\n vector<int> popped;\n for(int i=0; i<s2.size(); i++){\n if(isdigit(s2[i])){\n int val = 0;\n while(isdigit(s2[i])){\n val = val*10 + (s2[i]-'0');\n i++;\n }\n i--;\n popped.push_back(val);\n }\n }\n bool ans = validateStackSequences(pushed, popped);\n if(ans)\n cout<<\"true\";\n else \n cout<<\"false\";\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static boolean validateStackSequences(int[] pushed, int[] popped) {\r\n // Write Your''s code here\r\n return false;\r\n }\r\n\r\n public static int[] getArr(String s){\r\n String nums[] = s.split(\" \");\r\n int n = nums.length;\r\n int ar[] = new int[n];\r\n for(int i=0;i<n;i++){\r\n ar[i] = Integer.parseInt(nums[i]);\r\n }\r\n return ar;\r\n }\r\n \r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int pushed [] = getArr(read.readLine());\r\n int popped [] = getArr(read.readLine());\r\n \r\n boolean result = validateStackSequences(pushed, popped);\r\n\r\n System.out.println(result);\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"1 2 3 4 5\r\n4 5 3 2 1","sampleOutput":"true\r\n","questionVideo":"https://www.youtube.com/embed/KsIeZfmvuVQ","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8c6022a5-8654-4226-918f-8110af738bd4","name":"Stacks For Intermediate","slug":"stacks-for-intermediate-688","type":0},{"id":"6742cf92-3e9c-4359-a684-3a543c699cbc","name":"Validate Stack Sequences","slug":"validate-stack-sequences","type":1}],"next":{"id":"d6552f27-8e6f-41bd-ac3b-c692471eccfd","name":"Validate Stack Sequences Medium MCQ","type":0,"slug":"validate-stack-sequences-medium-mcq"},"prev":{"id":"30e43900-783e-4590-9a96-285354c00e0e","name":"Maximal Rectangle","type":3,"slug":"maximal-rectangle"}}}

Validate Stack Sequences

1: Given two sequences pushed and popped with distinct values. 2: You have to return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack

{"id":"94541ea7-ac6e-44b4-a902-b9f0ebb072db","name":"Validate Stack Sequences","description":"1: Given two sequences pushed and popped with distinct values.\r\n2: You have to return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1: pushed is a permutation of popped\r\n2: pushed and popped have distinct values","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<vector>\n#include<stack>\nusing namespace std;\n\nbool validateStackSequences(vector<int> pushed , vector<int> popped){\n // write your code here\n}\n\nint main(){\n string s1;\n getline(cin, s1);\n vector<int> pushed;\n for(int i=0; i<s1.size(); i++){\n if(isdigit(s1[i])){\n int val = 0;\n while(isdigit(s1[i])){\n val = val*10 + (s1[i]-'0');\n i++;\n }\n i--;\n pushed.push_back(val);\n }\n }\n string s2;\n getline(cin, s2);\n vector<int> popped;\n for(int i=0; i<s2.size(); i++){\n if(isdigit(s2[i])){\n int val = 0;\n while(isdigit(s2[i])){\n val = val*10 + (s2[i]-'0');\n i++;\n }\n i--;\n popped.push_back(val);\n }\n }\n bool ans = validateStackSequences(pushed, popped);\n if(ans)\n cout<<\"true\";\n else \n cout<<\"false\";\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static boolean validateStackSequences(int[] pushed, int[] popped) {\r\n // Write Your''s code here\r\n return false;\r\n }\r\n\r\n public static int[] getArr(String s){\r\n String nums[] = s.split(\" \");\r\n int n = nums.length;\r\n int ar[] = new int[n];\r\n for(int i=0;i<n;i++){\r\n ar[i] = Integer.parseInt(nums[i]);\r\n }\r\n return ar;\r\n }\r\n \r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int pushed [] = getArr(read.readLine());\r\n int popped [] = getArr(read.readLine());\r\n \r\n boolean result = validateStackSequences(pushed, popped);\r\n\r\n System.out.println(result);\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"1 2 3 4 5\r\n4 5 3 2 1","sampleOutput":"true\r\n","questionVideo":"https://www.youtube.com/embed/KsIeZfmvuVQ","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8c6022a5-8654-4226-918f-8110af738bd4","name":"Stacks For Intermediate","slug":"stacks-for-intermediate-688","type":0},{"id":"6742cf92-3e9c-4359-a684-3a543c699cbc","name":"Validate Stack Sequences","slug":"validate-stack-sequences","type":1}],"next":{"id":"d6552f27-8e6f-41bd-ac3b-c692471eccfd","name":"Validate Stack Sequences Medium MCQ","type":0,"slug":"validate-stack-sequences-medium-mcq"},"prev":{"id":"30e43900-783e-4590-9a96-285354c00e0e","name":"Maximal Rectangle","type":3,"slug":"maximal-rectangle"}}}
plane

Editor


Loading...

Validate Stack Sequences

medium

1: Given two sequences pushed and popped with distinct values. 2: You have to return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack

Constraints

1: pushed is a permutation of popped 2: pushed and popped have distinct values

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

1 2 3 4 5 4 5 3 2 1

Sample Output

true

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode