Number of Sub-arrays With Odd Sum | Brute Force | Better | Optimal | Leetcode 1524 |codestorywithMIK
569iPad PDF Notes - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad PDF Notes/Leetcode - 1524.pdf
Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
Hi Everyone, this is the 143rd video of our Playlist "Arrays 1D/2D : Popular Interview Problems".
Now we will be solving a good Graph problem - Number of Sub-arrays With Odd Sum | Brute Force | Better | Optimal | Detailed | Leetcode 1524 | codestorywithMIK
Problem Name : Number of Sub-arrays With Odd Sum | Brute Force | Better | Optimal | Detailed | Leetcode 1524 | codestorywithMIK
Company Tags : will update later
My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/Cumulative_Sum(Prefix Array)/Number of Sub-arrays With Odd Sum.cpp
Leetcode Link : https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Segment Tree Concepts Playlist : • Segment Tree | Introduction | Basics ...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
Trie Playlist - • Word Search II (Google, Amazon, Meta,...
Difference Array Technique: Concepts & Qns : • Introduction | What | How | Differenc...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Video Summary :
Approach-1 (Brute Force): This method considers all possible subarrays and checks if their sum is odd. Due to its O(n³) complexity, it is highly inefficient for large inputs.
Approach-2 (Better Brute Force): Instead of recalculating sums for each subarray from scratch, it maintains a running sum. This reduces the time complexity to O(n²), making it slightly better but still suboptimal.
Approach-3 (Optimal using Prefix Sum Array):
The idea is to use a prefix sum to track cumulative sums efficiently. Instead of checking each subarray individually, we count how many prefix sums are odd or even.
If the current prefix sum is even, the number of valid subarrays is equal to the count of odd prefix sums encountered so far.
If the prefix sum is odd, the valid subarrays count is derived from the even prefix sums seen previously.
This approach helps us count odd-sum subarrays efficiently in O(n) time using additional space for prefix sums.
Approach-4 (Optimal using Constant Space): Instead of maintaining a prefix sum array, we only track two values: the count of odd and even prefix sums seen so far. This allows us to achieve O(n) time and O(1) space, making it the most efficient approach.
✨ Timelines✨
00:00 - Introduction
0:22 - Motivation
0:53 - Problem Explanation
1:53 - Brute Force
4:29 - Better Brute Force
7:05 - Optimal Approach Intuition Building
10:43 - Already studied concept example
12:11 - Dry Run for Optimal Approach
27:41 - Coding Optimal using O(n) space
31:00 - Coding Optimal using O(1) space
#MIK #mik #Mik
#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 #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik