Calculated Range Extent — Problem Statement & Solution Guide
Problem Description
You are provided with a sequence of integer values representing a set of measurements. Your task is to determine the sum of the first two distinct values encountered in the sequence. A pair of values is considered distinct if they are not numerically equal. If the sequence contains fewer than two elements, or if no two distinct elements exist within the sequence, the result should be 0.
Formally, given an array nums of length n, find the indices i and j such that i < j, nums[i] != nums[j], and i is the smallest possible index satisfying these conditions. Return nums[i] + nums[j]. If no such pair exists, return 0.
This problem requires a linear scan to identify the first occurrence of a value different from the first element, or more generally, the first two elements in the sequence that differ from each other.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Calculated Range Extent"
WHY DOES IT MATTER?
The greedy scan guarantees linear time and constant space, which is critical for large datasets and streaming scenarios. It avoids the overhead of sorting or hash tables, making it the most efficient pattern for "first two distinct" problems.
OPTIMIZATION CHALLENGE
The core insight is that you only need to remember two values, not all distinct elements. By updating the second distinct value only when a new distinct number appears, you eliminate the need for auxiliary data structures and early exit once the answer is found.
REAL-WORLD CONNECTION
Consider a real-time sensor network where each node sends measurements. You need to quickly determine the first two different readings to trigger an alert. A greedy scan processes each packet as it arrives, using minimal memory and providing instant results.
In an interview, emphasize the early exit and constant space. Show that you can handle edge cases (all equal, single element) by initializing the variables to a sentinel value and checking after the loop.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to finding the first two distinct elements in a single left-to-right scan of the array. A naive approach would sort the array or use nested loops to compare every pair, leading to O(n log n) or O(n^2) time and potentially O(n) extra space for sorting or auxiliary data structures. The optimal greedy strategy maintains two variables: the first distinct value seen and the second distinct value. As we iterate, we update these variables only when we encounter a value different from the current first. Once both are set, we can immediately compute the sum and terminate, guaranteeing O(n) time and O(1) space.
This pattern is a classic example of the "first two distinct" greedy scan. It works because the problem only cares about the order of appearance, not the magnitude or frequency of values. By preserving the earliest distinct values, we avoid any need for sorting or counting, which would otherwise inflate complexity. The key insight is that once the second distinct value is found, no later element can change the answer, so we can stop early.
In large inputs, the linear scan is essential: it processes each element once, uses constant memory, and can handle streams or very long arrays that would not fit into memory if sorted. The greedy approach also naturally extends to streaming data, where you cannot store the entire sequence, making it highly scalable.
Interview Questions on This Problem
Q1How would you modify the algorithm if the input were a stream of numbers that could be infinite, and you needed to output the sum as soon as the second distinct number appears?
You would still use the same two-variable greedy scan, but you would process each incoming number one at a time, updating the first and second distinct values as they appear. Once the second distinct value is set, you immediately output the sum and can discard the rest of the stream, ensuring constant memory usage.
Q2A fintech company asks: if the array contains negative numbers, does the algorithm change?
No, the algorithm remains identical. The comparison logic only checks for inequality, not magnitude, so negative values are treated the same as positives. The sum will correctly reflect the first two distinct values regardless of sign.
Q3During a coding interview, a candidate mistakenly uses a set to track seen values and then picks the first two from the set. Why is this approach suboptimal?
Using a set loses the original order of appearance, so you might pick two distinct values that did not appear as the first two in the sequence. The problem explicitly requires the first two distinct values in order, so a set-based approach can produce an incorrect result and also incurs O(n) extra space and potentially O(n log n) time for insertion.
Examples
Input
nums = [4, 4, 7, 2, 9]
Output
11
Explanation: The first element is 4. The second element is 4, which is equal to the first, so we continue. The third element is 7, which is different from 4. Thus, the first two distinct elements are 4 and 7. Their sum is 4 + 7 = 11.
Input
nums = [5, 5, 5, 5]
Output
0
Explanation: All elements in the array are identical (5). There are no two distinct elements in the sequence. Therefore, the result is 0.
Input
nums = [10, 20, 30, 40]
Output
30
Explanation: The first element is 10. The second element is 20, which is different from 10. These are the first two distinct elements encountered. Their sum is 10 + 20 = 30.
Input
nums = [7]
Output
0
Explanation: The array contains only one element. Since there are not enough elements to form a pair of two distinct values, the result is 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Traverse the array once, maintaining two variables for the first and second distinct values. Update them as you encounter new distinct numbers and return the sum immediately once both are set, achieving O(n) time and O(1) space.
Brute Force Approach
A naive solution would sort the array and then pick the first two distinct elements, or use nested loops to compare each pair until two distinct values are found. Both approaches require extra time or space and are unnecessary for this problem.
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number}
*/
var calculatedRangeExtent = function(nums) {
if (nums.length < 2) return 0;
let first = nums[0];
let second = -1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== first) {
second = nums[i];
break;
}
}
if (second === -1) return 0;
return first + second;
};class Solution {
public:
int calculatedRangeExtent(vector<int>& nums) {
if (nums.size() < 2) return 0;
int first = nums[0];
int second = -1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] != first) {
second = nums[i];
break;
}
}
if (second == -1) return 0;
return first + second;
}
};class Solution {
public int calculatedRangeExtent(int[] nums) {
if (nums.length < 2) return 0;
int first = nums[0];
int second = -1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != first) {
second = nums[i];
break;
}
}
if (second == -1) return 0;
return first + second;
}
}class Solution:
def calculatedRangeExtent(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
first = nums[0]
second = -1
for i in range(1, len(nums)):
if nums[i] != first:
second = nums[i]
break
if second == -1:
return 0
return first + second/**
* @param {number[]} nums
* @return {number}
*/
var calculatedRangeExtent = function(nums) {
if (nums.length < 2) return 0;
let first = nums[0];
let second = -1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== first) {
second = nums[i];
break;
}
}
if (second === -1) return 0;
return first + second;
};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.