✅✅🔥🔥Two Approaches :- Sorting  O(n logn) and counting Sort O(n).
There are two approaches to solve this problem :-\n- Using Sorting\n- Using counting sort\n---\n# 1. Sorting Approach :-\n\n---\n\n\n# Intuition\n Describe your
# There are two approaches to solve this problem :-\n- Using Sorting\n- Using counting sort\n---\n# 1. *Sorting Approach :-*\n\n---\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe want to move the students to the seats Locations which are present in the seats vector. We want to move the students in such a way that the total number of moves to move all the students to the required seats must be minimum possible moves. Each move means incrementing or decrementing the position of current student by 1. Suppose there are 2 students and 2 seats.\n```\nseats = {5,9}\nstudents = {1,7}\n\n/* we want to move the students to the seat number 5 and 9, \n   which student to move to which side ??\n*/\n/*\n    The first thing comes in mind that whichever student is nearest to the\nseat should be moved to the seat. \nThis means for seat number 5 :-\n- student at seat number = 1 is 4 moves away from seat number 5.\n- student at seat number = 7 is 2 moves away from seat number 5.\n\n    int number of moves = 0\n    - Let the student at seat number 7 be moved to seat number 5.\n        number of moves += 2.\n        Now the student 1 must be moved to the seat number 9, which is 8 moves away.\n        number of moves = 2 + 8 = 10.\n\n\n        number of moves = 0\n    - Let the student at seat number 7 be moved to seat number 9, which is  moves away.\n        number of moves += 2\n        Now the student 1 must be moved to the seat number 5, which is 4 moves away.\n        number of moves = 2 + 4 = 6.\n\nSo which is giving the minimum number of moves.\nThe second way.\nIt means select the student from the students vector which is at lowest\nseat position, then select the lowest seat position from seats vector and\nthen move the student to that seat and then move forward for the other students.\n*/\n```\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Sort both of the vector in non-decreasing order.\n- Initialise ans , `int ans = 0;`\n- Start a for loop with seat = 0 , student = 0.\n```\nfor(int seat = 0, student = 0; seat < seats.size() && student < students.size(); seat++, student++) {\n}\n```\n- select the seat and store its seatPosition in `seatPosition = seats[seat]` and select the student seat position in `studentPosition = students[student]`\n```\nint seatPosition = seats[seat];\nint studentPosition = students[student];\n```\n- calculate the absolute difference of both.\n- add it to the `ans`.\n```\nans += abs(seatPosition - studentPosition);\n```\n- Out of the loop.\n- return `ans`.\n```\nreturn ans;\n```\n\n\n# Complexity\n- Time complexity: $$O(nlogn + nlogn + n)$$ = $$O(nlogn)$$ , two times sort and one for loop iterating n times, where n = seats.size() or students.size().\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(logn)$$ because memory used while using inbuilt sorting function.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n```C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        sort(seats.begin(),seats.end());\n        sort(students.begin(),students.end());\n\n        int n = seats.size();\n        int ans = 0;\n        for(int seat = 0, student = 0; seat < seats.size() && student < students.size(); seat++, student++) {\n            int seatPosition = seats[seat];\n            int studentPosition = students[student];\n            ans += abs(seatPosition - studentPosition);\n        }\n        return ans;\n    }\n};\n```\n```python3 []\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        seats.sort()\n        students.sort()\n\n        ans = 0\n        for seat, student in zip(seats, students):\n            ans += abs(seat - student)\n        return ans\n\n```\n``` Java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        Arrays.sort(seats);\n        Arrays.sort(students);\n\n        int ans = 0;\n        for (int i = 0; i < seats.length; i++) {\n            ans += Math.abs(seats[i] - students[i]);\n        }\n        return ans;\n    }\n}\n\n```\n```ruby []\n# @param {Integer[]} seats\n# @param {Integer[]} students\n# @return {Integer}\ndef min_moves_to_seat(seats, students)\n    seats.sort!\n    students.sort!\n    ans = 0\n    seats.each_with_index do |seat, i|\n        ans += (seat - students[i]).abs\n        end\n    ans\nend\n```\n\n\n``` JavaScript []\n/**\n * @param {number[]} seats\n * @param {number[]} students\n * @return {number}\n */\nvar minMovesToSeat = function(seats, students) {\n    seats.sort((a, b) => a - b);\n    students.sort((a, b) => a - b);\n\n    let ans = 0;\n    for (let i = 0; i < seats.length; i++) {\n        ans += Math.abs(seats[i] - students[i]);\n    }\n    return ans;\n};\n\n```\n```Rust []\nimpl Solution {\n    pub fn min_moves_to_seat(seats: Vec<i32>, students: Vec<i32>) -> i32 {\n        let mut seats = seats.clone();\n        let mut students = students.clone();\n        seats.sort();\n        students.sort();\n\n        let mut ans = 0;\n        for i in 0..seats.len() {\n            ans += (seats[i] - students[i]).abs();\n        }\n        ans\n    }\n}\n\n```\n``` Go []\nfunc minMovesToSeat(seats []int, students []int) int {\n\tsort.Ints(seats)\n\tsort.Ints(students)\n\n\tans := 0\n\tfor i := 0; i < len(seats); i++ {\n\t\tans += int(math.Abs(float64(seats[i] - students[i])))\n\t}\n\treturn ans\n}\n\n```\n[Instagram](https://www.instagram.com/iamsidharthaa__/)\n[LinkedIn](https://www.linkedin.com/in/sidharth-jain-36b542133)\n**If you find this solution helpful, consider giving it an upvote! Your support is appreciated. Keep coding, stay healthy, and may your programming endeavors be both rewarding and enjoyable!**\n\n---\n# 2. *Using Counting Sort Approach :-*\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have to place the students to the first seat which is non occupied in the seat array. So we will track the count of each seat location and also track the count of students initially positioned at their given seats.\nwe will check each seat, which is non occupied, after finding the first non-occupied seat, we will search the student which is not moved to the reqired seat, after finding the student we will move it to the current seat and add the moves to the answer and also if the current seat positions are all filled then we will go to the next seat.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n<!-- Discussed in the comments in the code. -->\n\n**The problem requires finding the minimum number of moves to seat all students in the given seats such that the moves are minimized. The given constraints specify that the seat positions and student positions range from 1 to 100.**\n\n\n### 1. Initialization:\n\n- Create two vectors, seatsLocation and studentsFreq, to store the frequency of each seat and student position, respectively.\n- The size of these vectors is determined by the maximum element in the seats and students vectors plus one. This ensures that the indices of the vectors cover all possible positions from 0 to the maximum seat/student position.\n\n### 2. Populate Frequency Vectors:\n\n- Iterate over the seats array and increment the corresponding index in the seatsLocation vector.\n- Similarly, iterate over the students array and increment the corresponding index in the studentsFreq vector.\n\n### 3. Finding Minimum Moves:\n\n- Initialize studentPosition to 1 since the positions start from 1.\n- Initialize ans to 0 to store the total minimum moves.\n- Iterate over the seatsLocation vector to find seats that need to be filled.\n- For each seat that has available positions (seatsLocation[seat] > 0), find the nearest student who is not already seated by checking the studentsFreq vector.\n- Calculate the moves required to seat the student at the current seat position and update ans.\n- Decrease the counts in both seatsLocation and studentsFreq to indicate that one seat is filled and one student is seated.\n- Move to the next seat position if the current seat is completely filled (seatsLocation[seat] == 0).\n\n### 4. Return the Result:\n\n- After all seats are filled, return the total number of moves stored in ans.\n\n# Complexity\n- Time complexity: $$O(n + n )$$ = $$O(n)$$ , where n = seats.size() or students.size().\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m1 + m2)$$ , where m1 = max seat position in the seats vector and where m2 = max seat position of student in the students vector. \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        vector<int> seatsLocation(*max_element(seats.begin(),seats.end()) + 1, 0); // to store the seats available and store its frequency.\n        vector<int> studentsFreq(*max_element(students.begin(),students.end()) + 1, 0); // to count the number of students which are initially present at the alloted seats initially.\n\n        for(auto loc: seats) seatsLocation[loc]++; // filling the seatsLocation vector\n        for(auto std: students) studentsFreq[std]++; // filling the students initially alloted seats\n        int seatsLocationSize = seatsLocation.size(); // size of the seatsLocation vector\n        int studentsFrequencySize = studentsFreq.size(); // size of the studentsFreq vector\n        int studentPosition = 1; // we know that the students initial position can be from 1 to 100. as given in the constraints :- 1 <= seats[i], students[j] <= 100\n        int ans = 0; // to store the minimum number of moves to move each student to the given seat location \n        for(int seat = 1; seat < seatsLocationSize; ) { // seats are available from 1 to 100 both inclusive as give int the constraints :- 1 <= seats[i], students[j] <= 100\n            if(seatsLocation[seat] == 0) { // if there is not any seat location in the seats vector then we can move forward\n                seat++; // incrementing the seat as the current seat is not available in the seats vector\n                continue; // skipping the further process\n            }\n\n            // now we have reached a seat which is present in the seats vector, now we have to find the student which is present in the students vector which is currently not seated at the required seat.\n            while(studentPosition < studentsFrequencySize && studentsFreq[studentPosition] == 0) studentPosition++; \n            // we have reached at the student which is currently at \'studentPosition\', we have to move the student to the \'seat\' and the number of moves for moving the student to seat from studentPosition = absolute value of (studentPosition - seat).\n            ans += abs(studentPosition - seat); // adding the number of moves in the answer\n            seatsLocation[seat]--; // now one of the location in the seats vector is filled, so we are decrementing the available seats which can be filled in the future by the students.\n            studentsFreq[studentPosition]--; // also one student is currently moved to the required seat location, so we are decrementing the studentsFreq which are currently present at the studentLocation seat\n            if(seatsLocation[seat] == 0) { // if current seat has no more positions for the seating of students, then we are incrementing the seat to go to the next available seat which is present in the seats vector.\n                seat++; // incrementing the seat by 1.\n            } \n        }\n        return ans; // returning the answer\n    }\n};\n```\n```Java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        int[] seatsLocation = new int[Arrays.stream(seats).max().getAsInt() + 1];\n        int[] studentsFreq = new int[Arrays.stream(students).max().getAsInt() + 1];\n\n        for (int loc : seats) seatsLocation[loc]++;\n        for (int std : students) studentsFreq[std]++;\n\n        int seatsLocationSize = seatsLocation.length;\n        int studentsFrequencySize = studentsFreq.length;\n        int studentPosition = 1;\n        int ans = 0;\n\n        for (int seat = 1; seat < seatsLocationSize; ) {\n            if (seatsLocation[seat] == 0) {\n                seat++;\n                continue;\n            }\n\n            while (studentPosition < studentsFrequencySize && studentsFreq[studentPosition] == 0) {\n                studentPosition++;\n            }\n\n            ans += Math.abs(studentPosition - seat);\n            seatsLocation[seat]--;\n            studentsFreq[studentPosition]--;\n\n            if (seatsLocation[seat] == 0) {\n                seat++;\n            }\n        }\n        return ans;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        seats_location = [0] * (max(seats) + 1)\n        students_freq = [0] * (max(students) + 1)\n\n        for loc in seats:\n            seats_location[loc] += 1\n        for std in students:\n            students_freq[std] += 1\n\n        seats_location_size = len(seats_location)\n        students_frequency_size = len(students_freq)\n        student_position = 1\n        ans = 0\n\n        seat = 1\n        while seat < seats_location_size:\n            if seats_location[seat] == 0:\n                seat += 1\n                continue\n\n            while student_position < students_frequency_size and students_freq[student_position] == 0:\n                student_position += 1\n\n            ans += abs(student_position - seat)\n            seats_location[seat] -= 1\n            students_freq[student_position] -= 1\n\n            if seats_location[seat] == 0:\n                seat += 1\n\n        return ans\n\n```\n``` Ruby []\n# @param {Integer[]} seats\n# @param {Integer[]} students\n# @return {Integer}\n\n  def min_moves_to_seat(seats, students)\n    seats_location = Array.new(seats.max + 1, 0)\n    students_freq = Array.new(students.max + 1, 0)\n\n    seats.each { |loc| seats_location[loc] += 1 }\n    students.each { |std| students_freq[std] += 1 }\n\n    seats_location_size = seats_location.size\n    students_frequency_size = students_freq.size\n    student_position = 1\n    ans = 0\n\n    seat = 1\n    while seat < seats_location_size\n      if seats_location[seat] == 0\n        seat += 1\n        next\n      end\n\n      while student_position < students_frequency_size && students_freq[student_position] == 0\n        student_position += 1\n      end\n\n      ans += (student_position - seat).abs\n      seats_location[seat] -= 1\n      students_freq[student_position] -= 1\n\n      seat += 1 if seats_location[seat] == 0\n    end\n\n    ans\n  end\n\n\n```\n```JavaScript []\n/**\n * @param {number[]} seats\n * @param {number[]} students\n * @return {number}\n */\nvar minMovesToSeat = function(seats, students) {\n    let seatsLocation = Array(Math.max(...seats) + 1).fill(0);\n    let studentsFreq = Array(Math.max(...students) + 1).fill(0);\n\n    seats.forEach(loc => seatsLocation[loc]++);\n    students.forEach(std => studentsFreq[std]++);\n\n    let seatsLocationSize = seatsLocation.length;\n    let studentsFrequencySize = studentsFreq.length;\n    let studentPosition = 1;\n    let ans = 0;\n\n    for (let seat = 1; seat < seatsLocationSize; ) {\n        if (seatsLocation[seat] === 0) {\n            seat++;\n            continue;\n        }\n\n        while (studentPosition < studentsFrequencySize && studentsFreq[studentPosition] === 0) {\n            studentPosition++;\n        }\n\n        ans += Math.abs(studentPosition - seat);\n        seatsLocation[seat]--;\n        studentsFreq[studentPosition]--;\n\n        if (seatsLocation[seat] === 0) {\n            seat++;\n        }\n    }\n    return ans;\n};\n```\n```Rust []\nimpl Solution {\n    pub fn min_moves_to_seat(seats: Vec<i32>, students: Vec<i32>) -> i32 {\n        let mut seats_location = vec![0; *seats.iter().max().unwrap() as usize + 1];\n        let mut students_freq = vec![0; *students.iter().max().unwrap() as usize + 1];\n\n        for &loc in &seats {\n            seats_location[loc as usize] += 1;\n        }\n        for &std in &students {\n            students_freq[std as usize] += 1;\n        }\n\n        let seats_location_size = seats_location.len();\n        let students_frequency_size = students_freq.len();\n        let mut student_position = 1;\n        let mut ans = 0;\n\n        let mut seat = 1;\n        while seat < seats_location_size {\n            if seats_location[seat] == 0 {\n                seat += 1;\n                continue;\n            }\n\n            while student_position < students_frequency_size && students_freq[student_position] == 0 {\n                student_position += 1;\n            }\n\n            ans += (student_position as i32 - seat as i32).abs();\n            seats_location[seat] -= 1;\n            students_freq[student_position] -= 1;\n\n            if seats_location[seat] == 0 {\n                seat += 1;\n            }\n        }\n        ans\n    }\n}\n```\n```Go []\nfunc minMovesToSeat(seats []int, students []int) int {\n\tseatsLocation := make([]int, max(seats)+1)\n\tstudentsFreq := make([]int, max(students)+1)\n\n\tfor _, loc := range seats {\n\t\tseatsLocation[loc]++\n\t}\n\tfor _, std := range students {\n\t\tstudentsFreq[std]++\n\t}\n\n\tseatsLocationSize := len(seatsLocation)\n\tstudentsFrequencySize := len(studentsFreq)\n\tstudentPosition := 1\n\tans := 0\n\n\tfor seat := 1; seat < seatsLocationSize; {\n\t\tif seatsLocation[seat] == 0 {\n\t\t\tseat++\n\t\t\tcontinue\n\t\t}\n\n\t\tfor studentPosition < studentsFrequencySize && studentsFreq[studentPosition] == 0 {\n\t\t\tstudentPosition++\n\t\t}\n\n\t\tans += int(math.Abs(float64(studentPosition - seat)))\n\t\tseatsLocation[seat]--\n\t\tstudentsFreq[studentPosition]--\n\n\t\tif seatsLocation[seat] == 0 {\n\t\t\tseat++\n\t\t}\n\t}\n\treturn ans\n}\n\nfunc max(arr []int) int {\n\tm := arr[0]\n\tfor _, v := range arr {\n\t\tif v > m {\n\t\t\tm = v\n\t\t}\n\t}\n\treturn m\n}\n\n```\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n\n\n[Instagram](https://www.instagram.com/iamsidharthaa__/)\n[LinkedIn](https://www.linkedin.com/in/sidharth-jain-36b542133)\n**If you find this solution helpful, consider giving it an upvote! Your support is appreciated. Keep coding, stay healthy, and may your programming endeavors be both rewarding and enjoyable!**
['Array', 'Greedy', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'Ruby', 'JavaScript']