✅Beats 100% - Explained with [ Video ] - C++/Java/Python/JS - Arrays - Sorting - Interview Solution
\n\n\n# YouTube Video Explanation:\n\n **If you want a video for this question please write in the comments** \n\n https://www.youtube.com/watch?v=ujU-jeO1v-k \
![Screenshot 2024-06-13 065049.png](https://assets.leetcode.com/users/images/f1166a57-0d26-4fef-a119-f59ee16b413a_1718242226.1727304.png)\n\n\n# YouTube Video Explanation:\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n<!-- https://www.youtube.com/watch?v=ujU-jeO1v-k -->\n\nhttps://youtu.be/2gkefxP-cQw\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 1900 Subscribers*\n*Current Subscribers: 1855*\n\n---\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to find the minimum number of moves to position each student in a seat such that no two students occupy the same seat. Since the cost of moving a student is the absolute difference between their current position and the target seat position, the optimal way to achieve this is to pair the closest seats with the closest students.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Sorting**:\n   - Sort both the `seats` and `students` arrays. By sorting, we ensure that the smallest available seat is paired with the smallest positioned student, the second smallest seat with the second smallest positioned student, and so on. This minimizes the overall distance each student has to move.\n   \n2. **Calculate Moves**:\n   - Iterate through the sorted arrays and compute the sum of absolute differences between the corresponding elements in the `seats` and `students` arrays. This gives the total number of moves required to seat all students.\n\n# Complexity\n- **Time Complexity**: `O(n log n)`\n  - Sorting the `seats` and `students` arrays takes \\( O(n \\log n) \\) time each.\n  - Calculating the total moves takes \\( O(n) \\) time.\n  - Hence, the overall time complexity is dominated by the sorting step, i.e., \\( O(n \\log n) \\).\n\n- **Space Complexity**: `O(1)`\n  - No extra space is used other than a few variables to store intermediate results.\n\n\n# Step by Step Explanation\n\nLet\'s take the example from the problem statement:\n\n**Example**: `seats = [3, 1, 5]`, `students = [2, 7, 4]`\n\n1. **Initial State**:\n\n| Seats | Students |\n|-------|----------|\n| 3     | 2        |\n| 1     | 7        |\n| 5     | 4        |\n\n2. **After Sorting**:\n\n| Seats | Students |\n|-------|----------|\n| 1     | 2        |\n| 3     | 4        |\n| 5     | 7        |\n\n3. **Calculate Moves**:\n\n| Seat | Student | Moves |\n|------|---------|-------|\n| 1    | 2       | 1     |\n| 3    | 4       | 1     |\n| 5    | 7       | 2     |\n| **Total Moves** |         | **4**   |\n\nThe total number of moves required is 4.\n\n\n\n\n# Code\n```java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        Arrays.sort(seats);\n        Arrays.sort(students);\n        int n=seats.length;\n        int sum=0;\n        for(int i=0;i<n;i++){\n            sum += Math.abs(seats[i]-students[i]);\n        }\n        return sum;\n    }\n}\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        int moves = 0;\n        for( int i=0; i<seats.size(); i++)\n            moves += abs(seats[i] - students[i]);\n        \n        return moves;\n    }\n};\n```\n```Python []\nclass Solution:\n    def minMovesToSeat(self, seats, students):\n        seats.sort()\n        students.sort()\n        return sum(abs(seat - student) for seat, student in zip(seats, students))\n```\n```JavaScript []\n/**\n * @param {number[]} seats\n * @param {number[]} students\n * @return {number}\n */\nvar minMovesToSeat = function(seats, students) {\n    let moves =0\n    seats = seats.sort((a,b)=>b-a)\n    students = students.sort((a,b)=>b-a)\n    seats.forEach((s,i)=>\n    moves = moves+Math.abs(s-students[i]))\n\n    return moves\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/93ac375b-d4bd-4666-86f3-b1cfdb8dc830_1718242308.1009545.png)\n\n# Another Approach (\u2705Beats 100%)\n\n# Intuition:\nTo minimize the number of moves required to seat each student, we need to pair each student with an available seat such that the distance between the student\'s position and the seat\'s position is minimized. We can achieve this by sorting the positions of seats and students and then iterating through both arrays simultaneously to calculate the total moves needed.\n\n# Approach:\n1. Sort the `seats` and `students` arrays.\n2. Initialize a variable `moves` to track the total number of moves.\n3. Iterate through both arrays simultaneously.\n   - Calculate the absolute difference between the position of the current student and the current seat.\n   - Add this difference to `moves`.\n4. Return the total number of moves.\n\n# Complexity:\n- Time complexity: O(nlogn) due to sorting the arrays.\n- Space complexity: O(n) for storing the sorted arrays.\n\n# Code\n\n```java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        int[] pos = new int[101];\n        int n = seats.length;\n        for(int i = 0; i < n; i++){\n            pos[seats[i]]++;\n            pos[students[i]]--;\n        }\n        int res = 0;\n        int current = 0;\n        for(int i: pos){\n            res += Math.abs(current);\n            current += i;\n        }\n        return res;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n       vector<int> pos(101, 0);\n        int n = seats.size();\n        for(int i = 0; i < n; i++){\n            pos[seats[i]]++;\n            pos[students[i]]--;\n        }\n        int res = 0;\n        int current = 0;\n        for(int i: pos){\n            res += abs(current);\n            current += i;\n        }\n        return res;\n    }\n};\n```\n```Python []\nclass Solution:\n    def minMovesToSeat(self, seats, students):\n        pos = [0] * 101\n        n = len(seats)\n        for i in range(n):\n            pos[seats[i]] += 1\n            pos[students[i]] -= 1\n        res = 0\n        current = 0\n        for i in pos:\n            res += abs(current)\n            current += i\n        return res\n```\n```JavaScript []\n/**\n * @param {number[]} seats\n * @param {number[]} students\n * @return {number}\n */\nvar minMovesToSeat = function(seats, students) {\n    const pos = new Array(101).fill(0);\n        const n = seats.length;\n        for(let i = 0; i < n; i++){\n            pos[seats[i]]++;\n            pos[students[i]]--;\n        }\n        let res = 0;\n        let current = 0;\n        for(const i of pos){\n            res += Math.abs(current);\n            current += i;\n        }\n        return res;\n};\n```
['Array', 'Greedy', 'Sorting', 'Python', 'C++', 'Java', 'JavaScript']