Clean code with explanation


  • 0
    K
    class Solution {
    public:
        int arrayPairSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int result = 0;
            for(int i = 0; i < nums.size(); i+=2){
                result += nums[i];
            }
            return result;
        }
    };
    

    Let me explain what it means by "makes sum of min(ai, bi) for all i from 1 to n as large as possible."
    Say you have an input of [1,2,3,4,5,6]
    The best grouping method would be: min(1,2) min(3,4) min(5,6) and the result would be 1+3+5 = 9.
    How about other combinations? Say you swap 2 and 4 you will get: min(1,4) min(3,2) min(5,6) and the result would be 1+2+5 = 8 which is smaller than 9.
    The correctness can be easily proved by contradiction.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.