Maximize Distance to Closest Person - Practice Coding Problems

Maximize Distance to Closest Person - Problem

Array Medium

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the i-th seat, and seats[i] = 0 represents that the i-th seat is empty (0-indexed).

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. Return that maximum distance to the closest person.

Input & Output

Example 1 — Basic Gap

$ Input: seats = [1,0,0,0,1,0,1]

› Output: 2

💡 Note: The largest gap is between positions 0 and 4. Sitting at position 2 gives distance 2 to the closest person.

Example 2 — End Position

$ Input: seats = [1,0,0,0]

› Output: 3

💡 Note: Sitting at the rightmost position (index 3) gives distance 3 to the person at index 0.

Example 3 — Multiple Gaps

$ Input: seats = [0,1,0,0,0,1,0]

› Output: 2

💡 Note: The gap between positions 1 and 5 has length 3, so sitting in the middle gives distance 2.

Constraints

2 ≤ seats.length ≤ 2 × 10⁴
seats[i] is 0 or 1
At least one seat is empty
At least one seat is occupied

Visualization

Tap to expand

Understanding the Visualization

Input

Array of seats with 1=occupied, 0=empty

Process

Find position that maximizes distance to closest person

Output

Return the maximum possible distance

Key Takeaway

🎯 Key Insight: The optimal seat is either at the ends or in the middle of the largest gap between people

Asked in

G Google 25 a Amazon 20 f Facebook 15

The key insight is that the maximum distance occurs either at the ends or in the middle of the largest gap between consecutive people. Best approach is Gap Analysis with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Gap Analysis	O(n)	O(1)	Find largest gap between consecutive people and check ends
Two Pass Distance Calculation	O(n)	O(n)	Pre-calculate distances to nearest person from left and right
Brute Force	O(n²)	O(1)	For each empty seat, find distance to closest occupied seat

Gap Analysis — Algorithm Steps

Step 1: Find all occupied seat positions
Step 2: Check distance at both ends
Step 3: Find largest gap between consecutive people and check middle

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Occupied

Identify all seats with people

Check Ends

Calculate distance from edges to first/last person

Check Gaps

Find middle of largest gap between people

Code -

solution.c — C

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

int solution(int* seats, int n) {
    int occupied[100];
    int occupiedCount = 0;
    
    // Find all occupied positions
    for (int i = 0; i < n; i++) {
        if (seats[i] == 1) {
            occupied[occupiedCount++] = i;
        }
    }
    
    int maxDist = 0;
    
    // Check left end
    if (occupied[0] > 0) {
        if (occupied[0] > maxDist) {
            maxDist = occupied[0];
        }
    }
    
    // Check right end
    if (occupied[occupiedCount - 1] < n - 1) {
        int rightDist = n - 1 - occupied[occupiedCount - 1];
        if (rightDist > maxDist) {
            maxDist = rightDist;
        }
    }
    
    // Check gaps between consecutive occupied seats
    for (int i = 1; i < occupiedCount; i++) {
        int gap = occupied[i] - occupied[i - 1] - 1;
        if (gap > 0) {
            int gapDist = gap / 2;
            if (gapDist > maxDist) {
                maxDist = gapDist;
            }
        }
    }
    
    return maxDist;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int seats[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        seats[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(seats, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find occupied positions, then check gaps

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track positions and maximum distance

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 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

Gap Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler