Evaluate postfix expression
Problem Statement: You are given an postfix expression, you need to evaluate that expression. Postfix expressions are in the form of a b op. Example Input: 2 3 1 * + 9 – Output: -4 Solution To solve this, we will make use of stacks. Create a stack to store the values. Then start scanning […]
Stack: Next Greater Element
Problem Statement: you are given an array, you need to get the next greater element for every element in the array. The next greater element for an element is the first greater element on the right side of x in the array. If there is no greater element then mark it as -1. Example Element […]
Stack: Check for balanced brackets using stack
Problem Statement: Given a string that has parenthesis. You need to check if it is balanced or not. Example Input: exp = “[()]{}{[()()]()}” Output: Balanced Solution We will use stack to solve this problem. We traverse the string and then if we encounter opening braces (‘(‘ or ‘{‘ or ‘[‘) we push into the stack. […]
Stack: Delete the middle element from the stack.
Problem Statement: You are given a stack, you need to delete the middle element from it. You should delete the middle element without using any other data structure. Example Input : Stack[] = [1, 2, 3, 4, 5] Output : Stack[] = [1, 2, 4, 5] Solution This can be done with the help of […]
Implement two stacks in an array
Problem Statement: You need to create a data structure called two_stacks that represents 2 stacks. It should use only one array. Both stacks should use the same array to store the elements. Below are the functions to be created: push_1(int x) -> should push element ‘x’ into first stack push_2(int x) -> should push element […]
Backtracking: Get maximum sum in a matrix
Problem Statement: You are given an m*n matrix, each cell has an integer. You need to return the path with maximum sum. You can start at any cell and you may go L, R, up or down, but you cannot visit same cell twice. Example Input: [[0,6,0], [5,8,7], [0,9,0]] Output: 24 9 -> 8 -> […]
Backtracking: Partition to K Equal Sum Subsets
Problem Statement: You are given an integer array and an integer K, you need to return true if you are able to divide the Example Input: [4,3,2,3,5,2,1], k = 4 Output: true It is possible to divide into 4 sub array with equal sum as: (5), (1, 4), (2,3), (2,3) Solution In the recursive function […]
Backtracking: Return the number of queens possible in a chessboard
Problem Statement: You are given an n * n chessboard, you need to return the number of queens possible in the chess board. Example n = 4 Output = 2 You can place 2 queens such that they dont attack each other Input: 4 Output: [ [".Q..", // Solution 1 "…Q", "Q…", "..Q."], ["..Q.", // […]
Backtracking: Get the sequential digits from the given range
Problem Statement: You are given 2 values, low, high. You need to find the sequential digits, where one number is more than the previous digit. You need to return the result in sorted order. Example Input: low = 100, high = 300 Output: [123,234] Solution We will use backtracking in the solution. We need the […]
Backtracking: Letter case permutation
Problem Statement: You are given a string, you need to transform every letter individually to be lowercase or uppercase to create another string. Example Input: “a1b” Output: “a1b”, “A1b”, “a1B”, “A1B” Solution We can solve this problem by using DFS method. Explanations is as below: a1b2 i=0 = a, as it is a letter, we […]