Count Number of Nice Subarrays | 2 Approaches | Similar Concept | Leetcode 1248 | codestorywithMIK
370iPad PDF Link - https://github.com/MAZHARMIK/Intervie...
Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 93rd Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good Array based Problem : Count Number of Nice Subarrays | 2 Approaches | Similar Concept | Leetcode 1248 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Count Number of Nice Subarrays | 2 Approaches | Similar Concept | Leetcode 1248 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/count-n...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using Prefix Sum and Hashmap
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(n)
This approach leverages the prefix sum technique combined with a hashmap to efficiently count subarrays with exactly k odd numbers.
Initialization:
mp (unordered_map) to store the frequency of prefix sums.
Variables: n (length of nums), count (result count), and currSum (current prefix sum).
Iterate Through Array:
For each element, update currSum by adding 1 if the element is odd (nums[i] % 2), else add 0.
Check if currSum - k exists in mp. If it does, increment count by the frequency of currSum - k.
Update mp to include the current currSum.
This method ensures that each subarray's prefix sum is calculated in linear time, and the hashmap provides efficient lookups for the required subarray sums.
Approach 2: Sliding Window (Khandani Template with a Twist)
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(1)
This approach utilizes a sliding window technique to dynamically count subarrays containing exactly k odd numbers.
Initialization:
Variables: n (length of nums), oddCount (number of odd numbers in the current window), count (subarrays ending at the current position), result (total count of valid subarrays), and two pointers i and j (window boundaries).
Sliding Window:
Iterate with j from 0 to n-1. For each element:
If the element is odd, increment oddCount and reset count to 0.
While oddCount equals k, increment count and adjust the window by incrementing i and decreasing oddCount if the element at i is odd.
Add count to result.
This method maintains a sliding window that expands and contracts based on the number of odd numbers, ensuring efficient computation in linear time with constant space.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024