I was solving cloudyday problem on hackerrank:

City has many towns. p is an array of population of n towns. x is an array of location of towns on 1 dimensional array (thus a numeric location). y is an array of location of clouds. r is an array of extent or breadth of clouds. Population in city under cloud is said to be in dark, rest of population are said to be sunny region. i-th cloud covers every town with location in the range [y[i]-r[i],y[i] r[i]]. City has a technology that can burst only single cloud. Write function to return max population that can be ensured to be in sunny region by bursting any single cloud.

I come across following solution with while loop. The solution did not had any comments. So I tried to figure out the logic and put it in comments myself. To cross check my understanding, I tried to re-write while loop as for loops as shown in comments:

from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
    towns = sorted(towns) # sort by index-0 i.e. location
    cloud_start = sorted(cloud_start)
    cloud_end = sorted(cloud_end)

    cloud_start_j = 0
    cloud_end_k = 0
    clouds = set()
 
    d = defaultdict(int)  # cloud index : total population sunnied if burst
    free = 0
    for town_i in range(len(towns)):
        town_x = towns[town_i][0]

        # find all clouds that occupy this town

        # add all clouds that start before town in clouds set

        while cloud_start_j < len(cloud_start) and cloud_start[cloud_start_j][0] <= town_x:
            clouds.add(cloud_start[cloud_start_j][1])
            cloud_start_j  = 1

        # for cloud_start_j in range(len(cloud_start)):
        #     if cloud_start[cloud_start_j][0] <= town_x:
        #         clouds.add(cloud_start[cloud_start_j][1])
        #     else: break

        # remove all clouds that end before town from clouds set

        while cloud_end_k < len(cloud_end) and cloud_end[cloud_end_k][0] < town_x:
            clouds.remove(cloud_end[cloud_end_k][1])
            cloud_end_k  = 1

        # for cloud_end_k in range(len(cloud_end)):
        #     if cloud_end[cloud_end_k][0] < town_x:
        #         clouds.remove(cloud_end[cloud_end_k][1])
        #     else: break

        if len(clouds) == 1: # if there are more than 1 cloud at location, ignore location
            # towns[town_i][2] = list(clouds)[0] # list of clouds at town location (unused)
            d[list(clouds)[0]]  = towns[town_i][1] # add to population of this cloud 
        elif len(clouds) == 0: 
            free  = towns[town_i][1]

    return max(d.values(), default=0)   free

def driver(n, p, x, m, y, r):
    #n = int(input().strip())
    #p = [int(x) for x in input().strip().split()]
    #x = [int(x) for x in input().strip().split()]
    towns = [[xi, pi, -1] for xi, pi in zip(x, p)] # [location, population, list of clouds at location (unused)]
    #m = int(input().strip())
    #y = [int(x) for x in input().strip().split()]
    #r = [int(x) for x in input().strip().split()]
    cloud_start = [[y[i]-r[i], i] for i in range(m)] # [cloud-start, index]
    cloud_end = [[y[i] r[i], i] for i in range(m)] # [cloud-end, index]
    result = maximumPeople(towns, cloud_start, cloud_end)
    print(result)

driver(3, [15,26,100,40], [3,5,100,29], 2, [4,31], [1,2])   # 141
driver(3, [15,15,100,40], [3,5,100,29], 2, [4,31], [1,2]) # 140
driver(2, [10,100], [5,100], 1, [4], [1]) # 110

The problem is that the given solution with while loops passes all test cases, but if you uncomment for loops and comment while loops, it timeouts in some test cases. Did I make mistake in translating while loops to for loops or my understanding of what those while loops are doing is incorrect?

CodePudding user response：

The translated for loops are not exactly equivalent to the while ones. The issue is where you start iterating from in for VS while.

• In the for loops - you always iterate starting from 0 (you reset cloud_start_j and cloud_end_k) for each iteration of the outer loop (over towns).
• In while loops however, you "remember" your old location, and don't go back to it.

This might in some cases result in O(n^2) time complexity for the for loops solution, while while loops are guaranteed to iterate over each element at most once, resulting in O(nlogn) (sorting at the beginning).