algoadvance

Leetcode 2037. Minimum Number of Moves to Seat Everyone

Problem Statement

Given an array seats consisting of n integers where seats[i] is the position of the i-th seat, and another array students of the same length n where students[j] is the position of the j-th student, return the minimum number of moves required to move each student to a seat such that no two students are in the same seat. A move consists of choosing any student and moving them to an adjacent seat by 1 unit.

Clarifying Questions

To fully understand the problem, let’s clarify a few things:

  1. Are the positions in the seats and students arrays guaranteed to be distinct? Yes. Each seat and each student position is distinct.

  2. What are the constraints on the values of seats and students? Both arrays have the same length and contain non-negative integers.

  3. What should be the output? The output should be the minimum number of moves required to seat all students.

Strategy

  1. Sort Both Arrays: The key to solving the problem efficiently is to align the students’ positions with the seats’ positions in an optimal way.
  2. Pair Sorted Seats and Students: By sorting both arrays, we can pair the smallest available seat with the smallest student’s position, the second smallest with the second smallest, and so on. This minimizes the total number of moves.
  3. Calculate Moves: Sum the absolute differences between the positions of the paired seats and students, which will give the minimum number of moves required.

Code

The following Java code implements the described solution:

import java.util.Arrays;

public class MinimumMovesToSeatEveryone {
    public int minMovesToSeat(int[] seats, int[] students) {
        // Sort both arrays
        Arrays.sort(seats);
        Arrays.sort(students);
        
        // Initialize total moves to 0
        int totalMoves = 0;
        
        // Calculate the sum of absolute differences
        for (int i = 0; i < seats.length; i++) {
            totalMoves += Math.abs(seats[i] - students[i]);
        }
        
        return totalMoves;
    }
    
    public static void main(String[] args) {
        MinimumMovesToSeatEveryone solution = new MinimumMovesToSeatEveryone();
        
        int[] seats = {4, 1, 5, 9};
        int[] students = {1, 3, 2, 6};
        
        int result = solution.minMovesToSeat(seats, students);
        System.out.println("Minimum number of moves: " + result); // Output: 7
    }
}

Time Complexity

Thus, the overall time complexity of the solution is O(n log n) due to the sorting step being the most dominant operation.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI