Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node p is the node with the smallest key greater than p.val. Example 1 Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2 Input: root = [5,3,6,2,4,null,null,1], p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.

by lek tin in "algorithm" access_time 2-min read

Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax. push(x) – Push element x onto stack. pop() – Remove the element on top of the stack and return it. top() – Get the element on the top. peekMax() – Retrieve the maximum element in the stack. popMax() – Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

by lek tin in "algorithm" access_time 3-min read

Maximum Frequency Stack

Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack has two functions: push(int x), which pushes an integer x onto the stack. pop(), which removes and returns the most frequent element in the stack. If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned. Example 1 Input: ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] Output: [null,null,null,null,null,null,null,5,7,5,4] Explanation: After making six .

by lek tin in "algorithm" access_time 2-min read

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. Example: Input: [2,1,5,6,2,3] Output: 10 Solution: Push height into the stack in ascending order. When we encounter a height that is shorter than te top of the stack, we start to calculate area by popping heights out of the stack.

by lek tin in "algorithm" access_time 1-min read

Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list – whose elements may also be integers or other lists. Example 1 Input: [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,1,2,1,1]`. Example 2 Input: [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,4,6]`.

by lek tin in "algorithm" access_time 4-min read

Valid Parentheses

Given a string containing just the characters ‘(', ‘)', ‘{', ‘}', ‘[’ and ‘]', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1 Input: "()" Output: true Example 2 Input: "()[]{}" Output: true Example 3 Input: "(]" Output: false Example 4 Input: "([)]" Output: false Example 5 Input: "{[]}" Output: true Solution: class Solution { public boolean isValid(String s) { HashMap<Character, Character> charMap = new HashMap<>(); charMap.

by lek tin in "algorithm" access_time 1-min read

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Example MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.

by lek tin in "algorithm" access_time 1-min read

Add Binary

Given two binary strings, return their sum (also a binary string). The input strings are both non-empty and contains only characters 1 or 0. Example 1 Input: a = "11", b = "1" Output: "100" Example 2 Input: a = "1010", b = "1011" Output: "10101" Solution class Solution: def addBinary(self, a, b): """ :type a: str :type b: str :rtype: str """ result = [] carry = 0 i = len(a)-1 j = len(b)-1 while carry or i >= 0 or j >= 0: total = carry if i >= 0: total += int(a[i]) i -= 1 if j >= 0: total += int(b[j]) j -= 1 result.

by lek tin in "algorithm" access_time 1-min read