Iterative Capacity Window — Problem Statement & Solution Guide

StringsMediumCharacter Frequency Map

TimeO(N)

SpaceO(1)

Problem Description

You are provided with an array nums of length N consisting of integers. The objective is to determine the sum of the two largest distinct values present in the array. If the array contains fewer than two distinct values, the result should be the single distinct value itself. The output must be a single integer representing this computed sum.

To solve this, you must identify the unique elements within the array, sort or filter them to find the top two maximums, and then perform the addition. Special care must be taken to handle cases where duplicates exist, ensuring that only distinct values are considered for the 'largest' and 'second largest' designations.

DSA Pattern Breakdown

"Iterative Capacity Window"

medium

WHY DOES IT MATTER?

Identifying top‑k distinct elements in linear time is a recurring pattern in performance‑critical code, such as leaderboard calculations, financial risk assessments, and real‑time analytics where sorting is too costly.

OPTIMIZATION CHALLENGE

The key insight is that you only need to remember the two best candidates at any moment; any other element cannot affect the final answer, allowing you to discard it immediately without extra storage.

REAL-WORLD CONNECTION

Think of a distributed cache that tracks the two most frequently accessed keys; instead of sorting all access counts, the system updates two counters on each request, mirroring the constant‑space max‑tracking technique.

During an interview, write the update logic as a small helper function or inline conditional block—clarity beats cleverness. Explicitly handle the "equal to current max" case to preserve distinctness.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(1)

Core Theory — Why This Approach?

The task reduces to finding the two maximum distinct elements in an unsorted integer array. A naive scan that records every element and then sorts the unique set incurs O(N log N) time, which becomes a bottleneck for very large N (e.g., N > 10^7) due to the overhead of sorting and extra memory for the distinct set. The optimal paradigm leverages a single linear pass while maintaining only the top two distinct values, achieving O(N) time and O(1) auxiliary space. This approach is rooted in the selection algorithm family, where we iteratively update candidate maxima based on comparisons, ensuring we never store more than constant state regardless of input size.

Interview Questions on This Problem

Q1How would you modify the algorithm to also return the indices of the two largest distinct values?

Maintain two pairs (value, index) for the first and second maximums. When a new element exceeds the current max, shift the max to second and update max; if it falls between max and second and is distinct, update second accordingly.

Q2What changes are needed if the array can contain NaN or non‑numeric sentinel values that should be ignored?

Add a validation step inside the loop to skip any element that is not a finite number (e.g., using Number.isFinite in JavaScript or isnan in C++). The rest of the logic remains unchanged, as only valid numbers participate in max updates.

Q3Explain how you would adapt the solution for a streaming scenario where the array elements arrive one by one and you must output the current sum after each insertion.

Keep the same two‑value state across the stream. For each incoming element, apply the same comparison logic to possibly update the top two distinct values, then emit the sum (or single value if only one distinct exists). This yields O(1) amortized update time per element.

Examples

Example 1

Input

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Output

Explanation: The distinct values in the array are {1, 2, 3, 4, 5, 6, 9}. The largest distinct value is 9. The second largest distinct value is 6. The sum is 9 + 6 = 15.

Example 2

Input

nums = [7, 7, 7, 7]

Output

Explanation: The only distinct value in the array is 7. Since there are fewer than two distinct values, the answer is simply the single distinct value, which is 7.

Example 3

Input

nums = [-1, -2, -3, -1, -2]

Output

-3

Explanation: The distinct values are {-1, -2, -3}. The largest distinct value is -1. The second largest distinct value is -2. The sum is -1 + (-2) = -3.

Example 4

Input

nums = [100, 200, 100, 300, 200, 400]

Output

Explanation: The distinct values are {100, 200, 300, 400}. The largest distinct value is 400. The second largest distinct value is 300. The sum is 400 + 300 = 700.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
The array will always contain at least one element.

Optimal Approach & Strategy

Traverse once while maintaining the top two distinct values in constant space, updating them via simple comparisons.

Brute Force Approach

Sort the array, deduplicate, then take the last two elements; this costs O(N log N) time and O(N) extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N)

function solution(nums) {
       let max = -Infinity;
       let secondMax = -Infinity;
       let uniqueElements = new Set(nums);
       if (uniqueElements.size < 2) {
           return Math.max(...nums);
       }
       for (let num of nums) {
           if (num > max) {
               secondMax = max;
               max = num;
           } else if (num > secondMax && num !== max) {
               secondMax = num;
           }
       }
       return max + secondMax;
   }

class Solution {
   public:
       int solution(vector<int>& nums) {
           int max_val = INT_MIN;
           int second_max_val = INT_MIN;
           unordered_set<int> unique_elements;
           for (int num : nums) {
               unique_elements.insert(num);
           }
           if (unique_elements.size() < 2) {
               int max_val = INT_MIN;
               for (int num : nums) {
                   max_val = max(max_val, num);
               }
               return max_val;
           }
           for (int num : nums) {
               if (num > max_val) {
                   second_max_val = max_val;
                   max_val = num;
               } else if (num > second_max_val && num != max_val) {
                   second_max_val = num;
               }
           }
           return max_val + second_max_val;
       }
   };

class Solution {
       public int solution(int[] nums) {
           int max = Integer.MIN_VALUE;
           int secondMax = Integer.MIN_VALUE;
           java.util.Set<Integer> uniqueElements = new java.util.HashSet<>();
           for (int num : nums) {
               uniqueElements.add(num);
           }
           if (uniqueElements.size() < 2) {
               int maxVal = Integer.MIN_VALUE;
               for (int num : nums) {
                   maxVal = Math.max(maxVal, num);
               }
               return maxVal;
           }
           for (int num : nums) {
               if (num > max) {
                   secondMax = max;
                   max = num;
               } else if (num > secondMax && num != max) {
                   secondMax = num;
               }
           }
           return max + secondMax;
       }
   }

def solution(nums):
       max_val = float('-inf')
       second_max_val = float('-inf')
       unique_elements = set(nums)
       if len(unique_elements) < 2:
           return max(nums)
       for num in nums:
           if num > max_val:
               second_max_val = max_val
               max_val = num
           elif num > second_max_val and num != max_val:
               second_max_val = num
       return max_val + second_max_val

function solution(nums) {
       let max = -Infinity;
       let secondMax = -Infinity;
       let uniqueElements = new Set(nums);
       if (uniqueElements.size < 2) {
           return Math.max(...nums);
       }
       for (let num of nums) {
           if (num > max) {
               secondMax = max;
               max = num;
           } else if (num > secondMax && num !== max) {
               secondMax = num;
           }
       }
       return max + secondMax;
   }

Asked in Top Tech Interviews

AmazonZomato

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.

Iterative Capacity Window Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Iterative Capacity Window — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor