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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Most Visited Sector in a Circular Track

Difficulty: Easy

Problem Description

Given an integer n and an integer array rounds, we have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The i-th round starts at sector rounds[i - 1] and ends at sector rounds[i]. The task is to return an array of the most visited sectors sorted in ascending order.

Key Insights

  • The track is circular, so after reaching the last sector, the next sector is the first one.
  • We need to count the number of visits to each sector during the rounds.
  • Sectors can be visited multiple times within a round, especially if the start sector is greater than the end sector.

Space and Time Complexity

Time Complexity: O(m + n)
Space Complexity: O(n)

Solution

To solve this problem, we can use an array to count the visits to each sector. We will iterate through the rounds to determine the sectors visited in each round. For each round, we will handle the circular nature of the track by incrementing the sector index and wrapping around when necessary. Finally, we will find the maximum visit count and return all sectors that have that count.

Code Solutions

def most_visited(n, rounds):
    visit_count = [0] * (n + 1)  # Initialize visit counts for each sector

    # Iterate through the rounds
    for i in range(len(rounds) - 1):
        start = rounds[i]
        end = rounds[i + 1]

        # Handle the circular track visit counts
        if start <= end:
            for j in range(start, end + 1):
                visit_count[j] += 1
        else:
            for j in range(start, n + 1):
                visit_count[j] += 1
            for j in range(1, end + 1):
                visit_count[j] += 1

    # Find the maximum visit count
    max_visits = max(visit_count)
    return [i for i in range(1, n + 1) if visit_count[i] == max_visits]
← Back to All Questions