Wonder what the runtime is, considering the difference between j and i can be as large as the entire pos list, seems like a O(n^2) solution because of the assignment slice pos[i:j]
livelearn
@livelearn
Posts made by livelearn

RE: Python solution

RE: I think this problem can not be solved in O(n) time?
I actually agree, no idea how you can come up with a O(k) solution. Also all the python solutions are O(nlogn), haven't seen one with O(n) because you need to sort elements with the same frequencies lexicographically. If you use bucket sort or quickselect that would give you a solution with the same frequencies, but still wouldn't pass a case like this ["aaa","aa","a"]1 without sorting.

RE: Easy and Concise 5lines Python/Java Solution
@YJL1228 Still not O(n). You're copying the list over using the concatenation and doing this for all indexes

RE: Python O( N ) solution. easy to understand
@steven5 Where is he doing that?

Simple Python iterative DFS
def getImportance(self, employees, id): """ :type employees: Employee :type id: int :rtype: int """ d={e.id:e for e in employees} ret=0 stk=[d[id]] #we can go straight to the employee since we have a map already while stk: top=stk.pop() ret+=top.importance for n in top.subordinates: stk.append(d[n]) return ret

RE: Why the answer of [[2,1],[3,1],[4,2],[1,4]] is [2,1] ?
Because it would still have a cycle and that's the whole point of the question...

RE: Python solution with detailed explanation
Faster to use a 2d matrix for storage rather than a dictionary