LC-1703 Hard LeetCode

1703. Minimum Adjacent Swaps for K Consecutive Ones

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 42% Topics: Array, Greedy, Sliding Window, Prefix Sum

Reading material

Arrays & Hashing 12 min Greedy 11 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def minMoves(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def moves(i, j):
            return prefix[j+1]-prefix[i]

        idxs = [i for i, x in enumerate(nums) if x]
        prefix = [0]*(len(idxs)+1)
        for i in xrange(len(idxs)):
            prefix[i+1] = prefix[i]+idxs[i]
        result = float("inf")
        for i in xrange(len(idxs)-k+1):
            result = min(result, -moves(i, i+k//2-1) + moves(i+(k+1)//2, i+k-1))  # take each i+k//2 as median, find min dist to median
        result -= (k//2)*((k+1)//2)  # rollback extra moves to the expected positions
        return result

Solution from kamyu104/LeetCode-Solutions · MIT