💹Easy Detailed 2 Approaches🔰📊 || Beats 100% || 🚀 Minimizing Student Moves to Vacant Seats
Detailed Explanation - \nArrays of seats represent the vacant seats in the the line of seats. Students arrays represents students position. To understand this p
# Detailed Explanation - \nArrays of seats represent the vacant seats in the the line of seats. Students arrays represents students position. To understand this problem lets take the first example.\n\nseats = [3,1,5], students = [2,7,4]\nseats array explanation: (1-2) -> filled, 3 - vacant, 4 occupied, 5-vacant, 6-7 occupied(why we took 7 here as student is at position 7 as well)\nUnderstanding if 1-2,4, 6-7 is already occupied meaning someone is already sitting there.\n\nso students array represent where two students might be sitting and we want to move each student to a different seats. Eg - seat 2 was already occupied because it is not vacant and we have another student at position 2 so we would move him to nearest vacant seat available i.e 3..\n\n# Intuition\nTo minimize the number of moves required to seat all students in vacant seats, it is intuitive to pair each student with the nearest vacant seat. This minimizes the individual distance each student needs to move.\n\n# 1st Approach:  \nThe simplest approach involves sorting both the `seats` and `students` arrays. By sorting, we can directly pair the closest vacant seat to each student, ensuring the total distance moved is minimized. This approach is based on the idea that matching the smallest available seat with the closest student yields the optimal solution.\n\nSteps:\n1. Sort the `seats` array.\n2. Sort the `students` array.\n3. Calculate the total number of moves by summing the absolute differences between corresponding elements in the sorted arrays.\n\n# Complexity\n- Time complexity:\n  The time complexity is $$O(n \\log n)$$ due to the sorting of both arrays.\n\n- Space complexity:\n  The space complexity is $$O(1)$$ as we only use a few extra variables for counting and indexing, irrespective of the input size.\n\n```JAVA []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        // Sort the seats array\n        Arrays.sort(seats);\n        \n        // Sort the students array\n        Arrays.sort(students);\n        \n        // Initialize the count of moves to 0\n        int count = 0;\n        \n        // Iterate through the sorted arrays\n        for (int i = 0; i < seats.length; i++) {\n            // Calculate the absolute difference between the seat and student positions\n            count += Math.abs(seats[i] - students[i]);\n        }\n        \n        // Return the total count of moves\n        return count;\n    }\n}\n```\n```python []\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        # Sort the seats array\n        seats.sort()\n        # Sort the students array\n        students.sort()\n        # Initialize the count of moves to 0\n        count = 0       \n        # Iterate through the sorted arrays\n        for seat, student in zip(seats, students):\n            # Calculate the absolute difference between the seat and student positions\n            count += abs(seat - student)\n        # Return the total count of moves\n        return count\n\n```\n```C++ []\n#include <vector>\n#include <algorithm>\n#include <cmath>\n\nclass Solution {\npublic:\n    int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {\n        // Sort the seats array\n        std::sort(seats.begin(), seats.end());\n        \n        // Sort the students array\n        std::sort(students.begin(), students.end());\n        \n        // Initialize the count of moves to 0\n        int count = 0;\n        \n        // Iterate through the sorted arrays\n        for (int i = 0; i < seats.size(); i++) {\n            // Calculate the absolute difference between the seat and student positions\n            count += std::abs(seats[i] - students[i]);\n        }\n        \n        // Return the total count of moves\n        return count;\n    }\n};\n\n```\n# 2nd Approach: \n\nTo achieve an optimal solution in \\(O(n)\\) time complexity, we use a counting approach:\n1. Use two arrays to count the occurrences of seats and students at each position.\n2. Traverse through these arrays to match students to the nearest vacant seats and calculate the moves.\n\n# Complexity\n- Time complexity:\n  The time complexity is \\(O(n)\\) since we only iterate through the arrays once.\n\n- Space complexity:\n  The space complexity is \\(O(n)\\) due to the additional arrays used for counting.\n\n```JAVA []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        int maxPosition = 100; // Assuming positions are within the range 1 to 100\n\n        // Arrays to store the counts of seats and students at each position\n        int[] seatCount = new int[maxPosition + 1];\n        int[] studentCount = new int[maxPosition + 1];\n\n        // Fill the count arrays\n        for (int seat : seats) {\n            seatCount[seat]++;\n        }\n        for (int student : students) {\n            studentCount[student]++;\n        }\n\n        int moves = 0;\n        int seatIndex = 1, studentIndex = 1;\n\n        // Match students to the nearest seats\n        while (seatIndex <= maxPosition && studentIndex <= maxPosition) {\n            // Find the next available seat\n            while (seatIndex <= maxPosition && seatCount[seatIndex] == 0) {\n                seatIndex++;\n            }\n            // Find the next student to move\n            while (studentIndex <= maxPosition && studentCount[studentIndex] == 0) {\n                studentIndex++;\n            }\n\n            // If both seat and student positions are within range\n            if (seatIndex <= maxPosition && studentIndex <= maxPosition) {\n                int minCount = Math.min(seatCount[seatIndex], studentCount[studentIndex]);\n\n                // Calculate the moves for the current position\n                moves += minCount * Math.abs(seatIndex - studentIndex);\n\n                // Decrease the count of seats and students matched\n                seatCount[seatIndex] -= minCount;\n                studentCount[studentIndex] -= minCount;\n            }\n        }\n\n        return moves;\n    }\n}\n```\n```python []\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        max_position = 100  # Assuming positions are within the range 1 to 100\n\n        # Arrays to store the counts of seats and students at each position\n        seat_count = [0] * (max_position + 1)\n        student_count = [0] * (max_position + 1)\n\n        # Fill the count arrays\n        for seat in seats:\n            seat_count[seat] += 1\n        for student in students:\n            student_count[student] += 1\n\n        moves = 0\n        seat_index = 1\n        student_index = 1\n\n        # Match students to the nearest seats\n        while seat_index <= max_position and student_index <= max_position:\n            # Find the next available seat\n            while seat_index <= max_position and seat_count[seat_index] == 0:\n                seat_index += 1\n            # Find the next student to move\n            while student_index <= max_position and student_count[student_index] == 0:\n                student_index += 1\n\n            # If both seat and student positions are within range\n            if seat_index <= max_position and student_index <= max_position:\n                min_count = min(seat_count[seat_index], student_count[student_index])\n\n                # Calculate the moves for the current position\n                moves += min_count * abs(seat_index - student_index)\n\n                # Decrease the count of seats and students matched\n                seat_count[seat_index] -= min_count\n                student_count[student_index] -= min_count\n\n        return moves\n\n```\n```C++ []\n#include <vector>\n#include <algorithm>\n#include <cmath>\n\nclass Solution {\npublic:\n    int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {\n        int maxPosition = 100; // Assuming positions are within the range 1 to 100\n\n        // Arrays to store the counts of seats and students at each position\n        std::vector<int> seatCount(maxPosition + 1, 0);\n        std::vector<int> studentCount(maxPosition + 1, 0);\n\n        // Fill the count arrays\n        for (int seat : seats) {\n            seatCount[seat]++;\n        }\n        for (int student : students) {\n            studentCount[student]++;\n        }\n\n        int moves = 0;\n        int seatIndex = 1, studentIndex = 1;\n\n        // Match students to the nearest seats\n        while (seatIndex <= maxPosition && studentIndex <= maxPosition) {\n            // Find the next available seat\n            while (seatIndex <= maxPosition && seatCount[seatIndex] == 0) {\n                seatIndex++;\n            }\n            // Find the next student to move\n            while (studentIndex <= maxPosition && studentCount[studentIndex] == 0) {\n                studentIndex++;\n            }\n\n            // If both seat and student positions are within range\n            if (seatIndex <= maxPosition && studentIndex <= maxPosition) {\n                int minCount = std::min(seatCount[seatIndex], studentCount[studentIndex]);\n\n                // Calculate the moves for the current position\n                moves += minCount * std::abs(seatIndex - studentIndex);\n\n                // Decrease the count of seats and students matched\n                seatCount[seatIndex] -= minCount;\n                studentCount[studentIndex] -= minCount;\n            }\n        }\n\n        return moves;\n    }\n};\n\n```\n\nPlease UpVote for Anya Chan if you read it till here..\n\n![image.png](https://assets.leetcode.com/users/images/fa3925b0-153c-4700-b0d3-32e814755613_1718245390.15616.png)\n\n\n\n
['Array', 'Two Pointers', 'Sorting', 'Python', 'C++', 'Java', 'Python3']