_3189. Minimum Moves to Get a Peaceful Board.md

3189. Minimum Moves to Get a Peaceful Board

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 20, 2024

Last updated : August 20, 2024

---

Related Topics : Array, Greedy, Sorting, Counting Sort

Acceptance Rate : 76.42 %

---

Not the most efficient. Could probably do this with a stack and counting sort but it is effective enough. This would end up being $O(nlogn)$ due to the heap process and sorting.

---

Solutions

• m3189.py

Python

m3189.py

class Solution:
    def minMoves(self, rooks: List[List[int]]) -> int:
        remainingRows = set(range(len(rooks)))
        remainingCols = remainingRows.copy()
        extraRows = []
        extraCols = []

        for x, y in rooks :
            if x in remainingRows :
                remainingRows.remove(x)
            else :
                heapq.heappush(extraRows, x)

            if y in remainingCols :
                remainingCols.remove(y)
            else :
                heapq.heappush(extraCols, y)

        remainingRows = sorted(list(remainingRows), reverse=True)
        remainingCols = sorted(list(remainingCols), reverse=True)
        output = 0

        while remainingRows :
            output += abs(remainingRows.pop() - heapq.heappop(extraRows))
        while remainingCols :
            output += abs(remainingCols.pop() - heapq.heappop(extraCols))


        return output