Dynamic Stream Minimum — Problem Statement & Solution Guide
Problem Description
Given an array of integers, determine the value obtained by subtracting the largest element from the total sum of all elements. The input consists of two lines: the first line contains an integer N (1 ≤ N ≤ 10^5) representing the number of elements, and the second line contains N space‑separated integers, each in the range [−10^9, 10^9]. The output is a single integer equal to (sum of all elements) − (maximum element).
DSA Pattern Breakdown
DSA Pattern Breakdown
"Dynamic Stream Minimum"
WHY DOES IT MATTER?
The scan/aggregation pattern is fundamental because many real‑world metrics (totals, minima, maxima, averages) can be derived in a single pass, enabling algorithms to scale to massive data streams without costly recomputation.
OPTIMIZATION CHALLENGE
The key insight is recognizing that both required values (sum and max) are *associative* and can be updated incrementally; no need for sorting, extra arrays, or repeated traversals.
REAL-WORLD CONNECTION
Think of a financial dashboard that continuously receives transaction amounts. To display "total revenue minus the biggest transaction" in real time, the system only needs to keep a running total and the current largest transaction, mirroring the algorithm's state.
During an interview, write the loop that updates sum and max side‑by‑side, and immediately compute the answer after the loop. This demonstrates both correctness and awareness of constant‑space optimization.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The task reduces to computing two aggregate values over a sequence: the total sum of all elements and the maximum element. A naive solution might recompute these aggregates for each query or use nested loops, leading to O(N^2) time, which is infeasible for N up to 10^5. The optimal paradigm leverages a single linear scan, updating both the running sum and the current maximum in constant time per element, yielding O(N) overall. This approach exemplifies the "scan" or "prefix aggregation" pattern, where a problem can be solved by maintaining a small amount of state while iterating through the data, eliminating the need for extra data structures or repeated passes.
Interview Questions on This Problem
Q1How would you modify the solution if the array is presented as a real‑time stream and you must output the result after each new element arrives?
Maintain two variables – cumulative sum and current maximum – and update them with each incoming element. After processing the i‑th element, output sum - max. This keeps the per‑element work O(1) and uses O(1) extra space.
Q2What changes are required if the problem asks for sum minus the *second* largest element instead of the largest?
Track both the largest and second‑largest values while scanning. When a new element exceeds the current max, shift the old max to second‑max; otherwise, update second‑max if the element lies between them. The rest of the algorithm remains linear.
Q3Can you solve the problem using a binary‑search‑tree (BST) or heap, and what would be the trade‑offs compared to the linear scan?
Inserting each element into a max‑heap or BST gives O(log N) per insertion, allowing O(N log N) total time and O(N) space to retrieve the maximum. While functional, it is slower and uses more memory than the O(N) scan with O(1) extra space, making it sub‑optimal for large N.
Examples
Input
5 1 2 3 4 5
Output
10
Explanation: The sum of the array is 1+2+3+4+5 = 15. The maximum element is 5. Subtracting gives 15 − 5 = 10.
Input
4 -3 -1 -4 -2
Output
-9
Explanation: Sum = -3-1-4-2 = -10. Maximum = -1. Result = -10 − (-1) = -9.
Input
3 0 0 0
Output
0
Explanation: Sum = 0, maximum = 0, so 0 − 0 = 0.
Input
6 1000000000 -1000000000 500000000 -500000000 0 1
Output
-999999999
Explanation: Sum = 1000000000-1000000000+500000000-500000000+0+1 = 1. Maximum = 1000000000. Result = 1 − 1000000000 = -999999999.
Constraints
- 1 <= N <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The final answer fits within a 64‑bit signed integer.
Optimal Approach & Strategy
Combine the two passes into a single loop that updates both sum and max simultaneously, achieving O(N) time with only O(1) extra memory.
Brute Force Approach
Compute the sum by iterating over the array, then find the maximum by a second separate loop; this uses two passes, O(N) time but still O(N) overall, which is acceptable but not optimal in constant‑factor terms.
Verified Code Solutions
function solution(nums) {
if (!nums || nums.length === 0) return 0;
let sum = 0;
let maxVal = -Infinity;
for (const num of nums) {
sum += num;
if (num > maxVal) maxVal = num;
}
return sum - maxVal;
}#include <vector>
#include <climits>
class Solution {
public:
long long solution(const std::vector<int>& nums) {
if (nums.empty()) return 0;
long long sum = 0;
int maxVal = INT_MIN;
for (int num : nums) {
sum += num;
if (num > maxVal) {
maxVal = num;
}
}
return sum - maxVal;
}
};class Solution {
public long solution(int[] nums) {
if (nums == null || nums.length == 0) return 0;
long sum = 0;
int maxVal = Integer.MIN_VALUE;
for (int num : nums) {
sum += num;
if (num > maxVal) {
maxVal = num;
}
}
return sum - maxVal;
}
}def solution(nums):
if not nums:
return 0
return sum(nums) - max(nums)function solution(nums) {
if (!nums || nums.length === 0) return 0;
let sum = 0;
let maxVal = -Infinity;
for (const num of nums) {
sum += num;
if (num > maxVal) maxVal = num;
}
return sum - maxVal;
}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.