Skip to main content
Talentd

Maximum Valid Pair Sum - Solution & Explanation

MediumArrayEnumeration6 min read
Practice this problem

Problem Statement

You are given an integer array nums of length n and an integer k.

A pair of indices (i, j) is called valid if:

  • 0 <= i < j < n
  • j - i >= k

Return the maximum value of nums[i] + nums[j] among all valid pairs.

 

Example 1:

Input: nums = [1,3,5,2,8], k = 2

Output: 13

Explanation:

The valid pairs are:

  • (0, 2): nums[0] + nums[2] = 6
  • (0, 3): nums[0] + nums[3] = 3
  • (0, 4): nums[0] + nums[4] = 9
  • (1, 3): nums[1] + nums[3] = 5
  • (1, 4): nums[1] + nums[4] = 11
  • (2, 4): nums[2] + nums[4] = 13

Thus, the answer is 13.ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Example 2:

Input: nums = [5,1,9], k = 1

Output: 14

Explanation:

  • Since k = 1, every pair is valid.
  • The maximum value is obtained from a pair (0, 2)ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹, which is nums[0] + nums[2] = 5 + 9 = 14.
  • Thus, the answer is 14.

 

Constraints:

  • 2 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= n - 1

Approach Overview

Problem Overview: You need to find the maximum possible sum formed by a pair of numbers that satisfies the validity condition defined in the problem. The challenge is not just checking every pair, but reducing unnecessary comparisons while still tracking the largest valid sum.

Approach 1: Brute Force Pair Checking (Time: O(nĀ²), Space: O(1))

The direct solution iterates through every possible pair using two nested loops. For each pair, evaluate the validity rule and update the answer if the pair sum is larger than the current maximum. This approach is easy to implement and useful for verifying correctness during interviews. Its main drawback is scalability because checking all pairs becomes expensive for large inputs.

Approach 2: Hash Map Grouping (Time: O(n), Space: O(n))

The optimized solution groups values based on the property used to define a valid pair. A hash map stores the best candidate seen for each group while iterating through the array once. When you encounter a new value, you perform constant-time hash lookups to determine whether it can form a better valid pair. This avoids repeated pair comparisons and reduces the runtime from quadratic to linear.

Approach 3: Sorting with Greedy Comparison (Time: O(n log n), Space: O(n) or O(1))

If the validity condition depends on ordering or shared characteristics, sorting can simplify pair construction. After sorting, you iterate through adjacent or grouped elements and compute candidate sums efficiently. This approach is useful when you want cleaner logic or when the pair rule naturally aligns with sorted traversal. Many interview solutions combine sorting with greedy checks for readability.

Recommended for interviews: Start with the brute force approach to show you understand the pair validation logic. Then move to the hash map optimization because interviewers usually expect you to eliminate redundant comparisons and achieve near-linear performance. Problems like this commonly test pattern recognition around arrays, grouping, and constant-time lookups.

Solution

For a valid pair (i, j), we require j - i geq k, i.e., i leq j - k. We enumerate the right endpoint j starting from k. For each j, the maximum left endpoint is j - k. We maintain the maximum value x of nums[i] in the range [0, j - k], and update the answer with x + nums[j].

The time complexity is O(n), and the space complexity is O(1), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckingO(nĀ²)O(1)Small inputs or validating correctness
Hash Map GroupingO(n)O(n)General optimal solution for unsorted arrays
Sorting with Greedy ComparisonO(n log n)O(1) to O(n)When ordering simplifies pair selection

Video Solution

Maximum Valid Pair Sum | Leetcode 3979 | 3 Approaches | Biweekly Contest 186 | Dry Run ā€¢ Vijay Algorithms ā€¢ 178 views views

Watch 7 more video solutions ā†’

Frequently Asked Questions

Is Maximum Valid Pair Sum easy or hard?
Maximum Valid Pair Sum is generally considered a medium-level problem because the brute force logic is simple, but identifying the optimal grouping or lookup strategy requires stronger pattern recognition.
Maximum Valid Pair Sum Python/Java solution
Python solutions usually rely on dictionaries for grouping and fast lookups, while Java implementations commonly use HashMap. Both languages can implement the optimal approach in O(n) time.
How to solve Maximum Valid Pair Sum in O(n)?
Use a hash map to track the best candidate for each grouping condition while iterating through the array once. For every new value, perform constant-time lookups and update the maximum valid pair sum immediately.
What is the best approach for Maximum Valid Pair Sum?
The best approach is usually a hash map based solution that groups numbers by the property required for a valid pair. This reduces repeated comparisons and achieves O(n) time complexity with O(n) extra space.
Is Maximum Valid Pair Sum asked at Google/Amazon/Meta?
Pair-based array problems with hash map optimization patterns frequently appear in interviews at Google, Amazon, and Meta. Interviewers use them to evaluate problem decomposition, data structure selection, and time complexity optimization.
What data structure is used in Maximum Valid Pair Sum?
The most common data structure is a hash map because it supports constant-time insertion and lookup. Some solutions also use arrays, sorting, or greedy traversal depending on the pair validation rule.
What is the time complexity of Maximum Valid Pair Sum?
The brute force solution runs in O(nĀ²) because it checks every possible pair. The optimized hash map approach typically runs in O(n) time with O(n) auxiliary space.

Ready to solve this problem?

Practice Maximum Valid Pair Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays