Intuition Create a map os strings, group by it’s sorted version. Approach Create a map os strings, group by it’s sorted version. Complexity Time complexity: O(n logn) Space complexity: O(n) Code class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ _map = {} for s in strs: _sorted = "".join(sorted(s)) if _sorted in _map: _map[_sorted].append(s) else: _map[_sorted] = [s] return _map.values()
Intuition My thought was first going left to right checking both neighbours. For example, for [1,2,3,4] would work perfectly. However it’s not possible to solve this in one pass checking both neighbours. We need to use a two pass approach, LTR, RTL. To visualize better the problem, using [1,2,3,4] let’s see how many candies LTR and RTL would give for each children: LTR [1,2,3,4] -> [1,2,3,4] since it's always increase each children get's one more candy than the previous one. RTL [1,2,3,4] -> [1,1,1,1] From RTL perspective, it's always decreasing, so all children get's one. In this case the correct solution is [1,2,3,4] ...
Intuition Another way to read the problem is: find if all s characters are present in t, in the same order. It doesn’t have to be consecutive. We need to keep two pointers: One for the string t One for the string s We got loop through the string t, and if t[tPointer] == s[iPointer], we increase both. If t[tPointer] != s[iPointer], will increase just tPointer. At the end if iPointer==len(s) we reach end of s, we are good, return True This will be solved in time O(n) and space(1), since is one pass and we don’t use additional structures other than the pointers. ...
Intuition Find the first station where we have a net positive tank. However that solution is not optimized. Approach After reading the editorial, it’s possible to complete the solution with optimal time complexity using the greedy approach (one pass). The idea is to go iterate over the elements and whenever we find a net negative level we restart the segment and keep the next array index as starting index. Also, while going over the elements we need to keep a the final tank level. If the final tank level is negative, then there’s no solution. ...
Intuition Create a map with the integer and the roman value of that integer, loop through the reversed array, treating the special cases (4 and 9) Approach Conver the number to a string then reverse it. Once reversed, create a base variable to store whether the digit is 1s, 10s, 100s, 1000s. Loop through each digit (d) getting the equivalent in roman: if d > 9 or d>4, return map[1*base] + map[(d+1)*base] if d > 5, store map[5*base], decrease d while d > 0 concat map[1*base] return stored roman Complexity Time complexity: O(n) ...