All the 3 approaches along with optimized O(n) 🔥 approach | C++ ✔️| Java✔️ | Python ✔️|
If you like the solution , please make a upvote \uD83D\uDE0A\u2B06\uFE0F\n\n---\n\n\n# Approach 1 - Sorting\n\n---\n\n\n\n# Intuition\nIn each step we want to f
## If you like the solution , please make a upvote \uD83D\uDE0A\u2B06\uFE0F\n\n---\n\n\n# Approach 1 - Sorting\n\n---\n\n![IMG_0042.jpg](https://assets.leetcode.com/users/images/1a8747a6-d3d2-4f7c-aeba-da1c93dc621e_1718246744.1540582.jpeg)\n\n# Intuition\nIn each step we want to find a student , closest to a position , so that student have to move minimum positions.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe sort both the arrays , so that we can get the minimum positions as well as the students nearest to the minimum position.\n\n# Complexity\n- Time complexity: `O(n log(n))`\n\n\n- Space complexity:`O(log(n))` (*for recursive stack calls*)\n\n# Code\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 ans = 0;\n        for(int i=0;i<seats.size();i++){\n            ans+=abs(seats[i]-students[i]);\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution(object):\n    def minMovesToSeat(self, seats, students):\n        seats.sort()\n        students.sort()\n        ans = 0\n        for i in range(len(seats)):\n            ans += abs(seats[i] - students[i])\n        return ans\n\n        \n```\n```java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        Arrays.sort(seats);\n        Arrays.sort(students);\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---\n\n# Approach 2 - Priority Queue\n\n---\n![IMG_0043.jpg](https://assets.leetcode.com/users/images/5ea619e9-c419-4dc4-9adc-b13253712ff2_1718247173.4869456.jpeg)\n\n\n\n# Complexity\n- Time complexity: `O(n log(n))`\n\n\n- Space complexity:`O(n)` (*each priority queue will store n elements*)\n\n\n```C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(vector<int>& seats, vector<int>& students) {\n        int ans = 0;\n        priority_queue<int> pq , student;\n        for(int i=0;i<seats.size();i++){\n            pq.push(seats[i]);\n            student.push(students[i]);\n        }\n        for(int i=0;i<seats.size();i++){\n            int a = pq.top();\n            int b = student.top();\n            pq.pop();\n            student.pop();\n            ans+=abs(a-b);\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution(object):\n    def minMovesToSeat(self, seats, students):\n        ans = 0\n        pq = []\n        student = []\n        \n        for seat in seats:\n            heapq.heappush(pq, -seat)  # Using negative values to simulate max-heap\n        for stud in students:\n            heapq.heappush(student, -stud)  # Using negative values to simulate max-heap\n        \n        while pq:\n            a = -heapq.heappop(pq)\n            b = -heapq.heappop(student)\n            ans += abs(a - b)\n        \n        return ans\n\n        \n```\n```java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        int ans = 0;\n        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());\n        PriorityQueue<Integer> student = new PriorityQueue<>(Collections.reverseOrder());\n        \n        for (int i = 0; i < seats.length; i++) {\n            pq.add(seats[i]);\n            student.add(students[i]);\n        }\n        \n        while (!pq.isEmpty()) {\n            int a = pq.poll();\n            int b = student.poll();\n            ans += Math.abs(a - b);\n        }\n        \n        return ans;\n    }\n}\n```\n\n---\n\n\n\n# Approach 3 - Counting sort (O(n))\n\n---\n\n\n# Intuition \nThe main idea is to take advantage of the fact that the seat and student positions are bounded between 1 and 100. This allows us to use a counting sort approach, which can be more efficient than comparison-based sorting for small ranges. By counting the occurrences of each seat and student position, we can then match them in a way that minimizes the movement.\n\n# Approach \n1. **Count Occurrences**: Create arrays to count the occurrences of each position for both seats and students.\n2. **Match Positions**: Iterate through the counted positions and match students to seats while minimizing the total moves.\n3. **Calculate Moves**: For each matching, calculate the absolute difference and sum it up.\n\n# Complexity\n- Time complexity: `O(n+k)` (*k = 100 , making it O(n) effectively*)\n\n\n- Space complexity:`O(k)` (*k = 100 , making it O(1) effectively*)\n```C++ []\nclass Solution {\npublic:\n    int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {\n        const int maxPosition = 100;\n        std::vector<int> seatCount(maxPosition + 1, 0);\n        std::vector<int> studentCount(maxPosition + 1, 0);\n        \n        for (int seat : seats) {\n            seatCount[seat]++;\n        }\n        \n        for (int student : students) {\n            studentCount[student]++;\n        }\n        \n        int seatIdx = 0;\n        int studentIdx = 0;\n        int moves = 0;\n        \n        while (seatIdx <= maxPosition && studentIdx <= maxPosition) {\n            while (seatIdx <= maxPosition && seatCount[seatIdx] == 0) {\n                seatIdx++;\n            }\n            while (studentIdx <= maxPosition && studentCount[studentIdx] == 0) {\n                studentIdx++;\n            }\n            \n            if (seatIdx <= maxPosition && studentIdx <= maxPosition) {\n                int count = std::min(seatCount[seatIdx], studentCount[studentIdx]);\n                moves += count * std::abs(seatIdx - studentIdx);\n                seatCount[seatIdx] -= count;\n                studentCount[studentIdx] -= count;\n            }\n        }\n        \n        return moves;\n    }\n};\n```\n```python []\nclass Solution(object):\n    def minMovesToSeat(self, seats, students):\n        max_position = 100\n        seat_count = [0] * (max_position + 1)\n        student_count = [0] * (max_position + 1)\n        \n        for seat in seats:\n            seat_count[seat] += 1\n        \n        for student in students:\n            student_count[student] += 1\n        \n        seat_idx = 0\n        student_idx = 0\n        moves = 0\n        \n        while seat_idx <= max_position and student_idx <= max_position:\n            while seat_idx <= max_position and seat_count[seat_idx] == 0:\n                seat_idx += 1\n            while student_idx <= max_position and student_count[student_idx] == 0:\n                student_idx += 1\n            \n            if seat_idx <= max_position and student_idx <= max_position:\n                count = min(seat_count[seat_idx], student_count[student_idx])\n                moves += count * abs(seat_idx - student_idx)\n                seat_count[seat_idx] -= count\n                student_count[student_idx] -= count\n        \n        return moves\n\n        \n```\n```java []\nclass Solution {\n    public int minMovesToSeat(int[] seats, int[] students) {\n        int maxPosition = 100;\n        int[] seatCount = new int[maxPosition + 1];\n        int[] studentCount = new int[maxPosition + 1];\n        \n        for (int seat : seats) {\n            seatCount[seat]++;\n        }\n        \n        for (int student : students) {\n            studentCount[student]++;\n        }\n        \n        int seatIdx = 0;\n        int studentIdx = 0;\n        int moves = 0;\n        \n        while (seatIdx <= maxPosition && studentIdx <= maxPosition) {\n            while (seatIdx <= maxPosition && seatCount[seatIdx] == 0) {\n                seatIdx++;\n            }\n            while (studentIdx <= maxPosition && studentCount[studentIdx] == 0) {\n                studentIdx++;\n            }\n            \n            if (seatIdx <= maxPosition && studentIdx <= maxPosition) {\n                int count = Math.min(seatCount[seatIdx], studentCount[studentIdx]);\n                moves += count * Math.abs(seatIdx - studentIdx);\n                seatCount[seatIdx] -= count;\n                studentCount[studentIdx] -= count;\n            }\n        }\n        \n        return moves;\n    }\n\n}\n```\n\n
['Array', 'Greedy', 'Sorting', 'Python', 'C++', 'Java']