What is the time complexity of Count Number of Nice Subarrays?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Count Number of Nice Subarrays?

This problem uses Array, Hash Table, Math, Sliding Window, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Count Number of Nice Subarrays?

Insight 1: The core idea is to realize that counting subarrays with exactly `k` odd numbers can be done by finding the difference between the number of subarrays with *at most* `k` odd numbers and the number of subarrays with *at most* `k-1` odd numbers. Insight 2: The 'atMost' function efficiently counts subarrays satisfying an upper bound constraint (at most k odd numbers) using a sliding window technique.

Which companies ask LeetCode 1248. Count Number of Nice Subarrays in interviews?

This problem is frequently asked at Deliveroo, Roblox.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Count Number of Nice Subarrays - LeetCode 1248 Solution

Q: How to solve Count Number of Nice Subarrays?

The solution uses the principle of inclusion-exclusion to efficiently count the number of subarrays with exactly k odd numbers. It calculates the number of subarrays with at most k odd numbers and then subtracts the number of subarrays with at most k-1 odd numbers. This difference gives the exact count of subarrays with k odd numbers. The `atMost` function uses the sliding window technique. The right pointer moves to the right, including more elements in the current window. The left pointer only moves when the number of odd numbers in the current window exceeds the specified limit, effectively shrinking the window from the left to satisfy the constraint.

Count Number of Nice Subarrays - Complete Solution Guide

Count Number of Nice Subarrays is LeetCode problem 1248, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array of integers nums and an integer k . A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays . Example 1: Input: nums = [1,1,2,1,1], k = 3 Output: 2 Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1]. Example 2: Input: nums = [2,4,6], k = 1 Output: 0 Explanation: There are no odd numbers in the array. Example 3: Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2 Output: 16 Constraints: 1 <= nums.length <= 5000

Detailed Explanation

The problem asks us to find the number of "nice" subarrays within a given array of integers, `nums`. A subarray is considered "nice" if it contains exactly `k` odd numbers. We need to count and return the number of such subarrays, given the array `nums` and the integer `k`.

Solution Approach

The solution uses the principle of inclusion-exclusion to efficiently count the number of subarrays with exactly k odd numbers. It calculates the number of subarrays with at most k odd numbers and then subtracts the number of subarrays with at most k-1 odd numbers. This difference gives the exact count of subarrays with k odd numbers. The `atMost` function uses the sliding window technique. The right pointer moves to the right, including more elements in the current window. The left pointer only moves when the number of odd numbers in the current window exceeds the specified limit, effectively shrinking the window from the left to satisfy the constraint.

Step-by-Step Algorithm

Step 1: Define a helper function `atMost(k_val)` that counts the number of subarrays with at most `k_val` odd numbers.
Step 2: Initialize `res = 0`, `left = 0`, and `odd_count = 0`. `res` will store the count of valid subarrays, `left` is the left boundary of the sliding window, and `odd_count` tracks the number of odd numbers in the current window.
Step 3: Iterate through the `nums` array using a `right` pointer (sliding window).
Step 4: For each `right`, check if `nums[right]` is odd. If it is, increment `odd_count`.
Step 5: While `odd_count > k_val`, shrink the window from the left by incrementing `left` and decrementing `odd_count` if `nums[left]` was odd.
Step 6: The current window `[left, right]` is valid. Add the number of subarrays ending at `right` to `res`. The number of such subarrays is `right - left + 1`.
Step 7: After the loop completes, the function returns `res`.
Step 8: Finally, in the main function `numberOfSubarrays`, return `atMost(k) - atMost(k - 1)`.

Key Insights

Insight 1: The core idea is to realize that counting subarrays with exactly `k` odd numbers can be done by finding the difference between the number of subarrays with *at most* `k` odd numbers and the number of subarrays with *at most* `k-1` odd numbers.
Insight 2: The 'atMost' function efficiently counts subarrays satisfying an upper bound constraint (at most k odd numbers) using a sliding window technique.
Insight 3: We can determine if a number is odd or even by using the modulo operator (%) efficiently, as `num % 2 == 1` implies an odd number.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Hash Table, Math, Sliding Window, Prefix Sum.

Companies

Asked at: Deliveroo, Roblox.

Count Number of Nice Subarrays | LeetCode 1248

Medium

Array Hash Table Math Sliding Window Prefix Sum

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k_val) {
        int res = 0;
        int left = 0;
        int odd_count = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 == 1) {
                odd_count += 1;
            }

            while (odd_count > k_val) {
                if (nums[left] % 2 == 1) {
                    odd_count -= 1;
                }
                left += 1;
            }

            res += (right - left + 1);
        }
        return res;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1248: Count Number of Nice Subarrays - Detailed explanation and solution approaches.

Topics

Array Hash Table Math Sliding Window Prefix Sum

Companies

DeliverooRoblox

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:1248

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Define a helper function `atMost(k_val)` that counts the number of subarrays with at most `k_val` odd numbers.
2
Step 2: Initialize `res = 0`, `left = 0`, and `odd_count = 0`. `res` will store the count of valid subarrays, `left` is the left boundary of the sliding window, and `odd_count` tracks the number of odd numbers in the current window.
3
Step 3: Iterate through the `nums` array using a `right` pointer (sliding window).
4
Step 4: For each `right`, check if `nums[right]` is odd. If it is, increment `odd_count`.
5
Step 5: While `odd_count > k_val`, shrink the window from the left by incrementing `left` and decrementing `odd_count` if `nums[left]` was odd.
6
Step 6: The current window `[left, right]` is valid. Add the number of subarrays ending at `right` to `res`. The number of such subarrays is `right - left + 1`.
7
Step 7: After the loop completes, the function returns `res`.
8
Step 8: Finally, in the main function `numberOfSubarrays`, return `atMost(k) - atMost(k - 1)`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The sliding window approach ensures that each element in the array is visited at most twice (once by the `right` pointer and once by the `left` pointer), resulting in O(n) time complexity. The algorithm uses only a few integer variables, independent of the input size, hence O(1) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Prefix Sum

Calculate the prefix sum of odd numbers. Then, iterate through all possible subarrays and check if the difference in prefix sums equals k.

Time: O(n^2)Space: O(n)

Trade-offs: The prefix sum approach is conceptually simpler but less efficient due to the nested loops for iterating through all possible subarrays. It's useful for understanding the problem but not recommended for large input sizes.

Hash Table

Use a hash table to store the count of each prefix sum of odd numbers. Iterate through the array, calculate prefix sums, and check if `prefix_sum - k` exists in the hash table. If it does, increment the count by the corresponding value in the hash table.

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

Trade-offs: This approach also has linear time complexity but has an overhead with the hash table which slows it down a bit and it is slightly less intuitive than the sliding window approach. Still this could be a viable method.

✨

Key Insights

1Insight 1: The core idea is to realize that counting subarrays with exactly `k` odd numbers can be done by finding the difference between the number of subarrays with *at most* `k` odd numbers and the number of subarrays with *at most* `k-1` odd numbers.
2Insight 2: The 'atMost' function efficiently counts subarrays satisfying an upper bound constraint (at most k odd numbers) using a sliding window technique.
3Insight 3: We can determine if a number is odd or even by using the modulo operator (%) efficiently, as `num % 2 == 1` implies an odd number.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

Edge Cases

Edge case 1: `k = 0`. If k is 0, the function `atMost(k - 1)` would call `atMost(-1)`. This will not cause an error as the logic of `atMost` continues to work with this negative number and still gives an accurate result. It effectively calculates the number of subarrays that have no odd numbers.
Edge case 2: `nums` contains no odd numbers. In this case, `atMost(k)` and `atMost(k-1)` will both return the same value which is the sum of the number of contiguous arrays in `nums`, causing the return value to be 0.
Edge case 3: `k > number of odd numbers in nums`. In this case, the function `atMost(k-1)` will return a value greater than zero. Thus the result will still calculate the correct number of subarrays.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to update the `odd_count` when shrinking the window from the left. The solution needs to decrement `odd_count` if `nums[left]` was odd.

✗Common mistake 2: Incorrectly calculating the number of subarrays ending at `right`. The number of such subarrays is `right - left + 1`, not just `right - left`.

✗Common mistake 3: Trying to directly count subarrays with *exactly* k odd numbers in the main loop, which leads to a more complex and less efficient solution. Using the atMost function to solve the problem simplifies it a lot.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing network traffic data. You might want to identify time windows (subarrays) where the number of error packets (odd numbers) is within a specific range.

🏦Real-world scenario 2: Financial data analysis. Identifying time periods (subarrays) where the number of days with positive returns (odd numbers) meets a certain criteria for investment strategy analysis.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Count Number of Nice Subarrays"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?