Iterative Stack Horizon — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Iterative Stack Horizon problem optimally.
O(n)O(1)Problem Description
You are given an integer array nums. Identify the two greatest distinct values present in the array and return their sum. If the array contains fewer than two distinct numbers, the result is undefined (the test data will always contain at least two different values). The solution must run in linear time relative to the size of nums and use only O(1) additional memory.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Iterative Stack Horizon"
WHY DOES IT MATTER?
Maintaining two running maxima in a single pass eliminates the need for sorting or auxiliary data structures, which is critical for large datasets where memory and time budgets are tight. This pattern is a classic example of a linear scan with constant state, a staple in interview questions that test understanding of space-time trade-offs.
OPTIMIZATION CHALLENGE
The key insight is that only the two largest distinct values matter; all other elements can be ignored after a single comparison. By updating two variables on the fly, we avoid sorting or hashing, thus reducing both time and space complexity.
REAL-WORLD CONNECTION
Consider a real-time monitoring system that tracks the top two highest CPU usage values across a fleet of servers. Instead of storing all usage samples, the system keeps only the current top two, updating them as new samples arrive, mirroring the algorithmic pattern here.
When explaining this in an interview, emphasize the invariant that after each iteration the two variables always hold the largest and second largest distinct values seen so far. This clarity helps the interviewer see why the algorithm is correct.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the sum of the two greatest distinct values in an integer array. A naive solution would sort the array or use a data structure like a set to collect unique values and then pick the top two, which would require O(n log n) time or O(n) extra space. The optimal linear-time, constant-space approach is to perform a single pass through the array while maintaining two variables: one for the maximum value seen so far and one for the second maximum distinct value. Whenever a new element is encountered, we compare it against these two variables, updating them appropriately while ensuring they remain distinct. This guarantees O(n) time and O(1) additional memory, meeting the strict constraints.
Interview Questions on This Problem
Q1How would you modify this algorithm if the array could contain negative numbers and you need the two smallest distinct values instead?
You would maintain two variables for the minimum and second minimum, updating them similarly to the maximum case but with reversed comparison logic. Ensure that the second minimum is distinct from the minimum by checking equality before assignment.
Q2In a distributed system where each node holds a segment of the array, how can you compute the global sum of the two largest distinct values efficiently?
Each node can locally compute its own top two distinct values in O(k) time for its segment. Then, a reduction step merges these local pairs by comparing the four candidates to produce the global top two, requiring only O(log p) communication rounds for p nodes.
Q3What would be the impact on time complexity if you were required to return the indices of the two largest distinct values instead of their sum?
The algorithm remains O(n) time; you simply store the indices alongside the values when updating the maximum and second maximum. The additional bookkeeping does not change the asymptotic complexity.
Examples
Input
[4, 7, 2, 9, 5]
Output
16
Explanation: The distinct values sorted descending are 9, 7, 5, 4, 2. The two largest are 9 and 7; their sum is 9 + 7 = 16.
Input
[-3, 12, 12, 8, -1, 0]
Output
20
Explanation: Distinct values are -3, -1, 0, 8, 12. The two greatest distinct numbers are 12 and 8, giving 12 + 8 = 20.
Input
[100, 45, 100, 23, 67]
Output
167
Explanation: After removing duplicates we have 100, 67, 45, 23. The top two distinct numbers are 100 and 67; their sum equals 167.
Constraints
- 1 <= nums.length <= 100000
- -10^9 <= nums[i] <= 10^9
- At least two distinct values exist in nums
- Solution must run in O(n) time and O(1) extra space
Optimal Approach & Strategy
Traverse the array once, maintaining two variables for the largest and second largest distinct values, updating them with simple comparisons. This yields O(n) time and O(1) space.
Brute Force Approach
Collect all unique numbers, sort them, and pick the last two. This takes O(n log n) time and O(n) space.
Code Solutions
function solution(nums) {
nums = [...new Set(nums)].sort((a, b) => b - a);
return nums[0] + nums[1];
}class Solution {
public:
int solution(vector<int>& nums) {
sort(nums.rbegin(), nums.rend());
int max1 = INT_MIN;
int max2 = INT_MIN;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2 && num != max1) {
max2 = num;
}
}
return max1 + max2;
}
};class Solution {
public int solution(int[] nums) {
Arrays.sort(nums);
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2 && num != max1) {
max2 = num;
}
}
return max1 + max2;
}
}def solution(nums):
nums = sorted(set(nums), reverse=True)
return nums[0] + nums[1]function solution(nums) {
nums = [...new Set(nums)].sort((a, b) => b - a);
return nums[0] + nums[1];
}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.