From 3dd518795de5a8372b39a6f6984acb0b2d5d5dbc Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 1 Aug 2024 21:42:36 -0600 Subject: 2134. minimum swaps to group all 1's together --- min_swap_group_1.c | 3 +-- min_swap_group_1.py | 33 +++++++++++++++++++++++++++++++++ 2 files changed, 34 insertions(+), 2 deletions(-) create mode 100644 min_swap_group_1.py diff --git a/min_swap_group_1.c b/min_swap_group_1.c index 4fa2384..2536259 100644 --- a/min_swap_group_1.c +++ b/min_swap_group_1.c @@ -1,6 +1,5 @@ // 2134. Minimum Swaps to Group All 1's Together II -#include -#include +#include "leetcode.h" #pragma GCC optimize("-O3") /* diff --git a/min_swap_group_1.py b/min_swap_group_1.py new file mode 100644 index 0000000..4365fa8 --- /dev/null +++ b/min_swap_group_1.py @@ -0,0 +1,33 @@ +# 2134. Minimum Swaps to Group All 1's Together II + +""" +a swap is defined as taking two distinct position in an array and swapping +the values in them. a circular array is defined as an array where we consider +the first element and the last element to adjacent. given a binary circular +array 'nums', return the minimum number of swaps required to group all 1's +preent in the array together at any location. +""" + + +class Solution(object): + def minSwaps(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + ones, nums = nums.count(1), nums + nums + x, curr_ones = 0, 0 + for i in range(len(nums)): + if i >= ones and nums[i - ones]: + x -= 1 + if nums[i] == 1: + x += 1 + curr_ones = max(x, curr_ones) + return ones - curr_ones + + +if __name__ == "__main__": + obj = Solution() + print(obj.minSwaps(nums=[0, 1, 0, 1, 1, 0, 0])) + print(obj.minSwaps(nums=[0, 1, 1, 1, 0, 0, 1, 1, 0])) + print(obj.minSwaps(nums=[1, 1, 0, 0, 1])) -- cgit v1.2.3