Java :: ~O(N) but space optimised - explained - ttt
Idea\n\n - The idea is to store all the nums[i] having the same sum_of_digits in a hashmap\n - the hashmap can be structured as <Integer, int[]> to enhance spac
**Idea**\n```\n - The idea is to store all the nums[i] having the same sum_of_digits in a hashmap\n - the hashmap can be structured as <Integer, int[]> to enhance space complexity \n - for each (key, value) pair in the hashmap, value[] will store the largest and the second largest num that have a sum_of_digit as key\n\n```\n\n**Example**\n\n```\nEg: nums = [18,43,36, 4,13,7, 45, 9]\n\n- the nums 18, 36, 45 and 9 have a sum_of_digit = 9 \n\tso we will have a <key, val> entry in our hashmap as < 9, [ 45, 36] >\n\t note how we will be storing the first 2 largest nums in out array\n\t\n- the nums 43 and 7 add up to 7, so we make an entry as < 7, [43, 7] >\n\n- the num 6 will make an entry of <6, [6, -1]> \n   the -1 indicates that only 1 num has sum_of_digit = 6, hence cannot be considered\n  \n- the num 4 is stores as <4, [13, -1]>\n\nFinally the hashmap is ready as \n - < 9, [ 45, 36] >\n - < 7, [43, 7] >\n - <6, [6, -1]> \n - <4, [13, -1]>\n\nWe can now iterate over all entries and find the best res\nIn this case, res = 81 (for sum 9 -> 45 + 36 = 81)\n```\n\n*The space optimisation takes place while storing the two largest nums that have a sum of digit = key in stead of storing all nums and then sorting them to get the two largest.*\n\n**Java**\n```\nclass Solution {\n    \n    HashMap<Integer, int[]> map = new HashMap<>();\n    int res = -1;\n    // make sure to use res as a global var as we can\'t use local vars in lambda expressions \n    \n    public int maximumSum(int[] nums) {\n        initialise(nums);\n        \n        map.forEach((k, v) -> {\n            if(v[1] != -1){\n                res = Math.max(res, v[0] + v[1]);\n            }\n        });\n        return res;\n    }\n    \n    public void initialise(int[] nums){\n        for(int x: nums){  // O(N) operations\n            calculateDigitSum(x);\n        }\n    }\n    \n    public void calculateDigitSum(int x){\n        int sum = 0;\n        int temp = x;\n        while(x > 0){ // Worst case TC O(9) as the max val is 10^9\n            sum += ( x % 10);\n            x /= 10;\n        }\n        if(map.containsKey(sum)){\n            int[] j = map.get(sum);\n            int a = j[0], b = j[1];\n            \n            //insert sum at the right place \n            if(temp > a && temp > b){\n                j[0] = temp;\n                j[1] = Math.max(a, b);\n            }else j[1] = Math.max(b, temp);\n        }else{\n            map.put(sum, new int[]{temp, -1});\n        }\n    }\n}\n```\n\n```\nTC: O(N) where N = nums.length\nthe complexity to find sum of digits will be at max O(9)\n\nSC: constant - as at max there will be 82 entries in Hashmap \nas the max value of nums[i] = 999999999 with a digit sum of 81. \nHence, no matter what the length of nums, the max entries of hashmap will be 82\n```\n\n*upvote helps :)*
['Java']