We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Visited Sector in a Circular Track

Number: 1682

Difficulty: Easy

Paid? No

Companies: Expedia

Problem Description

Given a circular track with n sectors labeled from 1 to n, a marathon is conducted over m rounds. The starting sector for the entire marathon is rounds[0], and each subsequent round ends at sectors given in the rounds array. The marathon always moves in a counter-clockwise direction following ascending order of sector numbers, wrapping around from n to 1 when necessary. The task is to return an array of the sectors that are visited the most, sorted in ascending order.

Key Insights

  • The journey is always in the counter-clockwise direction, meaning sectors are visited in increasing order and wrap from n back to 1.
  • The problem can be reduced to finding the sectors in the interval from the starting sector (rounds[0]) to the final sector (rounds[-1]) when traversing in the circular order.
  • If the final sector is greater than or equal to the starting sector, the answer is simply the sectors within that range.
  • If the final sector is less than the starting sector, the answer consists of two parts: from sector 1 to the final sector, and from the starting sector to n.
  • This observation avoids simulating all rounds and leverages the order property.

Space and Time Complexity

Time Complexity: O(n) - At most we traverse each sector once when constructing the result. Space Complexity: O(n) - The space required for the result and any auxiliary data required is linear in the number of sectors.

Solution

The solution leverages a simple observation about the circular nature of the track. Since the movement is always in one direction (counter-clockwise) and sectors are visited sequentially, the sectors that will be visited most are those in the continuous interval from the starting sector (rounds[0]) to the ending sector (rounds[-1]).

If rounds[-1] (the final sector) is greater than or equal to rounds[0] (the start), then the most visited sectors will simply be the continuous block from rounds[0] to rounds[-1]. Otherwise, if rounds[-1] is less, it implies a wrap-around, hence the answer includes sectors 1 to rounds[-1] and rounds[0] to n.

By avoiding simulation of all rounds, this approach runs in constant/linear time relative to n with minimal space overhead.

Code Solutions

# Python solution for Most Visited Sector in a Circular Track

def mostVisited(n, rounds):
    # Get start and end sectors from the rounds list
    start, end = rounds[0], rounds[-1]
    
    # If the endpoint is equal or comes after the start in the circular order,
    # simply generate the sectors in the interval.
    if end >= start:
        # Create list of sectors from start to end (inclusive)
        most_visited = [sector for sector in range(start, end + 1)]
    else:
        # Handle the wrap-around: sectors from 1 to end and from start to n.
        most_visited = [sector for sector in range(1, end + 1)] + [sector for sector in range(start, n + 1)]
    
    return most_visited

# Example usage:
print(mostVisited(4, [1,3,1,2]))  # Output: [1, 2]
← Back to All Questions