Minimum Number of Moves to Seat Everyone - Problem

There are n available seats and n students standing in a room. You are given an array seats of length n, where seats[i] is the position of the i^th seat. You are also given the array students of length n, where students[j] is the position of the j^th student.

You may perform the following move any number of times:

Increase or decrease the position of the i^th student by 1 (i.e., moving the i^th student from position x to x + 1 or x - 1)

Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.

Note: There may be multiple seats or students in the same position at the beginning.

Input & Output

Example 1 — Basic Case

$ Input: seats = [3,1,5], students = [2,7,4]

› Output: 4

💡 Note: After sorting: students=[2,4,7], seats=[1,3,5]. Moves: |2-1|+|4-3|+|7-5| = 1+1+2 = 4

Example 2 — Same Positions

$ Input: seats = [4,1,5,9], students = [1,3,2,6]

› Output: 7

💡 Note: After sorting: students=[1,2,3,6], seats=[1,4,5,9]. Moves: |1-1|+|2-4|+|3-5|+|6-9| = 0+2+2+3 = 7

Example 3 — Minimal Case

$ Input: seats = [2,2,6,6], students = [1,3,2,6]

› Output: 4

💡 Note: After sorting: students=[1,2,3,6], seats=[2,2,6,6]. Moves: |1-2|+|2-2|+|3-6|+|6-6| = 1+0+3+0 = 4

Constraints

n == seats.length == students.length
1 ≤ n ≤ 100
1 ≤ seats[i], students[j] ≤ 100

Visualization

Tap to expand

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that to minimize total moves, we should pair the i-th smallest student position with the i-th smallest seat position. This greedy approach works because any crossing assignments (where a smaller student goes to a larger seat while a larger student goes to a smaller seat) can always be uncrossed to reduce total moves. Best approach is Greedy Sort and Match with Time: O(n log n), Space: O(1).

Common Approaches

✓ Brute Force - Try All Permutations

⏱️ Time: O(n!) Space: O(n)

Try every possible way to assign n students to n seats and calculate the total moves for each assignment. Return the minimum.

Greedy Approach - Sort and Match

⏱️ Time: O(n log n) Space: O(1)

Sort both students and seats arrays, then greedily match the i-th smallest student position with the i-th smallest seat position. This minimizes total moves.

Brute Force - Try All Permutations — Algorithm Steps

Generate all permutations of seat assignments
For each permutation, calculate total Manhattan distance
Return the minimum total moves

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible ways to assign students to seats

Calculate Moves

For each assignment, sum up Manhattan distances

Find Minimum

Keep track of assignment with least total moves

Code -

solution.c — C

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

static int seats[100], students[100];
int minMoves;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int* seats, int* students, int* indices, int n, int start) {
    if (start == n) {
        int moves = 0;
        for (int i = 0; i < n; i++) {
            moves += abs(students[i] - seats[indices[i]]);
        }
        if (moves < minMoves) {
            minMoves = moves;
        }
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(&indices[start], &indices[i]);
        permute(seats, students, indices, n, start + 1);
        swap(&indices[start], &indices[i]);
    }
}

int solution(int* seats, int* students, int n) {
    minMoves = INT_MAX;  // Reset global variable
    int* indices = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }
    
    permute(seats, students, indices, n, 0);
    free(indices);
    return minMoves;
}

int parseArray(const char* str, int* arr) {
    int size = 0;
    const char* p = str;
    
    // Skip to opening bracket
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        // Skip whitespace and commas
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        // Parse number
        char* endptr;
        arr[size++] = (int)strtol(p, &endptr, 10);
        p = endptr;
    }
    
    return size;
}

int main() {
    char line[1000];
    
    // Read seats array
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = '\0';  // Remove newline
    int n = parseArray(line, seats);
    
    // Read students array
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = '\0';  // Remove newline
    int m = parseArray(line, students);
    
    printf("%d\n", solution(seats, students, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generate n! permutations, each taking O(n) time to evaluate

⚠ Quadratic Growth

Space Complexity

O(n)

Store current permutation and minimum result

⚡ Linearithmic Space

28.1K Views

Medium Frequency

~15 min Avg. Time

850 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

Minimum Number of Moves to Seat Everyone - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler