🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve the problem of finding the number of "nice" subarrays (subarrays with exactly k
odd numbers), we can use a two-pointer (or sliding window) approach. The idea is to maintain a window of elements that contains exactly k
odd numbers and calculate how many such subarrays can be formed by shifting the window along the array.
Approach
- Initialize Variables: Start with two pointers,
l
(left) andr
(right), both set to the beginning of the array. Use a variableres
to count the number of nice subarrays, andcount
to keep track of the number of odd numbers in the current window. - Expand the Window: Move the right pointer
r
to the right, expanding the window until the window contains exactlyk
odd numbers. - Count Subarrays: Once the window contains exactly
k
odd numbers, count how many subarrays end atr
and start at positions betweenl
and the currentl
. Incrementres
by the number of valid subarrays. - Shrink the Window: Move the left pointer
l
to the right to reduce the number of odd numbers in the window. Adjustl
until the window no longer containsk
odd numbers. - Repeat: Repeat steps 2-4 until the right pointer
r
reaches the end of the array. - Return Result: Return the total count of nice subarrays stored in
res
.
The approach ensures that we efficiently count the number of subarrays by leveraging the sliding window technique, which avoids the need for nested loops and thus improves performance.
Complexity
- Time Complexity:
O(n)
, wheren
is the length of the input array. Each element is processed at most twice (once by the right pointer and once by the left pointer). - Space Complexity:
O(1)
, since we only use a fixed amount of extra space for pointers and counters.
Code
C++
class Solution {
public:
int minOperations(vector& nums) {
bool flag = true;
int res = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if ((nums[i] != 0) != flag) {
flag = !flag;
++res;
}
}
return res;
}
};
Python
class Solution:
def minOperations(self, nums: List[int]) -> int:
flag = True
res = 0
n = len(nums)
for i in range(n):
if (nums[i] != 0) != flag:
flag = not flag
res += 1
return res
Java
public class Solution {
public int minOperations(List nums) {
boolean flag = true;
int res = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if ((nums.get(i) != 0) != flag) {
flag = !flag;
++res;
}
}
return res;
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var minOperations = function (nums) {
var flag = true;
var res = 0;
var n = nums.length;
for (var i = 0; i < n; ++i) {
if (nums[i] ^ flag) {
flag = !flag;
++res;
}
}
return res;
};
Go
func minOperations(nums []int) int {
flag := true
res := 0
n := len(nums)
for i := 0; i < n; i++ {
if (nums[i] != 0) != flag {
flag = !flag
res++
}
}
return res
}
C#
public class Solution {
public int MinOperations(List nums) {
bool flag = true;
int res = 0;
int n = nums.Count;
for (int i = 0; i < n; ++i) {
if ((nums[i] != 0) != flag) {
flag = !flag;
++res;
}
}
return res;
}
}