Code Logo

Minimum Number of Moves to Seat Everyone

Published at24 Jul 2026
Created by
Easy 1 views
Like0

There are n seats and n students in a room. Each seat and student has a position on a number line. A move consists of moving a student by 1 position left or right. Find the minimum number of moves required to seat every student in a distinct seat.

Sort both arrays. The optimal assignment pairs the i-th smallest seat with the i-th smallest student. Sum the absolute differences between corresponding positions after sorting. This works due to the rearrangement inequality.

Time is O(n log n) for sorting, O(n) for the sum calculation. Space is O(1). Edge cases include a single student (return absolute difference), already matched positions (return 0), and large gaps between seats and students.

The pairing strategy of matching sorted positions minimizes total absolute distance because crossing pairs would only increase the total distance. This is formalized by the rearrangement inequality, which states that the sum of absolute differences is minimized when both sequences are sorted in the same order.

This problem illustrates how sorting enables optimal matching between two sets of points on a line, a pattern that appears in many assignment and scheduling problems.

Example Input & Output

Example 1
Input
[3,1,5], [2,7,4]
Output
4
Explanation

Match: 1-2, 3-4, 5-7. Moves: 1+1+2=4.

Example 2
Input
[5,5], [1,5]
Output
4
Explanation

5-5=0, 1-5=4. Total=4.

Example 3
Input
[1], [5]
Output
4
Explanation

Single student moves 4.

Example 4
Input
[2,2,2], [2,2,2]
Output
0
Explanation

Already matched.

Example 5
Input
[4,1,5,9], [1,3,2,6]
Output
7
Explanation

Moves: 1-1=0, 3-4=1, 2-5=3, 6-9=3. Total=7.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Number of Moves to Seat Everyone

Solution Approach

Sort both the positions and the students arrays in ascending order, then pair them by index and sum the absolute differences. This greedy approach works because matching the smallest student with the smallest position minimizes the total moves.

function minMoves(seats, students) {
  seats.sort(function(a, b) { return a - b; });
  students.sort(function(a, b) { return a - b; });
  var moves = 0;
  for (var i = 0; i < seats.length; i++) {
    moves += Math.abs(seats[i] - students[i]);
  }
  return moves;
}

After sorting both arrays, each student is assigned to the seat at the same index. The absolute difference between each pair represents the number of moves required. Summing these differences gives the minimum total moves.

Time complexity is O(n log n) for the two sorts, space complexity is O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] seats, int[] students) {
        Arrays.sort(seats);Arrays.sort(students);
        int m=0;
        for (int i=0;i<seats.length;i++) m+=Math.abs(seats[i]-students[i]);
        return m;
    }
}