Most Visited Sector in a Circular Track - Practice Coding Problems

Most Visited Sector in a Circular Track - Problem

Array Simulation Easy

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, and the marathon consists of m rounds.

The i-th round starts at sector rounds[i-1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1].

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, rounds = [1,3,1,2]

› Output: [1,2]

💡 Note: Marathon path: 1→2→3 (round 1), 3→4→1 (round 2), 1→2 (round 3). Sectors 1 and 2 are visited twice each, which is the maximum.

Example 2 — Wrap Around

$ Input: n = 2, rounds = [2,1,2,1,2]

› Output: [2]

💡 Note: All rounds start and end at sectors 1 or 2. Following the pattern, sector 2 gets visited most frequently.

Example 3 — Single Round

$ Input: n = 7, rounds = [1,3]

› Output: [1,2,3]

💡 Note: Only one round from 1 to 3, visiting sectors 1→2→3. All three sectors are visited once.

Constraints

2 ≤ n ≤ 10⁴
1 ≤ rounds.length ≤ 10⁵
rounds[i] is between 1 and n

Visualization

Tap to expand

Understanding the Visualization

Input

Circular track with n sectors and rounds array showing start/end of each round

Process

Track visits to each sector during the marathon rounds

Output

Return sectors with maximum visit count in ascending order

Key Takeaway

🎯 Key Insight: Only the start and end positions of the entire marathon determine the most visited sectors

Asked in

a Amazon 15 G Google 8

The key insight is that only the starting and ending sectors of the entire marathon matter for determining the most visited sectors. The optimal approach identifies the first start and last end, then returns sectors between them. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(m × n)	O(n)	Simulate every step of the marathon and count visits to each sector
Smart Observation	O(n)	O(1)	Only the start and end sectors matter, not the full circular path

Brute Force Simulation — Algorithm Steps

Step 1: Initialize visit counter for each sector
Step 2: For each round, simulate walking from start to end
Step 3: Count visits for each sector in the path
Step 4: Find maximum visit count and return those sectors

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Counters

Create array to count visits for each sector

Simulate Each Round

Walk step by step from start to end, counting visits

Find Maximum

Return sectors with highest visit count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int n, int* rounds, int roundsSize, int* returnSize) {
    int* count = (int*)calloc(n + 1, sizeof(int));
    
    for (int i = 0; i < roundsSize - 1; i++) {
        int start = rounds[i];
        int end = rounds[i + 1];
        
        int current = start;
        while (current != end) {
            count[current]++;
            current = current < n ? current + 1 : 1;
        }
        count[end]++;
    }
    
    int maxCount = 0;
    for (int i = 1; i <= n; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
        }
    }
    
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = 0;
    for (int i = 1; i <= n; i++) {
        if (count[i] == maxCount) {
            result[(*returnSize)++] = i;
        }
    }
    
    free(count);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %s", line);
    
    int rounds[100];
    int roundsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        rounds[roundsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(n, rounds, roundsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

For m rounds, each could visit up to n sectors

✓ Linear Growth

Space Complexity

O(n)

Array to count visits for n sectors

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

924 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler