Maximum Valid Pair Sum solution and explanation
7 more videos on this problem
Maximum Valid Pair Sum | Leetcode 3979 | 3 Approaches | Biweekly Contest 186 | Dry RunVijay Algorithms · 25:54 · 178 views
3979. Maximum Valid Pair Sum (Leetcode Medium)Programming Live with Larry · 8:09 · 160 views
maximum valid pair sum - (optimal solution) | leetcode biweeklyVEDANT 999 · 5:41 · 157 views
LeetCode 3979: Maximum Valid Pair Sum | C++ (Brute Force to Optimal)AeXel · 17:18 · 103 views
Maximum Valid Pair SumOwen Wu · 5:24 · 93 views
Biweekly Contest 186| Leetcode 3979 | Maximum Valid Pair SumCode Like Him · 2:16 · 64 views
LeetCode 3979 Explained | Prefix Max + Suffix Max Trick | O(n) Java SolutionCodeVia · 3:34 · 15 views
LeetCode 3979. Maximum Valid Pair Sum | Biweekly Contest 186yoBro · 0:16 · 6 views
The problem
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 < nj - 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 isnums[0] + nums[2] = 5 + 9 = 14. - Thus, the answer is 14.
Constraints:
2 <= n == nums.length <= 1051 <= nums[i] <= 1091 <= 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.
class Solution:
def maxValidPairSum(self, nums: list[int], k: int) -> int:
ans = x = 0
for j in range(k, len(nums)):
y = nums[j]
x = max(x, nums[j - k])
ans = max(ans, x + y)
return ansclass Solution {
public int maxValidPairSum(int[] nums, int k) {
int ans = 0;
int x = 0;
for (int j = k; j < nums.length; ++j) {
int y = nums[j];
x = Math.max(x, nums[j - k]);
ans = Math.max(ans, x + y);
}
return ans;
}
}class Solution {
public:
int maxValidPairSum(vector<int>& nums, int k) {
int ans = 0;
int x = 0;
for (int j = k; j < nums.size(); ++j) {
int y = nums[j];
x = max(x, nums[j - k]);
ans = max(ans, x + y);
}
return ans;
}
};function maxValidPairSum(nums: number[], k: number): number {
let [ans, x] = [0, 0];
for (let j = k; j < nums.length; ++j) {
const y = nums[j];
x = Math.max(x, nums[j - k]);
ans = Math.max(ans, x + y);
}
return ans;
}func maxValidPairSum(nums []int, k int) int {
var ans, x int
for j := k; j < len(nums); j++ {
y := nums[j]
x = max(x, nums[j-k])
ans = max(ans, x+y)
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Small inputs or validating correctness |
| Hash Map Grouping | O(n) | O(n) | General optimal solution for unsorted arrays |
| Sorting with Greedy Comparison | O(n log n) | O(1) to O(n) | When ordering simplifies pair selection |
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.