42. Trapping Rain Water
Topic: Array, Two pointer, Stack
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
44. Wildcard Matching
Topic: String, DP, Backtracking, Greedy
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*‘.
- ’?’ Matches any single character.
- ‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence.
Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Input: s = "acdcb" p = "a*c?b" Output: false
76. Minimum Window Substring
Topic: Hash Table, Two pointer, String, Sliding window
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
- If there is no such window in S that covers all characters in T, return the empty string “”.
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
84. 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.
Input: [2,1,5,6,2,3] Output: 10