Maximum Valid Pair Sum | Leetcode 3979 | 3 Approaches | Biweekly Contest 186 | Dry Run
Maximum Valid Pair Sum - Video Solution
Watch 8 video solutions for Maximum Valid Pair Sum, a medium level problem involving Array, Enumeration. This walkthrough by Vijay Algorithms has 178 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 < 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.
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 |