Max Sum of a Pair With Equal Sum of Digits solution and explanation
Google
9 more videos on this problem
Max Sum of a Pair With Equal Sum of Digits | 4 Approaches | Leetcode 2342 | codestorywithMIKcodestorywithMIK · 25:31 · 7K views
Max Sum of a Pair With Equal Sum of Digits | Leetcode 2342Techdose · 14:25 · 5K views
LeetCode 2342 Solution: Max Sum of a Pair With Equal Sum of DigitsEngineering Digest · 8:30 · 2K views
2342. Max Sum of a Pair With Equal Sum of Digits | leetcode daily challenge | shashcode | java | dsaShashCode · 16:23 · 1K views
Leetcode 2342 Max Sum of a Pair With Equal Sum of Digits | 2 ApproachesCoding Decoded · 10:17 · 1K views
2342. Max Sum of a Pair With Equal Sum of Digits | HashMap | 3 ApproachesAryan Mittal · 18:28 · 1K views
2342. Max Sum of a Pair With Equal Sum of Digits (Leetcode Medium)Programming Live with Larry · 4:30 · 595 views
Daily Leetcode #1779: Feb 12, 2025 - 2342. Max Sum of a Pair With Equal Sum of DigitsProgramming Live with Larry · 7:13 · 588 views
2342. Max Sum of a Pair With Equal Sum of Digits | Leetcode Daily ChallengeEthos Typos · 11:18 · 469 views
Leetcode 2342. Max Sum of a Pair With Equal Sum of DigitsElite Code · 14:39 · 307 views
The problem
You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].
Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions.
Example 1:
Input: nums = [18,43,36,13,7] Output: 54 Explanation: The pairs (i, j) that satisfy the conditions are: - (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54. - (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50. So the maximum sum that we can obtain is 54.
Example 2:
Input: nums = [10,12,19,14] Output: -1 Explanation: There are no two numbers that satisfy the conditions, so we return -1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an array of integers. Two numbers can form a valid pair only if the sum of their digits is the same. Among all such pairs, return the maximum possible value of nums[i] + nums[j]. If no pair shares the same digit sum, return -1.
Approach 1: Hash Map Grouping (O(n) time, O(n) space)
Compute the digit sum for every number and group numbers that share the same value. A hash table maps digitSum → list or best values. While iterating through the array, calculate the digit sum in O(d) where d is the number of digits. For each group, track the two largest numbers. If a group contains at least two elements, compute their sum and update the global maximum.
This approach works because only numbers with identical digit sums can form valid pairs. Instead of checking every pair, the hash map restricts comparisons to numbers within the same group. The total work is linear with respect to the array size. Time complexity is O(n), and space complexity is O(n) for storing grouped values.
Approach 2: Optimized Direct Pair Processing (O(n) time, O(1)–O(n) space)
The optimized approach avoids storing full groups. Maintain a hash map where each key is a digit sum and the value is the largest number seen so far with that digit sum. Iterate once through the array. For each number, compute its digit sum and check the map.
If the digit sum already exists, you immediately have a candidate pair: the current number plus the stored maximum. Update the answer if this pair is larger. Then update the stored value with max(existing, current). This ensures the map always keeps the best candidate for future pairs.
This technique turns grouping into a streaming process. Each element performs constant-time hash lookup and update. The overall time complexity remains O(n) and the space complexity is O(k), where k is the number of unique digit sums (at most ~82 for 32‑bit integers).
Alternative Idea: Sorting Within Groups (O(n log n) time, O(n) space)
You can also group numbers by digit sum, then sort each group and take the top two values. Sorting increases the time complexity to O(n log n), making it slower than the hash-based approach. It is still useful conceptually when exploring grouping strategies with sorting or when extending the problem to more complex ranking logic.
Recommended for interviews: The optimized direct processing method is the expected solution. It demonstrates efficient use of a hash table and avoids unnecessary storage. Showing the grouping idea first proves you understand the constraint (equal digit sums), but the single-pass optimization shows strong problem-solving instincts and attention to time complexity.
Approach 1: Approach 1: Hash Map Grouping
This approach involves using a hash map to collect numbers with the same digit sum as keys and their corresponding numbers as values. Then, for each group (that has more than one number), calculate the maximal possible sum of any two numbers in that group.
def maxSum(nums):
def digit_sum(n):
return sum(int(d) for d in str(n))
digit_map = {}
for x in nums:
s = digit_sum(x)
if s in digit_map:
digit_map[s].append(x)
else:
digit_map[s] = [x]
max_sum = -1
for lst in digit_map.values():
if len(lst) > 1:
lst.sort(reverse=True)
max_sum = max(max_sum, lst[0] + lst[1])
return max_sumimport java.util.*;
public class Solution {
public int maxSum(int[] nums) {
Map<Integer, PriorityQueue<Integer>> digitMap = new HashMap<>();
for (int num : nums) {
int sum = digit_sum(num);
digitMap.putIfAbsent(sum, new PriorityQueue<>(Collections.reverseOrder()));
digitMap.get(sum).offer(num);
}
int maxSum = -1;
for (PriorityQueue<Integer> pq : digitMap.values()) {
if (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
maxSum = Math.max(maxSum, a + b);
}
}
return maxSum;
}
private int digit_sum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int maxSum(vector<int>& nums) {
unordered_map<int, vector<int>> digitMap;
for (int num : nums) {
int sum = digitSum(num);
digitMap[sum].push_back(num);
}
int maxSum = -1;
for (auto& entry : digitMap) {
if (entry.second.size() > 1) {
sort(entry.second.begin(), entry.second.end(), greater<int>());
maxSum = max(maxSum, entry.second[0] + entry.second[1]);
}
}
return maxSum;
}function digitSum(num) {
return num.toString().split('').reduce((sum, digit) => sum + parseInt(digit, 10), 0);
}
function maxSum(nums) {
const digitMap = {};
for (const num of nums) {
const sum = digitSum(num);
if (!digitMap[sum]) {
digitMap[sum] = [];
}
digitMap[sum].push(num);
}
let maxSum = -1;
for (const list of Object.values(digitMap)) {
if (list.length > 1) {
list.sort((a, b) => b - a);
maxSum = Math.max(maxSum, list[0] + list[1]);
}
}
return maxSum;
}using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public int MaxSum(int[] nums) {
var digitMap = new Dictionary<int, List<int>>();
foreach (var num in nums) {
int sum = digitSum(num);
if (!digitMap.ContainsKey(sum)) {
digitMap[sum] = new List<int>();
}
digitMap[sum].Add(num);
}
int maxSum = -1;
foreach (var list in digitMap.Values) {
if (list.Count > 1) {
list.Sort((a, b) => b - a);
maxSum = Math.Max(maxSum, list[0] + list[1]);
}
}
return maxSum;
}
private int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}This Python function calculates the digit sum of each number and stores numbers in a dictionary keyed by their digit sum. It then checks if each key has multiple numbers, sorts them, and picks the largest two to calculate their sum.
Time Complexity: O(n log k), where n is the number of elements and k is the average length of the list stored in the hash map.
Space Complexity: O(n) for the hash map.
Approach 2: Approach 2: Optimized Direct Pair Processing
In this approach, instead of sorting within each digit group, use a max heap (priority queue) to track the two largest numbers efficiently. Maintain the largest two numbers seen on-the-fly for each digit sum group.
import heapq
def maxSum(nums):
def digit_sum(n):
return sum(int(d) for d in str(n))
max_dict = {}
for x in nums:
s = digit_sum(x)
if s in max_dict:
if len(max_dict[s]) < 2:
heapq.heappush(max_dict[s], x)
else:
heapq.heappushpop(max_dict[s], x)
else:
max_dict[s] = [x]
max_sum = -1
for lst in max_dict.values():
if len(lst) > 1:
max_sum = max(max_sum, sum(heapq.nlargest(2, lst)))
return max_sumimport java.util.*;
public class Solution {
public int maxSum(int[] nums) {
Map<Integer, PriorityQueue<Integer>> digitMap = new HashMap<>();
for (int num : nums) {
int sum = digitSum(num);
digitMap.putIfAbsent(sum, new PriorityQueue<>());
PriorityQueue<Integer> heap = digitMap.get(sum);
heap.offer(num);
if (heap.size() > 2) {
heap.poll();
}
}
int maxSum = -1;
for (PriorityQueue<Integer> pq : digitMap.values()) {
if (pq.size() == 2) {
int n1 = pq.poll();
int n2 = pq.poll();
maxSum = Math.max(maxSum, n1 + n2);
}
}
return maxSum;
}
private int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int maxSum(vector<int>& nums) {
unordered_map<int, vector<int>> digitMap;
for (int num : nums) {
int sum = digitSum(num);
auto& pq = digitMap[sum];
pq.push_back(num);
push_heap(pq.begin(), pq.end(), greater<int>());
if (pq.size() > 2) {
pop_heap(pq.begin(), pq.end(), greater<int>());
pq.pop_back();
}
}
int maxSum = -1;
for (auto& entry : digitMap) {
if (entry.second.size() == 2) {
maxSum = max(maxSum, entry.second[0] + entry.second[1]);
}
}
return maxSum;
}function digitSum(num) {
return num.toString().split('').reduce((sum, digit) => sum + parseInt(digit, 10), 0);
}
function maxSum(nums) {
const digitMap = {};
for (const num of nums) {
const sum = digitSum(num);
if (!digitMap[sum]) {
digitMap[sum] = [];
}
const heap = digitMap[sum];
heap.push(num);
heap.sort((a, b) => a - b);
if (heap.length > 2) heap.shift();
}
let maxSum = -1;
for (const list of Object.values(digitMap)) {
if (list.length == 2) {
maxSum = Math.max(maxSum, list[0] + list[1]);
}
}
return maxSum;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxSum(int[] nums) {
var digitMap = new Dictionary<int, List<int>>();
foreach (var num in nums) {
int sum = digitSum(num);
if (!digitMap.ContainsKey(sum)) {
digitMap[sum] = new List<int>();
}
var heap = digitMap[sum];
heap.Add(num);
heap.Sort();
if (heap.Count > 2) {
heap.RemoveAt(0);
}
}
int maxSum = -1;
foreach (var list in digitMap.Values) {
if (list.Count == 2) {
maxSum = Math.Max(maxSum, list[0] + list[1]);
}
}
return maxSum;
}
private int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}This Python solution uses a heap to keep track of the top two numbers in each digit group efficiently. Heap operations ensure that the complexity remains lower than sorting.
Time Complexity: O(n log k), where k is typically small, so it's closer to O(n). Space Complexity: O(n) for the hash map.
Approach 3: Hash Table
We can use a hash table d to record the maximum value corresponding to each digit sum, and initialize an answer variable ans = -1.
Next, we traverse the array nums. For each number v, we calculate its digit sum x. If x exists in the hash table d, then we update the answer ans = max(ans, d[x] + v). Then update the hash table d[x] = max(d[x], v).
Finally, return the answer ans.
Since the maximum element in nums is 10^9, the maximum digit sum is 9 times 9 = 81. We can directly define an array d of length 100 to replace the hash table.
The time complexity is O(n times log M), and the space complexity is O(D). Here, n is the length of the array nums, and M and D are the maximum value of the elements in the array nums and the maximum value of the digit sum, respectively. In this problem, M leq 10^9, D leq 81.
function maximumSum(nums: number[]): number {
const d: number[] = Array(100).fill(0);
let ans = -1;
for (const v of nums) {
let x = 0;
for (let y = v; y; y = (y / 10) | 0) {
x += y % 10;
}
if (d[x]) {
ans = Math.max(ans, d[x] + v);
}
d[x] = Math.max(d[x], v);
}
return ans;
}func maximumSum(nums []int) int {
d := [100]int{}
ans := -1
for _, v := range nums {
x := 0
for y := v; y > 0; y /= 10 {
x += y % 10
}
if d[x] > 0 {
ans = max(ans, d[x]+v)
}
d[x] = max(d[x], v)
}
return ans
}impl Solution {
pub fn maximum_sum(nums: Vec<i32>) -> i32 {
let mut d = vec![0; 100];
let mut ans = -1;
for &v in nums.iter() {
let mut x: usize = 0;
let mut y = v;
while y > 0 {
x += (y % 10) as usize;
y /= 10;
}
if d[x] > 0 {
ans = ans.max(d[x] + v);
}
d[x] = d[x].max(v);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map Grouping | Time Complexity: O(n log k), where n is the number of elements and k is the average length of the list stored in the hash map. |
| Approach 2: Optimized Direct Pair Processing | Time Complexity: O(n log k), where k is typically small, so it's closer to O(n). Space Complexity: O(n) for the hash map. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Grouping | O(n) | O(n) | Clear grouping logic when exploring pairs with the same digit sum |
| Optimized Direct Pair Processing | O(n) | O(k) | Best general solution; single pass with constant-time hash lookups |
| Sort Numbers Within Groups | O(n log n) | O(n) | Useful when additional ranking or ordering inside groups is required |
Frequently asked questions
Is Max Sum of a Pair With Equal Sum of Digits easy or hard?
The problem is rated Medium because the key insight is recognizing that numbers should be grouped by digit sum. Once that observation is made, a hash map enables an efficient O(n) solution. The challenge lies in designing the grouping logic and avoiding unnecessary pair comparisons.
Max Sum of a Pair With Equal Sum of Digits Python/Java solution
Both Python and Java implementations follow the same logic: compute the digit sum of each number, use a hash map to store the largest value per digit sum, and update the maximum pair sum whenever another number with the same sum appears. The algorithm runs in O(n) time and works identically across Python, Java, C++, JavaScript, and C#.
How to solve Max Sum of a Pair With Equal Sum of Digits in O(n)?
Iterate through the array and compute the digit sum for each number. Use a hash map that maps digitSum → largest number seen with that sum. If the digit sum already exists in the map, calculate a candidate pair sum using the stored value and update the maximum result. Then update the map with the larger value between the stored number and the current number.
What is the best approach for Max Sum of a Pair With Equal Sum of Digits?
The best approach uses a hash map that stores the largest number seen for each digit sum. While iterating through the array, compute the digit sum and check if another number with the same sum already exists. This allows you to update the maximum pair sum in constant time. The overall time complexity is O(n) with O(k) extra space where k is the number of distinct digit sums.
Is Max Sum of a Pair With Equal Sum of Digits asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving hash tables and grouping by computed keys such as digit sums. Similar problems appear in coding interviews at companies like Amazon, Google, and Meta where candidates must efficiently group values and track optimal pairs in linear time.
What data structure is used in Max Sum of a Pair With Equal Sum of Digits?
A hash table (hash map) is the primary data structure. It maps each digit sum to the largest number encountered so far with that sum. This structure allows constant-time lookups and updates, enabling a single-pass O(n) algorithm.
What is the time complexity of Max Sum of a Pair With Equal Sum of Digits?
The optimal solution runs in O(n) time. Each number is processed once, its digit sum is computed, and a hash map lookup determines whether a matching partner already exists. Space complexity is O(k), where k represents the number of unique digit sums stored in the map.