 Hi guys,
I have been practicing leetcode problem for facebook interview. I came across quite a bit of interesting problems on their forum. I wish to make 2 threads a week for 2 problems. Today, I want to share this problem and hope to discuss this problem with you guys Problem statement:
Define amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
Example 1: 0, 1, 2, 3
Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.
Example 2: 1, 0 , 0
Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one

1 Like

The naive solution is O(n^2). We can do it in O(n).
My idea is for each number in the original array, compute the range that index 0 can be placed at to make this number amazing.
For example:
array = [4,5,3,2,1]
intervals =[[1, 1], [], [3, 4], [0, 1], [4, 4], [0, 3]]

Then, I will find the index that maximize the number of overlapping. Here we have to be a bit careful, because ending still count as an interval. The result is putting 0 at 1.
The overall runtime is O(n) since we know the maximum and minimum in our array.

Summary
``````def maxOverlapping(intervals,start,stop):
dictionary = {i:[0,0] for i in range(start,stop)}
countOverlapping = 0
res = None
maxOverlap = 0

for startIntewqrval,stopInterval in intervals:
dictionary[startIntewqrval]+= 1
dictionary[stopInterval]+= 1

for i in range(start,stop):
countOverlapping+= dictionary[i]
if countOverlapping > maxOverlap:
maxOverlap = countOverlapping
res = i
countOverlapping-= dictionary[i]

return res
``````

`

``````def computeIntervals(array):
size = len(array)
intervals = []
for index,num in enumerate(array):
if num < size:
if index >= num: # itself is a good one
intervals.append([0,index-num])
if index<size-1:
intervals.append([index+1,size-1])
else: # if index < num, we have to shift 0 to left, which means our 0 have to be from the right
# have to shift 0 to the left the amount of num-index,
start = index+1
# we check how many to the right can we do it, basically
stop = size - (num-index)
intervals.append([start,stop])
print (intervals)
return intervals        `
``````