Minimum Number of Moves to Seat Everyone - Practice Coding Problems

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

Understanding the Visualization

Input

Students at positions [3,1,5], seats at [2,7,4]

Process

Sort both arrays and pair optimally

Output

Minimum total moves = 4

Key Takeaway

🎯 Key Insight: Sorting both arrays and pairing corresponding positions minimizes total Manhattan distance

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

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(n!)	O(n)	Generate all possible seat assignments and find the one with minimum total moves
Greedy Approach - Sort and Match	O(n log n)	O(1)	Sort both arrays and pair each student with corresponding seat by position

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>

int minMoves = INT_MAX;

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) {
    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 main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int seats[100], students[100], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        seats[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        students[m++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler