Intuition My first thought was to sort the array, and return the first element where count < citations[i]. However this proved to be wrong, since this would return the first element, and after sorting the array we want to return the last element where count < citations[i] is True. Approach Sort the array, then iterate over it storing the count where count < citations[i]. Complexity Time complexity: O(n log n) since we have the sort function ...
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) ...
Intuition Split words into a array, build new string using .pop() Approach First split the text by (spaces), then pop the last element, strip whitespaces and concatenete at the end of the new string. Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def reverseWords(self, s): """ :type s: str :rtype: str """ words = s.strip().split(' ') reversed = '' while len(words) > 0: w = words.pop().strip() if len(w) == 0: continue reversed += w + (' ' if len(words) > 0 else '') return reversed
Intuition First thought was to use a dictionary(hashmap) to keep track of the items, however the random is an issue, since we need to convert the dictionary into a list to get a random item. Approach In order to achieve time complexity near O(1) we need to use two structures. One dictionary for fast deletion, and a list for fast randomization. The trick that makes the possible is to remove an element from a list in O(1), and this is achieved by u ...