User123
BAN USER
Comments (7)
Reputation 55
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
5
of 5 vote
Can be solved by sorting the array, and then using two pointers to maintain a window and finding max length of the window.
1. Sort array - O(nlogn)
2. Maintain two pointers
start = 0, end = 0
ans = 0
while end < n:
if arr[end+1] - arr[start] <= 1:
end += 1
else:
start += 1
ans = max(ans, end - start + 1)
# also keep window track
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Since you have to collect all k cheese blocks, there are max k! ways to do this, which is worst case 10! ways.
- User123 July 26, 2015Thus for each value in this 10! you would need to do BFS from (0,0) to cheese1. Then BFS from cheese1 to cheese2 and so on.. You then take min of all such paths
For example for a smaller k=3, you can have
origin->c1->c2->c3->jerry
origin->c1->c3->c2->jerry
origin->c2->c1->c3->jerry
origin->c2->c3->c1->jerry
origin->c3->c1->c2->jerry
origin->c3->c2->c1->jerry
making it 3!= 6 ways to do so.
You can obviously memoise this and bring down the complexity to O(k^2) from O(k!)
(Or you can do bottom up by storing BFS min value for cheeses at any two points ci and cj)
So you would be doing k BFS, bringing the complexity to k*O(V+E)*k^2 = k^3*O(V+E)