_1151. Minimum Swaps to Group All 1's Together.md

1151. Minimum Swaps to Group All 1's Together

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

Back to top

---

First completed : March 01, 2025

Last updated : March 01, 2025

---

Related Topics : Array, Sliding Window

Acceptance Rate : 61.09 %

---

V1

Initial decently performing prefix sum + sliding window attempt.

V2

Optimized window finding by using a max function

V3

Optimized further (though at the expense of no longer being $O(1)$ space) by using itertools.accumulate to get the prefix sum.

Note: Built in functions are almost always more efficiently implemented due to them falling back on C.

---

Solutions

• m1151 v1.py
• m1151 v2.py
• m1151 v3.py

Python

m1151 v1.py

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        # convert data into a prefix sum starting at zero
        running_total = 0
        for i in range(len(data)) :
            data[i], running_total = running_total, running_total + data[i]
        data.append(running_total)

        tot_ones = data[-1]

        # Find window of size tot_ones with the most ones already there
        output = 0
        for i in range(tot_ones, len(data)) :
            output = max(output, data[i] - data[i - tot_ones])

        return tot_ones - output

m1151 v2.py

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        # convert data into a prefix sum starting at zero
        running_total = 0
        for i in range(len(data)) :
            data[i], running_total = running_total, running_total + data[i]
        data.append(running_total)

        tot_ones = data[-1]

        return min(tot_ones - (data[i] - data[i - tot_ones]) for i in range(tot_ones, len(data)))

m1151 v3.py

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        data = [0] + list(accumulate(data))
        tot_ones = data[-1]
        return tot_ones - max(data[i + tot_ones] - data[i] for i in range(len(data) - tot_ones))