Solving a Leetcode problem daily - Day 7 | Array Partition I
Tags: array, cpp, leetcode, sort
Published: 2024-05-06 02:30:00

{% embed  https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-7-array-partition-i-2d915d787469 %}

---

Here is the Leetcode problem link — [Array Partition I](https://leetcode.com/explore/learn/card/array-and-string/205/array-two-pointer-technique/1154/)

---

### **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:**

```cpp
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**

```cpp
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:

```cpp
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](https://www.pmi.org/learning/library/resource-allocation-5304)
    
* **Inventory Management:** [https://www.investopedia.com/bullwhip-effect-definition-5499228](https://www.investopedia.com/bullwhip-effect-definition-5499228)
    
* **Network Optimization:** [https://en.wikipedia.org/wiki/Category:Routing\_algorithms](https://en.wikipedia.org/wiki/Category:Routing_algorithms)
    
* Cover Photo by [Nick Hillier](https://unsplash.com/@nhillier?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash) [on Unsplash](https://unsplash.com/@nhillier?utm_content=creditCopyText&utm_medium=referral&utm_source=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](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!