2815. Max Pair Sum in an Array

EasyArrayHash Table
Leetcode Link

Problem Description

In this problem, we are provided with an array of integers called nums, which is indexed starting from 0. Our task is to find the maximum sum obtainable by selecting two different numbers from this array where the largest digit present in both numbers is exactly the same.

For instance, if the array contains the numbers 34 and 42, we can't pair them to form a sum because their maximum digits (4 in 34 and 4 in 42) are not equal. However, if we had the numbers 34 and 43, their sum is a valid candidate because the maximum digit 4 is present in both numbers.

If it is possible to find at least one pair of numbers with this property, we should return the sum of that pair which is the largest among all such valid pairs. If no such pair exists, we need to return -1.

To summarize, the goal is to maximize the sum of a number pair, under the constraint that the pair's maximum digits are equal.

Intuition

The process of arriving at the solution involves enumerating all possible pairs from the array to check two primary conditions:

  1. Whether the largest digit in both numbers of the pair is the same.
  2. Whether the sum of these numbers is greater than any sum we've previously recorded.

We start with an answer variable ans which is initialized to -1, assuming initially that there are no pairs satisfying the condition. We then iterate over each possible pair of numbers in the array, checking the conditions for every such pair.

For the first condition, we are required to identify the largest digit of each number. This is achieved by converting the integers to strings, and then using the max function which finds the maximum character in each string representation (which corresponds to the maximum digit in the number). If the maximum digits of both numbers in the pair match, we proceed to the second condition.

For the second condition, we simply calculate the sum of the two numbers and check if this sum is larger than our current recorded maximum sum (ans). If it is, we update ans with this new sum.

This brute-force approach ensures that by the end of the iteration, we have checked every possible pair and identified the maximum sum possible under the given constraint—if at least one such valid pair exists. If after checking all pairs no valid pair is found, ans remains -1, which is the value we return.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The implementation of this problem's solution uses a straightforward approach: a nested loop to enumerate all possible pairs from the array and check the conditions for each pair to identify the one with the highest sum.

Here's a step-by-step walkthrough of the algorithm, utilizing the reference solution approach:

  1. We start by initializing an answer variable ans with a value of -1. This variable will keep track of the maximum sum we find that satisfies the condition.

  2. We use a for-loop to iterate over each element of the array nums by its index i. This outer loop picks the first number of the pair.

  3. Inside the outer loop, we use a nested for-loop to iterate over the rest of the elements in the array starting from index i + 1. This inner loop picks the second number of the pair.

  4. We calculate the potential sum v of the two numbers nums[i] (from the outer loop) and nums[j] (from the inner loop).

  5. We convert both numbers nums[i] and nums[j] to strings using str() to be able to utilize the max() function and extract the highest digit in each number.

  6. We compare the maximum digit of both numbers using max(str(nums[i])) == max(str(nums[j])) to check if they are equal. If they are not equal, we continue to the next iteration without executing further code.

  7. If the maximum digits are equal, we then check if the sum of these two numbers v is greater than the current ans. If it is, we update ans with the new, larger sum v.

  8. After iterating over all possible pairs, the loop concludes, and the maximum sum ans is returned. If ans has not been updated, meaning no valid pairs have been found, the initial -1 value will be returned.

This algorithm leverages the brute-force paradigm by checking each possible pair in the array against the condition. Although it is a simple and direct method, its time complexity is O(n^2) due to the nested loops. This complexity arises because for each element in the array, we are iterating through all other elements that follow it to form pairs.

Despite its simplicity, this approach guarantees we do not miss any valid pairs and subsequently the maximum sum that meets the criteria of having the same largest digit.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let us consider a small example using the array nums = [51, 71, 17, 42]. We will illustrate the solution approach with this array.

  1. We initialize ans to -1 to handle the case where we do not find any valid pairs.

  2. We start with the first number (at index i=0), nums[0] = 51, and compare it with every other number in the array.

  3. Now, we move to the second number (at index i=1), nums[1] = 71, and compare it with numbers after it. The first comparison is with nums[2] = 17.

    • The maximum digit in 71 is 7 and in 17 is also 7.
    • Since both have the same maximum digit, we compute the sum 71 + 17 = 88.
    • We compare this sum 88 with ans which is currently -1.
    • Since 88 is greater than -1, we update ans to 88.

  4. We then compare nums[1] = 71 with the last number nums[3] = 42.

    • The maximum digit in 71 is 7, whereas in 42 it is 4.
    • Since the digits are not the same, we do not update ans.

  5. Next, we move to the third number nums[2] = 17, and compare it with the only number after it, nums[3] = 42.

    • The maximum digit in both 17 and 42 is not the same (7 vs 4), so we do not update ans.

  6. Now, there are no more pairs left to be compared.

  7. Having finished the loop, the largest sum we found from valid pairs is 88.

  8. We return ans, which is 88.

By the end of this process, we've examined all possible pairs and determined that the 71 and 17 pair provides the highest sum (88) among pairs with matching maximum digits. If no such pair existed, the function would return the default ans value of -1.

Solution Implementation

1class Solution:
2    def maxSum(self, nums: List[int]) -> int:
3        # Initialize the answer with -1, which will also be the return value if no valid pair is found
4        max_sum = -1
5      
6        # Enumerate gives both the index (i) and the number (current_val) from the list nums
7        for i, current_val in enumerate(nums):
8            # Loop through the remaining numbers (other_val) in the list starting from the index right after i
9            for other_val in nums[i + 1:]:
10                # Calculate the potential maximum sum of the current pair
11                pair_sum = current_val + other_val
12              
13                # Convert both numbers to strings and find the maximum digit in each
14                max_digit_current = max(str(current_val))
15                max_digit_other = max(str(other_val))
16              
17                # Update the max_sum if the current pair sum is greater than the previous max_sum
18                # and the maximum digits of both numbers are equal
19                if max_sum < pair_sum and max_digit_current == max_digit_other:
20                    max_sum = pair_sum
21      
22        # Return the maximum sum found, or -1 if no such pair exists
23        return max_sum
24
1class Solution {
2  
3    // Computes the maximum sum of pairs with equal highest digits
4    public int maxSum(int[] nums) {
5        int maxPairSum = -1; // Initialize maximum pair sum to -1 (indicating no pairs found yet)
6        int n = nums.length; // Extract the length of the nums array.
7      
8        // Iterate over the array using two pointers to find all possible pairs
9        for (int i = 0; i < n; ++i) {
10            for (int j = i + 1; j < n; ++j) {
11                int currentSum = nums[i] + nums[j]; // Calculate the sum of the current pair
12              
13                // Check if the current pair has the same highest digit and if the sum is greater than maxPairSum
14                if (maxPairSum < currentSum && getHighestDigit(nums[i]) == getHighestDigit(nums[j])) {
15                    maxPairSum = currentSum; // Update the maximum pair sum if conditions are met
16                }
17            }
18        }
19      
20        return maxPairSum; // Return the computed maximum pair sum
21    }
22
23    // Helper function to determine the highest digit in an integer
24    private int getHighestDigit(int x) {
25        int highestDigit = 0; // Initialize highest digit to 0
26      
27        // Iterate over the digits of x
28        while (x > 0) {
29            int digit = x % 10; // Get the last digit of x
30            highestDigit = Math.max(highestDigit, digit); // Update the highest digit found so far
31            x /= 10; // Remove the last digit from x
32        }
33      
34        return highestDigit; // Return the highest digit found
35    }
36}
37
1#include <vector> // Include necessary header for vector
2using std::vector; // Makes using vector easier without std:: prefix
3
4class Solution {
5public:
6    int maxSum(vector<int>& nums) {
7        int maxSum = -1; // Use maxSum to track the maximum sum found
8        int n = nums.size(); // Store the size of the input vector
9
10        // Lambda function f extracts the highest digit from a given integer
11        auto getHighestDigit = [](int x) {
12            int highestDigit = 0;
13            // Loop to find the highest digit
14            while (x > 0) {
15                highestDigit = std::max(highestDigit, x % 10);
16                x /= 10;
17            }
18            return highestDigit;
19        };
20
21        // Double loop to check each pair of numbers in the vector
22        for (int i = 0; i < n; ++i) {
23            for (int j = i + 1; j < n; ++j) {
24                // Sum of the current pair
25                int currentSum = nums[i] + nums[j];
26
27                // Check if the highest digits are equal and update maxSum if necessary
28                if (maxSum < currentSum && getHighestDigit(nums[i]) == getHighestDigit(nums[j])) {
29                    maxSum = currentSum;
30                }
31            }
32        }
33        return maxSum; // Return the maximum sum found
34    }
35};
36
1function maxSum(nums: number[]): number {
2    const length = nums.length; // Get the length of the input array
3    let maxPairSum = -1; // Initialize the maxPairSum with -1 as the lowest possible value
4    // Function to calculate the highest single digit in a number
5    const findMaxDigit = (number: number): number => {
6        let maxDigit = 0;
7        // Iterate through digits of the number to find the maximum digit
8        while (number > 0) {
9            maxDigit = Math.max(maxDigit, number % 10);
10            number = Math.floor(number / 10); // Move to the next digit
11        }
12        return maxDigit;
13    };
14
15    // Iterate over all unique index pairs (i, j) to find the highest sum
16    // with the condition that the max digit of both numbers is the same
17    for (let i = 0; i < length; ++i) {
18        for (let j = i + 1; j < length; ++j) {
19            const currentSum = nums[i] + nums[j]; // Calculate the sum of the current pair
20            // Check if the max digit of both numbers is the same
21            // and if the current sum is greater than the current maxPairSum
22            if (maxPairSum < currentSum && findMaxDigit(nums[i]) === findMaxDigit(nums[j])) {
23                maxPairSum = currentSum; // Update the maxPairSum with the current sum
24            }
25        }
26    }
27    // Return the highest sum found that satisfies the condition
28    return maxPairSum;
29}
30
Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by two nested loops and the operation to find the maximum digit in numbers within the loops. The two nested loops over the array nums with length n give us O(n^2) complexity since every element is compared with every other element in a brute force manner.

For each pair (x, y) selected by the nested loops, the code converts x and y to strings and finds the maximum digit in each. Since the number of digits in a number is proportional to the logarithm of the number (to be precise, it's O(log M) where M is the value of the number), finding the maximum digit is O(log M). M here represents the maximum value found within the array to account for the largest possible number of digits to check.

Combining the nested loops O(n^2) with the operation to find the maximum digit O(log M), the overall time complexity of the code is O(n^2 * log M).

Space Complexity

The space complexity is O(1). Aside from the input list nums, the only extra space used by the algorithm is a fixed number of single-value variables (like ans, x, y, v) that do not depend on the size of the input. The algorithm does not allocate any additional space that grows with the input size, hence it uses constant extra space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫