Find the Minimum Cost to Sort the Array in Ascending or Descending Order

Given a list of integers nums, return the minimum cost of sorting the list in ascending or descending order. The cost is defined as the sum of differences between any element’s old and new value.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 4, 3]

Output
2
Explanation
The cost to change the list to ascending order is 2:
Change 4 to 3 for a cost of 1
Change 3 to 4 for a cost of 1

Example 2
Input
nums = [7, 3, 5]
Output
4
Explanation
The cost to change the list to descending order is 4:
Change 3 to 5 for a cost of 2
Change 5 to 3 for a cost of 2

Minimum Cost Sort Algorithm

We can sort the array twice one in ascending order, one in descending order, and compute the total cost for each way. The complexity is O(NlogN). The space complexity is O(N) as we are allocating two arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int minCostToSort(vector<int>& nums) {
    vector<int> a1 = nums;
    vector<int> a2 = nums;
    sort(begin(a1), end(a1));
    sort(rbegin(a2), rend(a2));
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        sum1 += abs(nums[i] - a1[i]); 
    }
    for (int i = 0; i < nums.size(); ++ i) {
        sum2 += abs(nums[i] - a2[i]); 
    }
    return min(sum1, sum2);
}

int minCostToSort(vector<int>& nums) {
    vector<int> a1 = nums;
    vector<int> a2 = nums;
    sort(begin(a1), end(a1));
    sort(rbegin(a2), rend(a2));
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        sum1 += abs(nums[i] - a1[i]); 
    }
    for (int i = 0; i < nums.size(); ++ i) {
        sum2 += abs(nums[i] - a2[i]); 
    }
    return min(sum1, sum2);
}

The improvement is only to sort the array once and index it from left-to-right and right-to-left directions in order to compute the costs. The complexity is still the same, however, the implementation improves the runtime twice as fast.

1
2
3
4
5
6
7
8
9
10
11
12

int minCostToSort(vector<int>& nums) {
    vector<int> a1 = nums;
    sort(begin(a1), end(a1));
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        sum1 += abs(nums[i] - a1[i]); 
    }
    for (int i = 0; i < nums.size(); ++ i) {
        sum2 += abs(nums[i] - a1[nums.size() - 1 - i]); 
    }
    return min(sum1, sum2);
}

int minCostToSort(vector<int>& nums) {
    vector<int> a1 = nums;
    sort(begin(a1), end(a1));
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        sum1 += abs(nums[i] - a1[i]); 
    }
    for (int i = 0; i < nums.size(); ++ i) {
        sum2 += abs(nums[i] - a1[nums.size() - 1 - i]); 
    }
    return min(sum1, sum2);
}

–EOF (The Ultimate Computing & Technology Blog) —