LeetCode 3721 | Longest Balanced Subarray II | Java | Hard | Segment Tree | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3721 — Longest Balanced Subarray II using Segment Tree, Array, and Hash Table in Java.
We need to find the maximum length of a contiguous subarray in an array named nums where the number of distinct even integers equals the number of distinct odd integers. We assign a parity weight of plus one to distinct even numbers and minus one to distinct odd numbers. A subarray is balanced when its cumulative balance score equals zero.
As we move the right endpoint r from left to right, newly encountered values only affect left endpoints that start after the previous occurrence of the same value. This transforms element parity updates into range addition operations on the candidate left endpoints.
To handle arrays containing up to 100,000 elements efficiently, we maintain balance scores across all left endpoints using a lazy Segment Tree. Removing one element from the left changes the parity balance by at most one, so adjacent balance scores never skip values. By the Discrete Intermediate Value Theorem, a range contains zero if its minimum is at or below zero and its maximum is at or above zero. This helps us find the earliest matching left endpoint in logarithmic time, achieving O(n log n) runtime and O(n + U) auxiliary space.
🔥 Problem Highlights
✅ Parity balance mapping using plus one for distinct even numbers and minus one for distinct odd numbers
✅ Lazy Segment Tree for range additions across candidate left endpoints
✅ Range updates from the previous occurrence plus one to the current right endpoint
✅ Discrete Intermediate Value Theorem to identify zero balance in O(log n) time
✅ Efficient O(n log n) time complexity for arrays containing up to 100,000 elements
✅ Reduced memory overhead using flat primitive arrays
⏱️ TIMESTAMPS
00:00 Intro
00:57 Problem Understanding and Constraints
01:55 Segment Tree and Discrete IVT Insight
03:35 Lazy Propagation Rebalancing Strategy
05:05 Java Code Walkthrough
06:20 Execution and Test Cases
08:10 Time Complexity Analysis O(n log n)
09:02 Space Complexity Analysis O(n + maxVal)
09:47 Outro and Wrap-up
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/solution.js
🔗 LeetCode Source Code
📌 Add the link here
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Segment Tree Range Queries and Lazy Propagation
Discrete Intermediate Value Theorem
Subarray Parity Balancing
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does the Discrete Intermediate Value Theorem apply to the balance scores across adjacent left endpoints?
1️⃣ Because all numbers in nums are strictly positive
2️⃣ Because removing one element from the left changes the distinct parity count by at most one, so the difference between consecutive balance scores is at most one in absolute value
3️⃣ Because the Segment Tree always sorts values in non-decreasing order
4️⃣ Because the number of distinct even numbers is always greater than the number of distinct odd numbers
#LeetCode3721 #LeetCode #LongestBalancedSubarrayII #Java #JavaDSA #SegmentTree #Array #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3721 — Longest Balanced Subarray II using Segment Tree, Array, and Hash Table in Java.
We need to find the maximum length of a contiguous subarray in an array named nums where the number of distinct even integers equals the number of distinct odd integers. We assign a parity weight of plus one to distinct even numbers and minus one to distinct odd numbers. A subarray is balanced when its cumulative balance score equals zero.
As we move the right endpoint r from left to right, newly encountered values only affect left endpoints that start after the previous occurrence of the same value. This transforms element parity updates into range addition operations on the candidate left endpoints.
To handle arrays containing up to 100,000 elements efficiently, we maintain balance scores across all left endpoints using a lazy Segment Tree. Removing one element from the left changes the parity balance by at most one, so adjacent balance scores never skip values. By the Discrete Intermediate Value Theorem, a range contains zero if its minimum is at or below zero and its maximum is at or above zero. This helps us find the earliest matching left endpoint in logarithmic time, achieving O(n log n) runtime and O(n + U) auxiliary space.
🔥 Problem Highlights
✅ Parity balance mapping using plus one for distinct even numbers and minus one for distinct odd numbers
✅ Lazy Segment Tree for range additions across candidate left endpoints
✅ Range updates from the previous occurrence plus one to the current right endpoint
✅ Discrete Intermediate Value Theorem to identify zero balance in O(log n) time
✅ Efficient O(n log n) time complexity for arrays containing up to 100,000 elements
✅ Reduced memory overhead using flat primitive arrays
⏱️ TIMESTAMPS
00:00 Intro
00:57 Problem Understanding and Constraints
01:55 Segment Tree and Discrete IVT Insight
03:35 Lazy Propagation Rebalancing Strategy
05:05 Java Code Walkthrough
06:20 Execution and Test Cases
08:10 Time Complexity Analysis O(n log n)
09:02 Space Complexity Analysis O(n + maxVal)
09:47 Outro and Wrap-up
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/11-February/3721-Longest-Balanced-Subarray-II/solution.js
🔗 LeetCode Source Code
📌 Add the link here
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Segment Tree Range Queries and Lazy Propagation
Discrete Intermediate Value Theorem
Subarray Parity Balancing
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does the Discrete Intermediate Value Theorem apply to the balance scores across adjacent left endpoints?
1️⃣ Because all numbers in nums are strictly positive
2️⃣ Because removing one element from the left changes the distinct parity count by at most one, so the difference between consecutive balance scores is at most one in absolute value
3️⃣ Because the Segment Tree always sorts values in non-decreasing order
4️⃣ Because the number of distinct even numbers is always greater than the number of distinct odd numbers
#LeetCode3721 #LeetCode #LongestBalancedSubarrayII #Java #JavaDSA #SegmentTree #Array #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description