Sponsored
Sponsored
This approach relies on sorting both the seats
and students
arrays. After sorting them, we pair the i-th seat with the i-th student. The sum of absolute differences between corresponding elements gives us the minimum number of moves required.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is in-place.
1using System;
2
3class Solution {
4 public int MinMovesToSeat(int[] seats, int[] students) {
5 Array.Sort(seats);
6 Array.Sort(students);
7 int result = 0;
8 for (int i = 0; i < seats.Length; i++) {
9 result += Math.Abs(seats[i] - students[i]);
10 }
11 return result;
12 }
13 static void Main(string[] args) {
14 Solution sol = new Solution();
15 int[] seats = {3, 1, 5};
16 int[] students = {2, 7, 4};
17 Console.WriteLine(sol.MinMovesToSeat(seats, students));
18 }
19}
The arrays seats
and students
are sorted using Array.Sort()
. The sum of the absolute differences between corresponding sorted elements is calculated to find the minimum moves.
This approach involves creating frequency arrays or maps for both seats and students positions. Align students to seats by finding the closest available seat iteratively, simulating a greedy approach.
Time Complexity: O(n + m), where m is the range of possible positions (maximum 100).
Space Complexity: O(m) due to frequency arrays.
1#include <vector>
#include <algorithm>
int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {
std::vector<int> seatCount(101, 0), studentCount(101, 0);
for (int seat : seats) seatCount[seat]++;
for (int student : students) studentCount[student]++;
int i = 0, j = 0, moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
int min_count = std::min(seatCount[i], studentCount[j]);
moves += abs(i - j) * min_count;
seatCount[i] -= min_count;
studentCount[j] -= min_count;
}
if (seatCount[i] == 0) i++;
if (studentCount[j] == 0) j++;
}
return moves;
}
int main() {
std::vector<int> seats = {3, 1, 5};
std::vector<int> students = {2, 7, 4};
std::cout << minMovesToSeat(seats, students) << std::endl;
return 0;
}
Create frequency counts for both seats and students. Utilize two iterators to link closest seat-student pairs while counting movements.