Facebook| Phone Screen| Q1

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 :slight_smile:

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][0]+= 1
    dictionary[stopInterval][1]+= 1
        

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

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        `