Day-15 Array Partition I

Background

This problem statement was a part of LeetCode's learn card: Array and Strings. Under the sub-heading Two pointer technique.

Problem Statement

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

Solution Approach 1

1. Pick some random examples. And, try calculating the sum of pairs manually for different combination of integers to see if there is some pattern.
2. Based on step 1. One conclusion that can be drawn is pairing consecutive small numbers together, followed by pairing large numbers. Leads to maximum sum.
3. Now, 2 achieve step 2. We can sort the given array.
4. Once the array is sorted. We can have 2 variables. One variable points to the current element. Another element points to the next element.
5. The current element and the next element form a pair.
6. Size of array is 2n. Number of pairs are n is mentioned in the problem statement. Based on this we can break the loop.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        current=0
        next_element = current+1
        total = 0
        counter = 0     
        nums.sort()
        while current < next_element:
            total += min(nums[current], nums[next_element])
            current  = next_element + 1
            next_element = current+ 1
            counter += 1
            if counter == int(len(nums)/2):
                break
        return total

Learnings and obervation from solution approach 1

1. Time complexity of list.sort() is O(nlogn). Then we are iterating over the list. And calling built-in method min. Min has its own complexity. This in turn would increase the overall time complexity.
2. We are already sorting the array. And then forming pairs. So, always the minimum element would be the current element. Hence, no need to again call built-in min method to find the minimum of the two numbers.

Updated code based on takeaways from solution approach 1

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        current=0
        next_element = current+1
        total = 0
        counter = 0
        nums.sort()
        while current < next_element:
            total += nums[current]
            current  = next_element + 1
            next_element = current+ 1
            counter += 1
            if counter == int(len(nums)/2):
                break
        return total

In the above solution, we are breaking the loop when count of pairs is equal to half the length of the array. Another approach could be to scrap this whole part off. Instead, put this condition. The index of current element should always be less the length of array.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        current=0
        next_element = current+1
        total = 0
        nums.sort()
        while current < next_element and current < len(nums)-1:
            total += nums[current]
            current  = next_element + 1
            next_element = current+ 1
        return total

Learnings

1. Time complexity - O(nlogn).
2. Got rid of unnecessary min() built-in function.
3. Two pointer technique.
4. List.sort() method is an in-place sort. Using sorted() for sorting would have returned a new list. That, however, was not needed.