Leetcode 2815: Max Pair Sum in an Array
You are given an integer array
nums, and you need to find the maximum sum of any two distinct numbers in the array such that the largest digit in both numbers is the same.Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers `nums`.
Example: nums = [2536, 1613, 3366, 162]
Constraints:
• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104
Output: Return the maximum sum of two numbers from the array where the largest digit in both numbers is the same. If no such pair exists, return -1.
Example: 5902
Constraints:
• The answer will always be a valid integer.
Goal: The goal is to find the pair of numbers with the same largest digit and return their maximum sum.
Steps:
• 1. Identify the largest digit in each number.
• 2. Group numbers by their largest digits.
• 3. For each group, find the two largest numbers and return their sum.
• 4. If no group has at least two numbers, return -1.
Goal: You are given an array `nums` containing integers. The length of `nums` and the range of values in `nums` are constrained.
Steps:
• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104
Assumptions:
• The input array will always contain at least two integers.
• The numbers in the array are positive integers.
• Input: nums = [2536, 1613, 3366, 162]
• Explanation: All numbers in the list have 6 as their largest digit. The sum of the two largest numbers, 2536 and 3366, gives the maximum sum of 5902.
Approach: To solve this problem, we can iterate through the numbers, extract their largest digit, and group numbers by this digit. Then, we can find the two largest numbers in each group and compute the maximum sum.
Observations:
• We need to efficiently find the largest digit in each number.
• We need to group the numbers based on their largest digit.
• We can use a dictionary to store numbers grouped by their largest digit.
Steps:
• 1. Create an empty dictionary to store numbers grouped by their largest digit.
• 2. For each number, find its largest digit and add the number to the corresponding group in the dictionary.
• 3. For each group of numbers with the same largest digit, find the two largest numbers.
• 4. Return the maximum sum of any pair from any group, or return -1 if no valid pair is found.
Empty Inputs:
• Input should always have at least two numbers.
Large Inputs:
• The input size will not exceed 100 elements.
Special Values:
• If no two numbers share the same largest digit, return -1.
Constraints:
• The input size is manageable with respect to both time and space complexity.
int maxSum(vector<int>& nums) {
vector<vector<int>> ids(10);
for(int x: nums) {
int val = x;
int f = x % 10;
while(x > 0) {
f = max(f, x % 10);
x /= 10;
}
ids[f].push_back(val);
}
int ans = -1;
for(int i = 0; i < ids.size(); i++) {
sort(ids[i].begin(), ids[i].end());
int n = ids[i].size();
if(ids[i].size() >= 2) {
// cout << ids[i][n - 1] << " " << ids[i][n - 2] << " "<< ids[i][n - 1] + ids[i][n - 2] << "\n";
ans = max(ans, ids[i][n - 1] + ids[i][n - 2]);
}
}
return ans;
}
1 : Function Declaration
int maxSum(vector<int>& nums) {
Declares the function `maxSum`, which takes a vector of integers `nums` and returns an integer value.
2 : Vector Initialization
vector<vector<int>> ids(10);
Initializes a 2D vector `ids` of size 10 to store numbers categorized by their highest digit.
3 : For Loop Start
for(int x: nums) {
Starts a loop to iterate over each integer `x` in the input vector `nums`.
4 : Assign Value
int val = x;
Assigns the value of `x` to a new variable `val` to preserve the original number.
5 : Get Last Digit
int f = x % 10;
Extracts the last digit of `x` by taking the modulus with 10 and stores it in `f`.
6 : While Loop Start
while(x > 0) {
Begins a while loop to iterate through each digit of `x` to find the highest digit.
7 : Find Maximum Digit
f = max(f, x % 10);
Updates `f` to store the maximum digit encountered during the iteration.
8 : Remove Last Digit
x /= 10;
Reduces `x` by removing its last digit.
9 : Store Value in Bucket
ids[f].push_back(val);
Adds the value `val` to the bucket `ids[f]` corresponding to its highest digit `f`.
10 : Initialize Answer
int ans = -1;
Initializes the variable `ans` to -1 to store the maximum sum found.
11 : Bucket Processing Loop
for(int i = 0; i < ids.size(); i++) {
Starts a loop to process each bucket in `ids`.
12 : Sort Bucket
sort(ids[i].begin(), ids[i].end());
Sorts the numbers in bucket `ids[i]` in ascending order.
13 : Bucket Size Check
int n = ids[i].size();
Stores the size of bucket `ids[i]` in the variable `n`.
14 : Check for Two Numbers
if(ids[i].size() >= 2) {
Checks if there are at least two numbers in the bucket to calculate a sum.
15 : Calculate Maximum Sum
ans = max(ans, ids[i][n - 1] + ids[i][n - 2]);
Calculates the sum of the two largest numbers in the current bucket and updates `ans` if the sum is greater than the current value of `ans`.
16 : Return Result
return ans;
Returns the maximum sum found, stored in `ans`.
Best Case: O(n log n) where n is the length of the array.
Average Case: O(n log n).
Worst Case: O(n log n).
Description: The dominant factor is the sorting operation for each group of numbers.
Best Case: O(n) for storing the numbers in the dictionary.
Worst Case: O(n) for storing the numbers in the dictionary.
Description: The space complexity is proportional to the number of elements in the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus