Intuition and Thought Process with code explained
The questions asks for the minimum number of swaps to group all the 1\'s together at any location.\n\n\nThought process:\n\n I initially started thinking in ter
The questions asks for the minimum number of swaps to group all the 1\'s together at **any location**.\n\n\nThought process:\n\n* I initially started thinking in terms of sorting the array in non-increasing order (**this meant brining all the 1\'s to the front of the array**). I then thought of using xor (**with bitset in c++**) to see the number of positions at which the original array and the sorted array differ. The number of positions at which they differ(i.e. the count of set bits in result of xor) will be equal to the number of swaps needed. This thought process gave me the realisation that sorting the array to bring all 1\'s to front of the array is just one possibility of how all the 1\'s can be grouped together. This can be better understood with an example. \n* Consider nums = [0,0, 1, 0,  1, 1,] => nums_modified= [1, 1, 1, 0, 0, 0]. It is clear from the earlier observation that nums_modified array is just one possible form of rearrangement to group all the 1\'s together. The other forms of rearrangement that group all 1\'s together include [0, 1, 1, 1, 0, 0] or [0,0,1,1,1,0] or [1, 0, 0, 0, 1, 1] ....so on. It is important to note that all of these rearrangements just differ in the position at which the group of 1\'s begins.\n* Now the ultimate aim would be to check which of these possible rearrangements of the original array will result in minimum number of swaps.\n* To break down the problem into simpler sub-problems, I wanted to first find out the number of swaps needed to convert the original array to any of the possible rearrangements. In a logical sense, it is easy to observe that the number of 0\'s that overlap with 1\'s is the number of swaps needed for the conversion.\n* The only part left is finding the number of swaps needed to convert the original array to each of the possible rearrangement and return the minimum number of swaps. This observation helped me in identifying the crux of the problem which is **Sliding window.**\n* The size of the window would be equal to the number of 1\'s and the number of swaps will be equal to the number of 0\'s in each of the window\'s of size k.\n\n```\nclass Solution {\npublic:\n    int minSwaps(vector<int>& nums) {\n        int n = nums.size();\n        int k = count(nums.begin(), nums.end(), 1);\n        \n        if(k <= 1 || k == n) return 0; //some minor optimizations\n        \n        //the window [i......j] is of size k\n\t\tint ans = INT_MAX, i = 0, j = 0, count = 0;\n        \n        while(i < n){\n\t\t\n\t\t//increement swaps count if 0 is encountered in the window\n            if(nums[j] == 0)\n                ++count;\n            \n            //when the window size becomes k, increement i(i.e. sliding the window)\n\t\t\tif((j - i + 1 + n)%n == k){\n                ans = min(ans, count);\n                if(nums[i] == 0)\n                    count--;\n                ++i;\n            }\n            \n            j = (j + 1)%n;   \n        }\n        return ans;   \n    }\n};\n```\n\n
['C', 'Sliding Window', 'C++']