Code Logo

Minimum Number of Moves to Seat Everyone

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Minimum Number of Moves to Seat Everyone

Solution Approach

Sort both arrays, sum absolute differences at each index.

function solution(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;
}

Time O(n log n), Space 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;
    }
}