Balanced Frequency Balance — Problem Statement & Solution Guide
Problem Description
Given an array of integers, calculate the balanced frequency balance by finding the next greater element for each number and summing up the differences. If the next greater element is not found, consider the next smaller element.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Frequency Balance"
WHY DOES IT MATTER?
Monotonic stack patterns solve a broad class of "next/previous" queries (greater, smaller, greater-or-equal, etc.) that appear in stock span, histogram area, and temperature prediction problems. Mastering this pattern equips engineers to replace quadratic scans with linear solutions, a critical skill for performance‑critical code.
OPTIMIZATION CHALLENGE
The key insight is that only elements that have not yet found a qualifying neighbor need to be remembered. By discarding elements as soon as a larger (or smaller) value appears, the stack never grows beyond O(n) and each element is processed a constant number of times, collapsing the naive O(n²) scan into O(n).
REAL-WORLD CONNECTION
Think of a conveyor belt with packages of varying heights. As each package passes, a sensor records the first taller package that follows; if none appears, it records the first shorter one. Using a stack is akin to keeping a temporary holding area of packages whose taller neighbor hasn't arrived yet, ensuring the belt's throughput stays constant.
During an interview, push indices—not values—onto the stack. This lets you compute the exact difference (arr[i] - arr[nextIdx]) later without extra lookups, and it also simplifies handling duplicate values and tie‑breaking rules.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Balanced Frequency Balance problem is a variant of the classic Next Greater Element (NGE) challenge. The naive solution scans to the right of each array element, looking for the first larger value; if none exists, it then scans again for the first smaller value. This double‑scan leads to O(n²) time on large inputs, quickly exceeding limits for arrays with millions of elements. The optimal paradigm leverages a monotonic stack—a data structure that maintains elements in a strictly decreasing (or increasing) order—to resolve the “next” relationship in a single linear pass. By pushing indices onto the stack and popping when a larger (or smaller) element is encountered, we can instantly determine the nearest qualifying neighbor for every position, achieving O(n) time while using O(n) auxiliary space for the stack and result arrays.
Interview Questions on This Problem
Q1How would you modify the monotonic stack solution if the problem required the next greater element on the left instead of the right?
Traverse the array from left to right while maintaining a decreasing stack of indices. For each element, pop until the top of the stack is greater; the top then represents the nearest greater on the left. Push the current index afterward. This mirrors the right‑side solution but reverses the traversal direction.
Q2Can you compute both the next greater and next smaller elements in a single pass without using two separate stacks?
Yes. Use a single stack that stores indices of elements whose next greater hasn't been found yet. When a larger element arrives, it resolves NGE for popped indices. Simultaneously, maintain a secondary stack (or reuse the same by tracking state) for elements awaiting a smaller neighbor; when a smaller element appears, it resolves those pending entries. This hybrid approach still runs in O(n) time.
Q3What is the impact on time and space complexity if the array is circular (i.e., you can wrap around to the start when searching for the next greater/smaller element)?
A circular array can be handled by iterating twice over the input (2n steps) while using the same monotonic stack logic. The time remains O(n) because each element is pushed and popped at most twice, and the space stays O(n) for the stack and result arrays.
Examples
Input
[3, 2, 11, 10]
Output
16
Explanation: Step-by-step: with input [3, 2, 11, 10], we find the next greater element for each number. For 3, the next greater element is 11, so the difference is 11-3 = 8. For 2, the next greater element is 11, so the difference is 11-2 = 9. For 11, the next greater element is not found, so we consider the next smaller element which is 10, and the difference is 10-11 = -1. For 10, the next greater element is not found, so we consider the next smaller element which is itself, and the difference is 10-10 = 0. The sum of the differences is 8 + 9 - 1 = 16.
Input
[10, 10, 10]
Output
0
Explanation: Step-by-step: with input [10, 10, 10], we find the next greater element for each number. Since all numbers are the same, the next greater element is not found for any number. So, we consider the next smaller element which is the same number for each, resulting in differences of 0. The sum of the differences is 0 + 0 + 0 = 0.
Constraints
- 1 <= N <= 10^5
- -10^9 <= arr[i] <= 10^9
- Time Complexity expected: O(N) or O(N log N)
- Space Complexity expected: O(1) or O(N)
Optimal Approach & Strategy
Use a decreasing monotonic stack to find next greater elements in one linear pass; for elements without a greater neighbor, run a second linear pass with an increasing stack to locate the next smaller element. Both passes together run in O(n) time.
Brute Force Approach
For each element, scan rightward until you encounter a larger number; if none, scan again for a smaller number, then add the difference. This double nested loop costs O(n²) time.
Verified Code Solutions
function solution(nums) { if (nums.length === 0) return 0; let stack = [], result = 0; for (let i = 0; i < nums.length; i++) { while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) { let idx = stack.pop(); result += nums[i] - nums[idx]; } stack.push(i); } for (let i = 0; i < stack.length; i++) { let idx = stack[i]; let nextSmaller = Infinity; for (let j = idx + 1; j < nums.length; j++) { if (nums[j] < nums[idx]) { nextSmaller = nums[j]; break; } } if (nextSmaller === Infinity) nextSmaller = nums[idx]; result += nextSmaller - nums[idx]; } return result; }class Solution { public: int solution(vector<int>& nums) { if (nums.empty()) return 0; vector<int> stack; int result = 0; for (int i = 0; i < nums.size(); i++) { while (!stack.empty() && nums[stack.back()] < nums[i]) { int idx = stack.back(); stack.pop_back(); result += nums[i] - nums[idx]; } stack.push_back(i); } for (int i = 0; i < stack.size(); i++) { int idx = stack[i]; int nextSmaller = INT_MAX; for (int j = idx + 1; j < nums.size(); j++) { if (nums[j] < nums[idx]) { nextSmaller = nums[j]; break; } } if (nextSmaller == INT_MAX) nextSmaller = nums[idx]; result += nextSmaller - nums[idx]; } return result; } }class Solution { public int solution(int[] nums) { if (nums.length == 0) return 0; int[] stack = new int[nums.length]; int top = -1, result = 0; for (int i = 0; i < nums.length; i++) { while (top >= 0 && nums[stack[top]] < nums[i]) { int idx = stack[top--]; result += nums[i] - nums[idx]; } stack[++top] = i; } for (int i = 0; i <= top; i++) { int idx = stack[i]; int nextSmaller = Integer.MAX_VALUE; for (int j = idx + 1; j < nums.length; j++) { if (nums[j] < nums[idx]) { nextSmaller = nums[j]; break; } } if (nextSmaller == Integer.MAX_VALUE) nextSmaller = nums[idx]; result += nextSmaller - nums[idx]; } return result; } }def solution(nums): if not nums: return 0 stack, result = [], 0 for i in range(len(nums)): while stack and nums[stack[-1]] < nums[i]: idx = stack.pop() result += nums[i] - nums[idx] stack.append(i) for i in range(len(stack)): idx = stack[i] next_smaller = float('inf') for j in range(idx + 1, len(nums)): if nums[j] < nums[idx]: next_smaller = nums[j] break if next_smaller == float('inf'): next_smaller = nums[idx] result += next_smaller - nums[idx] return resultfunction solution(nums) { if (nums.length === 0) return 0; let stack = [], result = 0; for (let i = 0; i < nums.length; i++) { while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) { let idx = stack.pop(); result += nums[i] - nums[idx]; } stack.push(i); } for (let i = 0; i < stack.length; i++) { let idx = stack[i]; let nextSmaller = Infinity; for (let j = idx + 1; j < nums.length; j++) { if (nums[j] < nums[idx]) { nextSmaller = nums[j]; break; } } if (nextSmaller === Infinity) nextSmaller = nums[idx]; result += nextSmaller - nums[idx]; } return result; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.