<p>You are given an integer array, <code>nums</code>, and an integer <code>k</code>. <code>nums</code> comprises of only <code>0</code>&#39;s and <code>1</code>&#39;s. In one move, you can choose two <strong>adjacent</strong> indices and swap their values.</p>

<p>Return <em>the <strong>minimum</strong> number of moves required so that </em><code>nums</code><em> has </em><code>k</code><em> <strong>consecutive</strong> </em><code>1</code><em>&#39;s</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,1,0,1], k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> In 1 move, nums could be [1,0,0,0,<u>1</u>,<u>1</u>] and have 2 consecutive 1&#39;s.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,0,0,0,1,1], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,<u>1</u>,<u>1</u>,<u>1</u>].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,0,1], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> nums already has 2 consecutive 1&#39;s.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums[i]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= k &lt;= sum(nums)</code></li>
</ul>

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        if k==1:
            return 0
        ones_inds = [i for i in range(len(nums)) if nums[i]==1]
        if k == 2:
            return min([ones_inds[i]-ones_inds[i-1]-1 for i in range(1, len(ones_inds))])
        left_count = 0
        right_count = 0
        count_arr = [-1]*(k-1)
        left_swaps = 0
        right_swaps = 0
        for i in range(0,len(count_arr)):
            count_arr[i] = ones_inds[i+1]-ones_inds[i]-1
            steps = min(i+1,k-1-i)
            if steps == k-1-i:
                right_swaps +=steps*count_arr[i]
            else:
                left_swaps += steps*count_arr[i]


        total_swaps = left_swaps + right_swaps
        mid_int = int((k-1)/2)
        left_count = sum(count_arr[0:mid_int])
        right_count = sum(count_arr[mid_int:k-1])  
        min_swaps = total_swaps    
        #print(count_arr)
        #print((left_swaps, right_swaps)) 
        #print((left_count, right_count))
        #print(mid_int)
        #print("--") 
        #[1,0,0,1,0,1,0,0,0,1,0,0,1,1,0,0,1,1,0,1]
        #print(left_count,right_count)
        #print("START")
        for i in range(1,len(ones_inds)-(k-1)):
            #print("i:"+str(i))
            #print(ones_inds)

            #print("left swap:"+str(left_swaps))
            left_swaps -= left_count
            #print("left swap:"+str(left_swaps))
            #print("mid int:"+str(mid_int))
            middle_count = ones_inds[mid_int+1]-ones_inds[mid_int]-1
            #print("middle count:"+str(middle_count))
            left_swaps += middle_count*int((k-1)/2)
            #print("left swap:"+str(left_swaps))
           
            left_count += middle_count
            left_count -=( ones_inds[i]-ones_inds[i-1]-1)
            right_count -= middle_count
            #print("left and right count:")
            #print((left_count, right_count))
            right_swaps -= middle_count*int(k/2)
            right_swaps+= right_count
            
            added_count= (ones_inds[i+k-1]-ones_inds[i+k-2]-1)
            right_count += added_count
            right_swaps += added_count
            #print("right_swaps:"+str(right_swaps))

            total_swaps = left_swaps + right_swaps
            #print("total swaps:"+str(total_swaps))
            #print(left_count, right_count)
            min_swaps = min(min_swaps, total_swaps)
            mid_int += 1
            #print(nums)

        return min_swaps




23500