Summary: This problem is similar to range searching e.g. given entry and exit times of people find max number of people in a room, or given birth and death years of people, find a year in which max number of people were alive. Time complexity O(n)

Details:

First find the start and end points for each number, i.e. the range of indexes for which the number remains an amazing number. I skip the numbers greater than nums length and for each index value I start the with the next index because starting from it will indeed make the value an amazing number. while searching for range of amazing number if the index value is greater than len(nums) I break the range into two -- first one ends at len(nums)-1 and second begins from 0 till the end where the number ceases to become amazing.

Create an index array to keep a running count of maximum range overlap, iterate over intervals(ranges) and increment overlap value by 1 when see a start value and decrement for end value. Compute the running count by iterating over index list and return index corresponding to max overlap count.

class Interval(object):
def __init__(self, s=0, e=0):
self.start = s
self.end = e
def amazingNumber(nums):
intervals = []
for i, v in enumerate(nums):
if v > len(nums)-1: continue
start = i + 1
nextp = i+1 +len(nums)-1-nums[i]
if nextp > len(nums)-1 and start > len(nums)-1:
start = 0
end = nextp - len(nums)
interval = Interval(start, end)
intervals.append(interval)
elif nextp > len(nums)-1:
end = len(nums)-1
interval = Interval(start, end)
intervals.append(interval)
start = 0
end = nextp - len(nums)
interval = Interval(start, end)
intervals.append(interval)
else:
interval = Interval(start, nextp)
intervals.append(interval)
return findindex(intervals,len(nums))
def findindex(intervals, n):
idxlist = [0]*n
for i in intervals:
idxlist[i.start] += 1
if i.end+1 < n:
idxlist[i.end+1] -= 1
maxcnt, maxidx = 0, None
for i, v in enumerate(idxlist):
if v > maxcnt:
maxcnt = v
maxidx = i
if i+1 < n:
idxlist[i+1] += v
return maxidx
if __name__ == "__main__":
nums = [1, 0, 0] # 1
print amazingNumber(nums)
nums = [0, 1, 2, 3] # 0
print amazingNumber(nums)
nums = [5, 3, 8, 7, 2] # 2
print amazingNumber(nums)
nums = [4, 0, 1, 2, -1] #1
print amazingNumber(nums)
nums = [1, 2, 3, 4, 5, 1, 2, 9, 10, 11, 1, 2, 3, 4, 5, 6] #9
print amazingNumber(nums)
nums = [0, 0, 0, 0, 0] #0
print amazingNumber(nums)
nums = [1, 2, 3, 4, 5, 6, 7] #6
print amazingNumber(nums)
nums = [3, 5, 2, 4, 1, 0] #2
print amazingNumber(nums)
nums = [4, 0, 1, 2, -1] #2
print amazingNumber(nums)