LeetCode 3505 | Minimum Operations to Make Elements Within K Subarrays Equal | Java | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3505 — Minimum Operations to Make Elements Within K Subarrays Equal using Sliding Window, Dual Fenwick Tree & Dynamic Programming in Java.
In this problem, we are given an integer array nums and two integers x and k. We want to find the minimum operations (each adding or subtracting 1 from an element) to obtain at least k non-overlapping subarrays of size exactly x where all elements within each subarray are equal. For any contiguous window of size x, the optimal equal value that minimizes the sum of absolute differences is the window median. Hence, calculating the minimum transformation cost for each potential subarray of length x is equivalent to a dynamic sliding window median and deviation problem.
We employ coordinate compression alongside two Fenwick Trees (Binary Indexed Trees) — one maintaining frequency counts and the other maintaining the sum of elements within the active window. Using binary lifting over powers of two on the Fenwick tree, we locate the median and compute the window cost in O(log n) time. Finally, we formulate a dynamic programming state transition over the precomputed subarray costs to select k non-overlapping blocks of size x, yielding an optimal O(n log n + k * n) time and O(n) auxiliary space solution.
🔥 Problem Highlights
✅ L1 norm mathematical property: equalizing window elements is minimized at the median
✅ Coordinate compression to bound values within distinct ranks for Fenwick Tree indexing
✅ Dual Fenwick Tree tracking counts and prefix sums in a sliding window of size x
✅ Binary lifting on the Fenwick tree to query the kth element rank in O(log n)
✅ Dynamic programming with rolling arrays to select k non-overlapping subarrays
✅ O(N log N + K * N) time complexity and O(N) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro & Day 102 Streak Celebration
00:34 Problem Understanding & Constraints Analysis
01:39 Key Breakthrough: Window Median & Dual Fenwick Tree
02:25 Binary Lifting on Fenwick Tree + Dynamic Programming
03:34 Optimal Java 17 Solution Walkthrough Line by Line
04:22 Test Cases Walkthrough & Day 102 Streak Celebration
04:57 Time Complexity Analysis (O(N log N + K * N))
05:33 Space Complexity Analysis (O(N) Auxiliary Space)
06:00 Summary & Outro!
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/solution.js
🔗 LeetCode Source Code
📌 https://codebytushu.com/leetcode/problem/minimum-operations-to-make-elements-within-k-subarrays-equal
🌐 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
Sliding Window Median
Binary Indexed Tree
Dynamic Programming
Coordinate Compression
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 is binary lifting on a Fenwick tree faster and more cache-friendly than binary searching the prefix sum?
1️⃣ It finds the k-th frequency prefix in O(log n) time without redundant BIT queries
2️⃣ It reduces space complexity from O(n) to O(1)
3️⃣ It avoids coordinate compression entirely
4️⃣ It sorts the window elements implicitly
#LeetCode3505 #LeetCode #MinimumOperationsToMakeElementsWithinKSubarraysEqual #Java #JavaDSA #FenwickTree #BinaryIndexedTree #DynamicProgramming #SlidingWindow #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3505 — Minimum Operations to Make Elements Within K Subarrays Equal using Sliding Window, Dual Fenwick Tree & Dynamic Programming in Java.
In this problem, we are given an integer array nums and two integers x and k. We want to find the minimum operations (each adding or subtracting 1 from an element) to obtain at least k non-overlapping subarrays of size exactly x where all elements within each subarray are equal. For any contiguous window of size x, the optimal equal value that minimizes the sum of absolute differences is the window median. Hence, calculating the minimum transformation cost for each potential subarray of length x is equivalent to a dynamic sliding window median and deviation problem.
We employ coordinate compression alongside two Fenwick Trees (Binary Indexed Trees) — one maintaining frequency counts and the other maintaining the sum of elements within the active window. Using binary lifting over powers of two on the Fenwick tree, we locate the median and compute the window cost in O(log n) time. Finally, we formulate a dynamic programming state transition over the precomputed subarray costs to select k non-overlapping blocks of size x, yielding an optimal O(n log n + k * n) time and O(n) auxiliary space solution.
🔥 Problem Highlights
✅ L1 norm mathematical property: equalizing window elements is minimized at the median
✅ Coordinate compression to bound values within distinct ranks for Fenwick Tree indexing
✅ Dual Fenwick Tree tracking counts and prefix sums in a sliding window of size x
✅ Binary lifting on the Fenwick tree to query the kth element rank in O(log n)
✅ Dynamic programming with rolling arrays to select k non-overlapping subarrays
✅ O(N log N + K * N) time complexity and O(N) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro & Day 102 Streak Celebration
00:34 Problem Understanding & Constraints Analysis
01:39 Key Breakthrough: Window Median & Dual Fenwick Tree
02:25 Binary Lifting on Fenwick Tree + Dynamic Programming
03:34 Optimal Java 17 Solution Walkthrough Line by Line
04:22 Test Cases Walkthrough & Day 102 Streak Celebration
04:57 Time Complexity Analysis (O(N log N + K * N))
05:33 Space Complexity Analysis (O(N) Auxiliary Space)
06:00 Summary & Outro!
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/04-November/3505-Minimum-Operations-to-Make-Elements-Within-K-Subarrays-Equal/solution.js
🔗 LeetCode Source Code
📌 https://codebytushu.com/leetcode/problem/minimum-operations-to-make-elements-within-k-subarrays-equal
🌐 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
Sliding Window Median
Binary Indexed Tree
Dynamic Programming
Coordinate Compression
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 is binary lifting on a Fenwick tree faster and more cache-friendly than binary searching the prefix sum?
1️⃣ It finds the k-th frequency prefix in O(log n) time without redundant BIT queries
2️⃣ It reduces space complexity from O(n) to O(1)
3️⃣ It avoids coordinate compression entirely
4️⃣ It sorts the window elements implicitly
#LeetCode3505 #LeetCode #MinimumOperationsToMakeElementsWithinKSubarraysEqual #Java #JavaDSA #FenwickTree #BinaryIndexedTree #DynamicProgramming #SlidingWindow #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description