Solving a Leetcode problem daily - Day 7 | Array Partition I

Solving a Leetcode problem daily — Day 7 | Array Partition I | by Subhradeep Saha | Medium

Subhradeep Saha ・ May 6, 2024 ・

Medium

Here is the Leetcode problem link — Array Partition I

Problem Statement

LeetCode presents a challenge where you’re given an integer array nums containing 2n elements. The objective is to group these elements into n pairs, where n is half the array size. Each pair consists of two elements ((a_i, b_i)) from the array. The goal is to maximize the sum obtained by adding the minimum value (min(a_i, b_i)) within each pair.

Example:

Input: nums = [1, 4, 3, 2]
Output: 4

Explanation: There are three possible pairings:

• (1, 4), (2, 3): Sum of minimums = 1 + 2 = 3

• (1, 3), (2, 4): Sum of minimums = 1 + 2 = 3

• (1, 2), (3, 4): Sum of minimums = 1 + 3 = 4

The optimal pairing is (1, 2) and (3, 4), resulting in a maximum sum of 4.

Constraints:

• The number of pairs (n) ranges from 1 to 10^4.

• The array size (nums.length) is always even (2n).

• Individual elements in the array (nums[i]) can range from -10^4 to 10^4.

High level approach

The problem looks to be complex at first glance but if we analyse the pattern of the optimal pairs, for a pair — the larger number gets sacrificed for the smaller one. To maximize the sum, we need to have the least difference between the numbers of a pair — so that for a pair, we don’t sacrifice a much bigger number.

Sorting helps us reduce the difference between the numbers of a pair and we ensure for every pair (a_i, b_i) , b_i is the least one that we sacrifice among all of the other numbers.

Code Implementation

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

Breakdown of the Code

Class and Function definition:

The code defines a class Solution with a function arrayPairSum that takes the integer array nums as input and returns the maximized sum of minimum values in pairs.

Sorting:

The sort function is used to arrange all elements in the nums array in ascending order. This step is crucial because we want to pair the smallest elements with the next larger elements to maximize the minimum value within each pair.

Iterating and Adding:

• An integer variable ans is initialized to 0 to store the accumulated sum.

• A for loop iterates through the sorted array nums with a step size of 2 (i += 2). This step size ensures we only consider the first element (minimum value) from each pair.

• Inside the loop, the value at the current index i (the minimum value in the current pair) is added to the ans variable.

Returning the Sum:

After iterating through all pairs, the final value of ans represents the maximized sum of minimum values, which is returned by the function.

Dry Run with a Test Case

Let’s use the provided example:

Input: nums = [1, 4, 3, 2]

Sorting: First, the array is sorted: [1, 2, 3, 4].

Iteration:

• Loop starts at i = 0 (index of the first element, which is 1).

• ans is incremented by nums[i] (1).

• Loop continues to i = 2 (index of the third element, which is 3).

• ans is again incremented by nums[i] (3).

• The loop terminates as it has considered all pairs (first and third elements).

Result: The final value of ans is 4 (1 + 3) — 1 from the first pair and 3 from the second pair. This matches the expected output for the given test case.

Real-World Applications

This concept of maximizing the minimum value in pairings can be applied in various real-world scenarios:

• Resource Allocation: When assigning resources (like budget, personnel, or materials) to multiple tasks or projects, this approach can help ensure that even the least-resourced projects receive enough to function at a base level, maximizing overall efficiency.

• Inventory Management: In managing inventory, prioritizing the sale of items with the lowest profit margin alongside items with higher margins can help clear out slow-moving stock while still generating some revenue.

• Network Optimization: In network routing algorithms, this strategy can be used to ensure that even the least efficient connections (with lower bandwidth) are paired with connections with higher bandwidth, optimizing overall network traffic flow.

Conclusion

This blog post explored the LeetCode challenge of maximizing the sum of minimum values in pairs. We tackled the problem statement by getting to understand how sorting helps in solving the problem, presented and explained the C++ code, performed a dry run with a test case and discussed a few real-world applications of this problem.

References

• Resource Allocation: https://www.pmi.org/learning/library/resource-allocation-5304

• Inventory Management: https://www.investopedia.com/bullwhip-effect-definition-5499228

• Network Optimization: https://en.wikipedia.org/wiki/Category:Routing_algorithms

• Cover Photo by Nick Hillier on Unsplash

If you liked this post, do applaude the post by clicking on the clap hands icon and follow me https://medium.com/@subhradeep_saha as well. Do checkout my other posts in my profile and let me know if you have any feedback. Thanks!