Back to top

Stacks

Quick Video Glance

Overview

A stack primarily supports two main operations - push and pop. Elements are added(aka pushed) and removed(aka popped) in last-in, first-out order. If the stack is empty, pop returns null or throws an exception. A stack can support operations such as peek, which returns the top of the stack without popping it. The image below demonstrates the various operations.

Fig 0: Different stack operations

In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using stacks. We don’t want to overwhelm our readers with a plethora of stack questions. So, we have done the heavy lifting for you by going through almost all the questions on leetcode and categorizing the different patterns of questions commonly asked in the interviews.

Pattern -1 : Real-Life Applications

Prob 71 - Simplify Path

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We want to create a canonical path given an absolute path
         * https://leetcode.com/problems/simplify-path/
         *
         * Approach: We will split the path by using the "/" character into an
         * array. We then iterate through the array to skip the empty characters.
         * After that, I pop from the stack when a ".." string is encountered.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         *
         * @param path
         * @return
         */
        public String simplifyPath(String path) {
            String[] a = path.split("/");
            Stack<String> stack = new Stack<>();

            for(int i = 0; i < a.length; i++) {
                if(a[i].equals("") || a[i].equals(".")) {
                    continue;
                }
                if(a[i].equals("..")) {
                    if(!stack.isEmpty()) {
                        stack.pop();
                    }
                    continue;
                }
                stack.push(a[i]);
            }
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("/");
            Stack<String> reverseStack = new Stack<>();
            while (!stack.isEmpty()) {
                reverseStack.push(stack.pop());
            }

            while (!reverseStack.isEmpty()) {
                stringBuilder.append(reverseStack.pop());
                stringBuilder.append("/");
            }
            if(stringBuilder.length() > 1) {
                stringBuilder.setLength(stringBuilder.length()-1);
            }

            return stringBuilder.toString();
        }

Prob 682 - Baseball Game

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         * This method is used to calculate points as specified here:
         * https://leetcode.com/problems/baseball-game/
         *
         *
         * The approach is to maintain the value of each valid round 
         * on a stack as we process the data.
         * We use a stack as we only deal with operations involving 
         * the last or second-last valid round.
         *
         * Time Complexity : O(n)
         * Space Complexity : O(n)
         *
         * @param ops - the input string
         * @return the calculated points
         */
        public int calPoints(String[] ops) {

            Stack<Integer> stack = new Stack();

            for(String op : ops) {
                if (op.equals("+")) {
                    int top = stack.pop();
                    int newtop = top + stack.peek();
                    stack.push(top);
                    stack.push(newtop);
                } else if (op.equals("C")) {
                    stack.pop();
                } else if (op.equals("D")) {
                    stack.push(2 * stack.peek());
                } else {
                    stack.push(Integer.valueOf(op));
                }
            }

            int ans = 0;
            for(int score : stack) ans += score;
            return ans;
        }

Prob 739 - Daily Temperatures

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * This method is used to tell you how many days 
         * you would have to wait until a warmer temperature.
         * https://leetcode.com/problems/daily-temperatures/
         *
         * Approach : We will maintain a stack to keep track 
         * of the indexes of elements and popping the elements
         * which are lesser than the current element.
         *
         * Time Complexity : O(n)
         * Space Complexity : O(n)
         *
         * @param T - array of daily temperatures
         * @return - array of number of days
         */
        public int[] dailyTemperatures(int[] T) {

            Stack<Integer> stack = new Stack<>();

            int[] res = new int[T.length];

            for (int i = 0; i < T.length; i++) {
                while (!stack.isEmpty() && T[stack.peek()] < T[i]){
                    int temp =  stack.pop();
                    res[temp] = i - temp;
                }
                stack.push(i);
            }

            return res;
        }

Prob 1410 - HTML Entity Parser

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         * The following method implements a parser that takes
         * HTML code as input and replace all the entities of the
         * special characters by the characters itself. 
         * https://leetcode.com/problems/html-entity-parser/
         *
         * Approach - We will maintain a map to store the html 
         * entities to the corresponding character. We will then use
         * stack to keep track of the characters encountered so far. 
         * Once the ";" character is encountered then we pop the
         * elements from the stack to create the string of the html entity.
         *
         * Time Complexity - O(n)
         * Space Complexity - O(n)
         *
         * @param text - the input text
         * @return the parsed html string
         */
        public String entityParser(String text) {

            Map<String, Character> entityMap = new HashMap<>();
            entityMap.put(";touq&", '"');
            entityMap.put(";sopa&", '\'');
            entityMap.put(";pma&", '&');
            entityMap.put(";tg&", '>');
            entityMap.put(";tl&", '<');
            entityMap.put(";lsarf&", '/');

            StringBuffer buffer = new StringBuffer();
            boolean push = false;
            Stack<Character> stack = new Stack<>();

            for(int i = 0; i  < text.length(); i++) {
                if (push && text.charAt(i) == ';') {
                    StringBuffer tempBuffer = new StringBuffer();
                    while (!stack.isEmpty()) {
                        tempBuffer.append(stack.pop());
                    }
                    if(entityMap.containsKey(tempBuffer.toString())) {
                        buffer.append(entityMap.get(tempBuffer.toString()));

                    } else {
                        buffer.append(tempBuffer.reverse().toString());
                    }

                    push = false;
                    continue;
                } else if (push) {
                    stack.push(text.charAt(i));
                    continue;
                }

                if(text.charAt(i) == '?') {
                    stack.push(text.charAt(i));
                    push = true;
                }
                if( !push) {
                    buffer.append(text.charAt(i));
                }
            }
            return buffer.toString();
        }

Prob 636 - Exclusive Time of Functions

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         * This method is used to calculate the time of functions 
         * in a single-threaded CPU as mentioned below.
         * https://leetcode.com/problems/exclusive-time-of-functions/
         *
         * Approach: We maintain two stacks, one for keeping track of
         * the jobs encountered so far and another to store the 
         * timestamps of the jobs.
         * 
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param n - number of jobs
         * @param logs - the CPU logs
         * @return the time spent by individual jobs
         */
        public int[] exclusiveTime(int n, List<String> logs) {

            Stack<Integer> timeStamps = new Stack<>();
            Stack<Integer> jobs = new Stack<>();
            int res[] = new int[n];
            for (String log : logs) {
                String[] split = log.split(":");
                int jobId = Integer.parseInt(split[0]);
                int timestamp = Integer.parseInt(split[2]);

                if(split[1].equals("start")) {

                    if(!jobs.isEmpty()) {
                        int spent = timestamp - timeStamps.peek();
                        res[jobId] += spent;
                    }
                    jobs.push(jobId);
                    timeStamps.push(timestamp);
                } else {
                    int spent = timestamp - timeStamps.peek() + 1;
                    res[jobId] += spent;
                    jobs.pop();
                    timeStamps.pop();
                    if (!timeStamps.isEmpty()) {
                        timeStamps.pop();
                        timeStamps.push(timestamp + 1);
                    }

                }
            }
            return res;
        }

Pattern - 2 : String Validations

Prob 856 - Score of Parantheses

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         *  This method is used to compute the score using the paranthesis,
         * as mentioned in link below.
         *  https://leetcode.com/problems/score-of-parentheses/
         *
         *  Approach - We use stack to keep track of the value computed so far.
         *  We increment the value when "()" is encountered.
         *  The value is doubled when a closing bracket(i.e. ")") is encountered.
         *
         *  Time Complexity : O(n)
         *  Space Complexity : O(n)
         *
         * @param S - the input string
         * @return the score computed based on the paranthesis
         */
        public int scoreOfParentheses(String S) {

            Stack<Integer> stack = new Stack<>();
            int val = 0;

            for( int i = 0; i < S.length(); i++) {
                if(i < S.length() -1 && S.charAt(i) == '(' && S.charAt(i+1) == ')') {
                    val++;
                    i++;
                } else if(S.charAt(i) == '(') {
                    stack.push(val);
                    val = 0;
                } else {
                    val = 2 * val  + stack.pop();
                }
            }
            return val;
        }

Prob 1003 - Check If Word Is Valid After Substitutions

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         * This method is used to determine if a word will be valid after substitution.
         * https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/
         *
         * Approach: Everytime we encounter the character 'c' we will 
         * check if the last two elements were 'a' and 'b'.
         * The stack should be empty in case of valid strings.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param S
         * @return
         */
        public boolean isValid(String S) {

            Stack<Character> stack = new Stack<>();

            for( int i = 0; i < S.length(); i++) {
                if(S.charAt(i) == 'c') {
                    if(stack.size() < 2) {
                        return false;
                    }
                    if(stack.pop() != 'b' || stack.pop() != 'a'){
                        return false;
                    }
                } else {
                    stack.push(S.charAt(i));
                }
            }
            return stack.isEmpty();
        }

Prob 1249 - Minimum Remove to Make Valid Parentheses

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         * This method is used to remove the minimum number 
         * of parenthesis for a valid string.
         * https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
         *
         * Approach: We will push the indexes of "(" character in the string.
         * We will pop those indexes from the stack when ")" is encountered.
         * We mark the indexes of all the extra opening and closing brackets with a
         * dummy underscores character.
         *
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param s - the input string
         * @return - the string after removing the invalid parenthesis
         */
        public String minRemoveToMakeValid(String s) {

            char[] sA = s.toCharArray();
            Stack<Integer> stack = new Stack<>();

            for(int i = 0; i < s.length(); i++) {
                if(sA[i] == '(') {
                    stack.push(i);
                } else if(sA[i] == ')') {
                    if(!stack.isEmpty()) {
                        stack.pop();
                    }else {
                        sA[i] = '_';
                    }
                }
            }

            while (!stack.isEmpty()) {
                sA[stack.pop()] = '_';
            }

            StringBuffer buffer = new StringBuffer();

            for( int i = 0; i < sA.length; i++) {
                if(sA[i] != '_') {
                    buffer.append(sA[i]);
                }
            }

            return buffer.toString();

        }

Pattern -3 : Auxillary Data Structure

Prob 456 - 132 Pattern

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

     /**
         * This method determines if a 1-3-2 patterns in an array of integers.
         * https://leetcode.com/problems/132-pattern/
         *
         * Approach: We maintain an auxillary data structure to store the
         * minimum element encountered so far. After that, we iterate starting
         * from the last element of the array. We push the elements on the stack
         * and pop the elements which don't satisfy the i-j-k property.
         *
         * Time Complexity : O(n)
         * Space Complexity : O(n)
         *
         * @param nums - array of integers
         * @return boolean flag representing if 1-3-2 pattern is satisfied or not.
         */
        public boolean find132pattern(int[] nums) {
            if(nums == null || nums.length < 3) {
                return false;
            }
            int aux[]= new int[nums.length];
            Stack<Integer> stack = new Stack<>();

            aux[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                aux[i] = Math.min(nums[i], aux[i-1]);
            }
            stack.push(nums[nums.length -1]);
            for (int i = nums.length -2; i >= 0; i--) {
                if(nums[i] > aux[i]) {
                    while (!stack.isEmpty() && stack.peek() <= aux[i]) {
                        stack.pop();
                    }
                    if(!stack.isEmpty() && stack.peek() < nums[i]) {
                        return true;
                    }
                    stack.push(nums[i]);
                }
            }
            return false;
        }

Prob 907 - Sum of subarray minimums

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         * This method finds the sum of sub array minimum elements defined here"
         * https://leetcode.com/problems/sum-of-subarray-minimums/
         *
         * Approach: We have used a dp based solution to find the sum of minimum
         * elements of all the subarrays till index i and total number of subarrays
         * ending at index i is equal to i + 1\. We start by iterating from index=1 and
         * use a stack to maintain the index of the latest smallest index encountered
         * so far. If we find an index "j" in the stack such that A[j] < A[i] then all
         * the subarrays which start from "j" will have A[i] as the smallest element. Otherwise,
         * the jth element will be the minimum element.
         *
         * Time Complexity : O(n)
         * Space Complexity : O(n)
         *
         * @param A
         * @return
         */
        public int sumSubarrayMins(int[] A) {
            if (A == null || A.length < 1) {
                return 0;
            }

            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            int mod = 1000000007;
            int dp[] = new int[A.length];
            int res = A[0];
            dp[0] = A[0];
            for (int i = 1; i < A.length; i++) {
                while (!stack.isEmpty() && A[stack.peek()] > A[i]) {
                    stack.pop();
                }
                if(!stack.isEmpty()) {
                    dp[i] = (A[i] * (i - stack.peek())) + dp[stack.peek()];
                } else {
                    dp[i] = A[i] * (i+1);
                }
                res = (res + dp[i])%mod;
                stack.push(i);
            }
            return res;
        }

References