public String simplifyPath(String path) {
String[] strs = path.split("/");
Stack<String> stack = new Stack<>();
for (int i = 1; i < strs.length; i++) {
if (strs[i].equals("..") && !stack.isEmpty()) {
stack.pop();
} else if (!strs[i].equals(".")
&& !strs[i].equals("..")
&& !strs[i].equals("")) {
stack.add(strs[i]);
}
}
StringBuilder sb = new StringBuilder("/");
for (String s : stack) {
sb.append(s).append("/");
}
return sb.length() != 1
? sb.deleteCharAt(sb.length() - 1).toString()
: sb.toString();
}
Next Greater Element
Find the next greater element in array, if no such element, return -1.
Pointer move from end to beginning, use a stack to store all element, but pop values which are smaller than the current value, this way we can keep a non-increasing sequence.
T: O(n) S: O(n)
public int[] nextGreaterElement(int[] nums) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
stack.pop();
}
res[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
stack.add(i);
}
return res;
}
Before add new element. Add the previous min to the stack.
int min = Integer.MAX_VALUE;
Stack<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
if (x <= min) {
stack.add(min);
min = x;
}
stack.add(x);
}
public void pop() {
int pop = stack.pop();
if (pop == min) {
min = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minstack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.minstack or x <= self.minstack[-1]:
self.minstack.append(x)
def pop(self) -> None:
pop = self.stack.pop()
if self.minstack and self.minstack[-1] == pop:
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minstack[-1]
Use two stacks to flip to get queue.
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
self.s1.append(x)
def pop(self) -> int:
if self.empty():
return None
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
def peek(self) -> int:
if self.empty():
return None
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
def empty(self) -> bool:
return not self.s1 and not self.s2
Loop over the token strings and add to a stack if it is a number. Alternatively run operation if it is an operator.
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String t : tokens) {
if ((t.equals("+") || t.equals("/") || t.equals("*") || t.equals("-")) && !stack.isEmpty()) {
int a = stack.pop();
int b = stack.pop();
if (t.equals("+")) {
stack.push(a + b);
} else if (t.equals("-")) {
stack.push(b - a);
} else if (t.equals("/")) {
stack.push(b / a);
} else if (t.equals("*")) {
stack.push(a * b);
}
} else {
stack.add(Integer.valueOf(t));
}
}
return stack.pop();
}
Use two stacks, one to store result and the other one store numbers.
meet "[", add to stack and reset current elements
meet "]", pop from stack and aggregate results
public String decodeString(String s) {
Stack<String> stack = new Stack<>();
Stack<Integer> nstack = new Stack<>();
String res = "";
int num = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (Character.isLetter(c)) {
res += c;
} else if (c == '[') {
stack.add(res);
nstack.add(num);
num = 0;
res = "";
} else if (c == ']' && !stack.isEmpty() && !nstack.isEmpty()) {
StringBuilder sb = new StringBuilder(stack.pop());
int n = nstack.pop();
for (int k = 0; k < n; k++) {
sb.append(res);
}
res = sb.toString();
}
}
return res;
}
Same as the problem above. Answer is the distance between peek value and current index.
T: O(n) S: O(n)
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[T.length];
for (int i = T.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
stack.pop();
}
res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
stack.add(i);
}
return res;
}
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = []
res = []
for i in range(len(T) - 1, -1, -1):
while stack and T[stack[-1]] <= T[i]:
stack.pop()
if stack:
res.insert(0, stack[-1] - i)
else:
res.insert(0, 0)
stack.append(i)
return res
Refer to as Next Greater Element.
T: O(n) S: O(n)
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for (int i = nums2.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums2[stack.peek()] <= nums2[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
map.put(nums2[i], nums2[stack.peek()]);
}
stack.add(i);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
if (map.get(nums1[i]) != null) {
res[i] = map.get(nums1[i]);
} else {
res[i] = -1;
}
}
return res;
}
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack = []
dic = {}
for i in range(len(nums2) - 1, -1, -1):
while stack and stack[-1] < nums2[i]:
stack.pop()
if stack:
dic[nums2[i]] = stack[-1]
stack.append(nums2[i])
res = []
for i in range(len(nums1)):
if nums1[i] in dic:
res.append(dic[nums1[i]])
else:
res.append(-1)
return res
Since it is a circular array, one way is looping over the array twice, and maintain the stack and result array. While looping, mod i by n (i % n) as it points to the position on the current array.
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
Stack<Integer> stack = new Stack<>();
int[] res = new int[n];
for (int i = n * 2 - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i % n]) {
stack.pop();
}
res[i % n] = stack.isEmpty() ? -1 : nums[stack.peek() % n];
stack.add(i % n);
}
return res;
}
If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.
If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.
For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)
Algorithm:
Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.
Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.
Swap the above found two digits, we get 536974 in above example.
public int nextGreaterElement(int n) {
char[] nums = String.valueOf(n).toCharArray();
// 1.
int i = nums.length - 1;
for (; i > 0; i--) {
if (nums[i - 1] < nums[i]) break;
}
if (i == 0) return -1;
// 2
int x = nums[i - 1], j = i + 1, smallest = i;
while (j < nums.length) {
if (nums[j] > x && nums[smallest] >= nums[j]) smallest = j;
j++;
}
// 3
char temp = nums[smallest];
nums[smallest] = nums[i - 1];
nums[i - 1] = temp;
Arrays.sort(nums, i , nums.length);
long val = Long.parseLong(new String(nums));
return (val <= Integer.MAX_VALUE) ? (int)val : -1;
}
Use stack to add element when it is positive. Otherwise, keep popping the previous one when it is smaller than opposite of current, for eg. [2, 3, -10].
When current and previous are exactly opposite, such as [8, -8], only pop. When the previous is negative, continue push current, eg [-2, -1]
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int a : asteroids) {
if (a > 0) { // a > 0
stack.push(a);
} else { // a > 0
while (!stack.isEmpty() && stack.peek() < -a && stack.peek() > 0) {
stack.pop();
}
if (!stack.isEmpty() && stack.peek() == -a) {
stack.pop();
} else if (stack.isEmpty() || stack.peek() < 0) {
stack.push(a);
}
}
}
int[] res = new int[stack.size()];
int i = 0;
for (int n : stack) {
res[i++] = n;
}
return res;
}
Same as 556 above:
find the first increase element i from the right
find the first element larger than i from the right
swap i and j, reverse from i + 1 to end.
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) j--;
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
}
Solution1: Sort and find the start and end of the difference: O(nlogn)
public int findUnsortedSubarray(int[] nums) {
int[] snums = nums.clone();
Arrays.sort(nums);
int start = nums.length, end = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != snums[i]) {
start = Math.min(start, i);
end = Math.max(end, i);
}
}
if (end - start >= 0) {
return end - start + 1;
}
return 0;
}
Solution1: Use Monotonic stack to find the smallest start index where it violates the increasing trend. Also find the largest end where it violates the decreasing trend from the back. O(n)
public int findUnsortedSubarray(int[] nums) {
Stack<Integer> stack = new Stack<>();
int start = nums.length, end = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
start = Math.min(start, stack.pop());
}
stack.add(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
end = Math.max(end, stack.pop());
}
stack.add(i);
}
if (end - start <= 0) return 0;
return end - start + 1;
}
Maintain a deque while going through Keep only the indexes of elements from the current sliding window. Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
// initiate a result array with size n - k + 1
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// pop First when your first index element exceeds window
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// keep popping from last when your last element is smaller or equals current num,
// which means all element in the deque is larger than current
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// add current number from last
deque.addLast(i);
// add to result when window size reach k
if (i >= k - 1) {
// everything in deque are large elements. The first is always the max since the deque is monotonic.
res[i - k + 1] = nums[deque.peekFirst()];
}
}
return res;
}
given an n x m matrix and a value k, find minimum values for all sub-matrixes of size k
First for each column calculate the minimum for each sliding window(vertical direction) of k
Then for each pair of row having col width k, run sliding window (horizontal direction) of k on col data from 1.
Similar as the question above. It needs to calculate the difference of an interval. Two deque is needed to get the min and max of the interval. The last element is always the largest or smallest. That:
In min deque, when the last element is larger than current element, poll last
in max deque, when the last element is smaller than current element, poll last
when the element reach to the current element, pop first
As well as maintain the longest interval.
public int longestSubarray(int[] nums, int limit) {
Deque<Integer> minD = new LinkedList<>();
Deque<Integer> maxD = new LinkedList<>();
int res = Integer.MIN_VALUE;
int i = 0, j;
for (j = 0; j < nums.length; j++) {
while (!minD.isEmpty() && nums[j] < minD.peekLast()) {
minD.pollLast();
}
while (!maxD.isEmpty() && nums[j] > maxD.peekLast()) {
maxD.pollLast();
}
minD.add(nums[j]);
maxD.add(nums[j]);
if (Math.abs(minD.peek() - maxD.peek()) > limit) {
if (minD.peek() == nums[i]) minD.poll();
if (maxD.peek() == nums[i]) maxD.poll();
i++;
}
}
return j - i;
}
Maintain an increasing monotonic stack. Add a -1 to the stack for easier calculation. When encounter a decreasing element, pop the stack and calculate the max before current element. At the end, clear all elements in the stack and calculate the left over areas.
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < n; i++) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
max = Math.max(max,
heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.add(i);
}
while (stack.peek() != -1) {
max = Math.max(max,
heights[stack.pop()] * (n - stack.peek() - 1));
}
return max;
}
Use a stack and only keep the elements larger than the new element, as well as aggregate the counts less or equals to the new element.
class StockSpanner {
Stack<int[]> stack;
public StockSpanner() {
stack = new Stack<>();
}
public int next(int price) {
int count = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
count += stack.pop()[1];
}
stack.add(new int[]{price, count});
return count;
}
}
Use a stack to store previous numbers. Use an operator character to store the last operator. When meet new operator or reach the last digit, perform the operation, aggregate results at last.
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0;
char operator = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
}
if ("+-/*".indexOf(c) != -1 || i == s.length() - 1) {
if (operator == '+') {
stack.add(num);
} else if (operator == '-') {
stack.add(num * -1);
} else if (operator == '*') {
stack.add(stack.pop() * num);
} else if (operator == '/') {
stack.add(stack.pop() / num);
}
num = 0;
operator = c;
}
}
int res = 0;
while (!stack.isEmpty()) res += stack.pop();
return res;
}
def calculate(self, s: str) -> int:
stack = []
op = '+'
val = 0
for i in range(len(s)):
c = s[i]
if c.isdigit():
val = val * 10 + int(c)
if c == '+' or c == '-' or c == '*' or c == '/' or i == len(s) - 1:
if op == '+':
stack.append(val)
elif op == '-':
stack.append(-val)
elif op == '*':
stack.append(val * stack.pop())
elif op == '/':
stack.append(int(stack.pop() / val))
val = 0
op = c
res = 0
for n in stack:
res += n
return res
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0, res = 0, sign = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
} else if (c == '+') {
res += sign * num;
sign = 1;
num = 0;
} else if (c == '-') {
res += sign * num;
sign = -1;
num = 0;
} else if (c == '(') {
stack.add(res);
stack.add(sign);
res = 0;
sign = 1;
} else if (c == ')' && stack.size() > 1) {
res += sign * num;
num = 0;
res *= stack.pop();
res += stack.pop();
}
}
res += sign * num;
return res;
}
public int calculate(String s) {
Queue<Character> q = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c != ' ') {
q.offer(c);
}
}
q.offer(' '); // placeholder
return helper(q);
}
private int helper(Queue<Character> q) {
int val = 0;
int prev = 0, res = 0;
char prevOp = '+';
while (!q.isEmpty()) {
char c = q.poll();
if (c >= '0' && c <= '9') {
val = val * 10 + c - '0';
} else if (c == '(') {
val = helper(q);
} else {
switch (prevOp) { // Note: prevOp, not current c
case '+':
res += prev;
prev = val;
break;
case '-':
res += prev;
prev = -val;
break;
case '*':
prev *= val;
break;
case '/':
prev /= val;
break;
}
if (c == ')') break;
val = 0;
prevOp = c;
}
}
return res + prev;
}
Store map: element : count to stack. When meeting brackets, deal with the maps in stack. Otherwise, store elements and their count to map.
public String countOfAtoms(String s) {
Stack<Map<String, Integer>> stack = new Stack<>();
Map<String, Integer> map = new HashMap<>();
int i = 0, n = s.length();
while (i < n) {
char c = s.charAt(i);
i++;
if (c == '(') {
stack.push(map);
map = new HashMap<>();
} else if (c == ')') {
int val = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
val = val * 10 + (s.charAt(i++) - '0');
}
if (val == 0) val = 1;
if (!stack.isEmpty()) {
Map<String, Integer> temp = map;
map = stack.pop();
for (String key : temp.keySet()) {
map.put(key, map.getOrDefault(key, 0) + temp.get(key) * val);
}
}
} else {
int start = i - 1;
while (i < n && Character.isLowerCase(s.charAt(i))) {
i++;
}
String curt = s.substring(start, i);
int val = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
val = val * 10 + (s.charAt(i++) - '0');
}
if (val == 0) val = 1;
map.put(curt, map.getOrDefault(curt, 0) + val);
}
}
StringBuilder sb = new StringBuilder();
List<String> list= new ArrayList<>(map.keySet());
Collections.sort(list);
for(String key: list){
sb.append(key);
if(map.get(key)>1) sb.append(map.get(key));
}
return sb.toString();
}
Constrained Subsequence Sum
Find the smallest consecutive two values to merge to get min cost. When encounter a number is larger than peek, calculate the product of peek (smaller number) and n or the one before peek. Later cumulate all products.
public int mctFromLeafValues(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
Stack<Integer> stack = new Stack<>();
for (int n : arr) {
while (!stack.isEmpty() && n >= stack.peek()) {
int mid = stack.pop();
if (stack.isEmpty()) {
res += mid * n;
} else {
res += mid * Math.min(stack.peek(), n);
}
}
stack.add(n);
}
while (stack.size() >= 2) {
res += stack.pop() * stack.peek();
}
return res;
}
public String reverseParentheses(String s) {
if(s.length() == 0) return "";
int begin = 0, end = 0;
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '(') begin = i;
if(s.charAt(i) == ')') {
end = i;
StringBuilder sb = new StringBuilder(s.substring(begin+1, end));
return reverseParentheses(s.substring(0, begin) + sb.reverse().toString() + s.substring(end+1));
}
}
return s;
}
public String removeDuplicates(String S) {
Stack<Character> stack = new Stack<>();
for (char c : S.toCharArray()) {
if (!stack.isEmpty()
&& stack.peek() == c) {
stack.pop();
} else {
stack.add(c);
}
}
StringBuilder sb = new StringBuilder();
for (char c : stack) {
sb.append(c);
}
return sb.toString();
}
Save the consecutive character lengths in a stack. When see the same char, and char length equals to k, remove the substring.
public String removeDuplicates(String s, int k) {
Stack<Integer> stack = new Stack<>();
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < sb.length(); i++) {
if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) { // new char
stack.push(1);
} else { // same char
int incre = stack.pop() + 1;
if (incre == k) {
sb.delete(i - k + 1, i + 1);
i -= k;
} else {
stack.add(incre);
}
}
}
return sb.toString();
}
Sum of Subarray Minimums
Online Stock Span
Score of Parentheses
Next Greater Element II
Next Greater Element I
Largest Rectangle in Histogram
Trapping Rain Water
Max Value of Equation
Simulate the stack push and pop operations, validate the sequence in popped array and pop in the stack.
public boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed == null || popped == null || pushed.length != popped.length) {
return false;
}
int j = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
while (!stack.isEmpty() && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return j == popped.length;
}