algoadvance

Leetcode 2815. Max Pair Sum in an Array

Problem Statement

Given an array of integers nums, find the maximum sum of any pair of integers in the array where the two integers are not adjacent to each other.

Example:

Input: nums = [3, 5, 2, 3, 7, 1] Output: 10 Explanation: The maximum pair sum is 3 + 7 = 10, which are not adjacent in the array.

Clarifying Questions

1. Array Constraints:
   • Is the array guaranteed to have at least two elements?
   • Are the integers in the array guaranteed to be positive? Any negative numbers?
2. Output Requirements:
   • Should we return the maximum sum as an integer?

Let’s proceed with the following assumptions until clarified:

• The array will have at least two elements.
• The integers could be negative based on general problem constraints.

Strategy

1. Initial Thoughts:
   • Directly checking non-adjacent pairs using brute force would involve checking every possible pair which is computationally expensive with O(n^2) time complexity.
2. Optimal Approach:
   • Sort the array. The two largest elements which are not adjacent will typically be found towards the end of the sorted array but ensuring they are non-adjacent will require careful selection.
   • Iterate through the sorted array from the end, finding the two largest numbers that are not adjacent in the original nums array.
3. Steps:
   1. Create a list of tuples containing each number and its original index.
   2. Sort the list based on the number values.
   3. Iterate through the sorted list from the highest value back, finding the two highest non-adjacent numbers.

Code

import java.util.*;

public class MaxPairSum {

    public static int maxPairSum(int[] nums) {
        List<int[]> numIdxList = new ArrayList<>();
        
        // Create list of (value, index) pairs
        for (int i = 0; i < nums.length; i++) {
            numIdxList.add(new int[]{nums[i], i});
        }
        
        // Sort the list based on the values in descending order
        numIdxList.sort((a, b) -> Integer.compare(b[0], a[0]));
        
        // Find two non-adjacent maximum values
        for (int i = 0; i < numIdxList.size(); i++) {
            for (int j = i + 1; j < numIdxList.size(); j++) {
                int[] first = numIdxList.get(i);
                int[] second = numIdxList.get(j);
                if (Math.abs(first[1] - second[1]) > 1) {
                    return first[0] + second[0];
                }
            }
        }
        
        // It should always be possible to find two non-adjacent values in a valid input array
        return -1; // Indicate error in unexpected cases, but we assume input validity
    }

    public static void main(String[] args) {
        int[] nums = {3, 5, 2, 3, 7, 1};
        System.out.println(maxPairSum(nums)); // Output: 10
    }
}

Time Complexity

• Sorting: O(n log n), where n is the length of the input array.
• Pair Search: Worst-case O(n^2) in the nested loop to find non-adjacent pairs.
  • However, since the search begins from the largest elements, it often terminates early, potentially improving practical performance.

Conclusion

This solution should work efficiently for moderately large arrays. Further optimization, if needed, can potentially be done by exploring advanced data structures or algorithmic tweaks based on specific array properties provided in the problem statement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?