Minimum Number of Moves to Seat Everyone

Easy
267.

Minimum Number of Moves to Seat Everyone

Minimum Number of Moves to Seat Everyone is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

There are n seats and n students in a room. seats[i] is the position of the i-th seat and students[j] is the position of the j-th student.

In one move you may shift a student one position left or right. Return the minimum number of moves needed to seat every student, with no two students in the same seat.

Example 1

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

Example 2

Input
seats = [4,1,5,9], students = [1,3,2,6]
Output
7

Example 3

Input
seats = [2,2,6,6], students = [1,3,2,6]
Output
4

Constraints

  • 1 <= seats.length <= 40
  • seats.length == students.length
  • 1 <= seats[i], students[j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} seats
 * @param {number[]} students
 * @return {number}
 */
var minMovesToSeat = function(seats, students) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Moves to Seat Everyone — Solution

Minimum Number of Moves to Seat Everyone solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Number of Moves to Seat Everyone is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Greedy, Counting Sort
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n seats and n students in a room. seats[i] is the position of the i-th seat and students[j] is the position of the j-th student.

In one move you may shift a student one position left or right. Return the minimum number of moves needed to seat every student, with no two students in the same seat.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 1 <= seats.length <= 40
  • seats.length == students.length
  • 1 <= seats[i], students[j] <= 100

Hints for Minimum Number of Moves to Seat Everyone

  1. Hint 1

    Sort both lists and match them position by position.

  2. Hint 2

    Crossing two assignments never helps — swapping them back cannot increase the total distance.

  3. Hint 3

    The answer is the sum of the absolute differences of the matched pairs.

How to solve Minimum Number of Moves to Seat Everyone

Sort both lists and match them index by index; the answer is the sum of absolute differences.

Approach

  1. Sort seats and students.
  2. Sum |seats[i] - students[i]|.

Why it works

If two assignments cross (a left student to a right seat and vice versa), uncrossing them never increases the total distance, so the sorted matching is optimal.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • The lists have equal length by the statement; no padding is needed.

Reference solution

Python

def minMovesToSeat(seats, students) -> int:
    return sum(abs(a - b) for a, b in zip(sorted(seats), sorted(students)))

Java

public static int minMovesToSeat(int[] seats, int[] students) {
    int[] a = Arrays.copyOf(seats, seats.length);
    int[] b = Arrays.copyOf(students, students.length);
    Arrays.sort(a);
    Arrays.sort(b);
    int total = 0;
    for (int i = 0; i < a.length; i++) total += Math.abs(a[i] - b[i]);
    return total;
}

C++

int minMovesToSeat(vector<int>& seats, vector<int>& students) {
    vector<int> a = seats;
    vector<int> b = students;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int total = 0;
    for (size_t i = 0; i < a.size(); i++) total += abs(a[i] - b[i]);
    return total;
}

JavaScript

var minMovesToSeat = function(seats, students) {
    const a = seats.slice().sort(function(x, y) { return x - y; });
    const b = students.slice().sort(function(x, y) { return x - y; });
    let total = 0;
    for (let i = 0; i < a.length; i++) total += Math.abs(a[i] - b[i]);
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms