Minimum Cost to Sort an Array by Sorting Subarrays

Sorting problems are among the most important topics in Data Structures and Algorithms. In this problem, we are given a special type of sorting operation where instead of swapping elements individually, we can sort any subarray in one operation. However, every operation comes with a cost, and our goal is to minimize the total cost required to sort the complete array.

You are given an array of N integers. Your task is to sort the entire array using the following operation:

• In a single operation, you may choose any contiguous subarray and sort it.
• The cost of performing the operation is equal to the square of the length of the selected subarray.

Your objective is to determine the minimum total cost required to make the whole array sorted in non-decreasing order.

Input Format

• The first line contains an integer T, representing the number of test cases.
• For each test case:
  • The first line contains an integer N, the size of the array.
  • The second line contains N space-separated integers representing the array elements.

Output Format

For each test case, print the minimum cost required to sort the array.

Constraints

Example 1

Input:

1
4
4 3 2 1

Output:

16

Explanation

We can select the complete array [4, 3, 2, 1] and sort it in one operation.

• Length of selected subarray = 4
• Cost = 4 × 4 = 16

Hence, the minimum cost required is 16.

Example 2

Input:

1
6
2 3 1 6 4 5

Output:

18

Explanation

The array is not sorted because:

• 1 should come before 2 and 3
• 4 and 5 should come before 6

To sort the array with minimum cost, we can perform the following operations:

• Select the subarray [2, 3, 1] and sort it.
• After sorting: [1, 2, 3, 6, 4, 5]
• Length of subarray = 3, Cost = 3² = 9
• Select the subarray [6, 4, 5] and sort it.
• After sorting: [1, 2, 3, 4, 5, 6]
• Length of subarray = 3, Cost = 3² = 9
• Total minimum cost: 9 + 9 = 18

Hence, the answer is: 18

Understanding the Core Idea

The most important observation in this problem is: We do not need to sort the entire array every time. Instead, we only need to focus on the portions of the array where the elements are misplaced. If a part of the array is already arranged exactly as it would appear in the fully sorted array, then sorting that part again is unnecessary. Performing operations on already-correct sections only increases the total cost without providing any benefit.

Since the cost of an operation depends on the square of the subarray length, unnecessarily choosing larger subarrays can make the total cost much higher.

Therefore, the main objective is:

• Identify the elements or regions that are out of order.
• Find the smallest possible contiguous subarrays that need sorting.
• Avoid including correctly placed elements whenever possible.

The entire problem revolves around minimizing the total cost by sorting only the required sections of the array.

Brute Force Approach

The brute force approach is based on one simple idea: Try every possible operation and choose the sequence of operations that produces the minimum total cost.

Since we do not initially know which subarrays should be sorted, the brute force solution explores all possibilities. For every step:

• Select any possible subarray.
• Sort that subarray.
• Observe the updated array.
• Continue applying operations until the entire array becomes sorted.

Finally, among all possible ways of sorting the array, we choose the one with the smallest total cost.

This approach guarantees the correct answer because no possible solution is ignored. However, the number of possibilities grows extremely fast, making the solution computationally expensive.

How the Brute Force Approach Works

The solution recursively explores every possible subarray operation. At each recursive step:

• Choose a subarray (i, j).
• Sort the selected subarray.
• Calculate the cost of the current operation.
• Recursively solve the remaining array.
• Add the current operation cost to the recursive answer.
• Track the minimum total cost among all choices.

By exploring every possible sequence of operations, the brute force method ensures that the optimal answer is always found.

The major drawback is that many array states are recomputed repeatedly, causing a massive amount of redundant work. As the array size increases, the total number of recursive states grows exponentially, making this approach impractical for large constraints.

Steps of the Brute Force Approach

• Check whether the array is already sorted.
  • If yes, return 0.
• Generate all possible subarrays (i, j).
• For every subarray:
  • Sort the selected subarray.
  • Calculate the operation cost.
  • Recursively solve the updated array.
• Add the current operation cost to the recursive result.
• Track the minimum answer among all possible operations.
• Return the minimum total cost required to sort the array.

Time Complexity

• Exponential : Because we try every possible subarray combination.

Space Complexity

• O(N), Due to recursion and array copies.

Better Observation

Instead of trying every possible operation, we can make an important observation that simplifies the problem significantly. Consider comparing the original array with its fully sorted version.

While traversing the array, we want to identify the smallest independent regions that can be sorted separately. If a portion of the array already matches the sorted order, then we do not need to perform any operation on that region. Only the misplaced parts of the array contribute to the answer.

However, simply checking continuous mismatched indices is not enough. Two distant portions of the array may actually belong to different independent sortable chunks even if every index between them is mismatched. Therefore, we need a smarter way to identify valid independent segments.

This transforms the problem from an exponential search problem into a partition-identification problem.

Key Insight

• Let: sorted[] = sorted version of arr[]
• Now traverse both arrays together from left to right.
• For every index:
  • keep track of the maximum element seen so far in the original array, and the maximum element seen so far in the sorted array.
  • Whenever: maxOriginal == maxSorted
  • it means the current region forms an independent sortable chunk.
  • That chunk can be sorted separately without affecting elements outside the chunk.
  • Additionally, we only add cost if that chunk actually contains at least one mismatch.

Why This Observation Works

• Consider the example: arr = [2, 3, 1, 6, 4, 5]
• Sorted version: sorted = [1, 2, 3, 4, 5, 6]
• Now compare step-by-step.

• At index 2, both maxima become equal.
• This means: [2,3,1] forms one valid independent segment.
• Sorting this segment gives: [1,2,3]
• Now continue.

• Again maxima become equal at index 5.
• So: [6,4,5]
• forms another independent segment.

Thus instead of sorting the entire array of length 6, we can sort two smaller chunks independently.

Why Smaller Independent Segments Are Better

The operation cost is:(length)^2

If we merge two independent chunks:

(a+b)^2 >a^2+b^2

So sorting smaller independent segments always produces a smaller total cost. That is why identifying maximum possible independent chunks gives the optimal answer.

Optimal Approach

The optimal solution is based on partitioning the array into smallest valid sortable chunks. The main idea is:

• Create a sorted copy of the array.
• Traverse both arrays together.
• Maintain:
  • maximum element seen so far in original array,
  • maximum element seen so far in sorted array.
• Whenever both maxima become equal:
  • we found one independent sortable chunk.
• If that chunk contains at least one mismatch:
  • calculate its length,
  • add square of the length to the final answer.

This guarantees the minimum possible cost because every chunk is processed independently and no unnecessary larger segment is created.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minimumCost(vector<int>& arr) {
    int n = arr.size();
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());

    int cost = 0;
    int start = 0;
    int maxArr = INT_MIN;
    int maxSorted = INT_MIN;
    bool hasMismatch = false;

    for (int i = 0; i < n; i++) {
        maxArr = max(maxArr, arr[i]);
        maxSorted = max(maxSorted, sorted[i]);
        if (arr[i] != sorted[i]) {
            hasMismatch = true;
        }

        // valid independent chunk
        if (maxArr == maxSorted) {
            if (hasMismatch) {
                int len = i - start + 1;
                cost += len * len;
            }
            start = i + 1;
            hasMismatch = false;
        }
    }
    return cost;
}

int main() {
    vector<int> arr = {2, 3, 1, 6, 4, 5};
    cout << minimumCost(arr) << endl;
    return 0;
}

import java.util.*;

public class Main {

    public static int minimumCost(int[] arr) {
        int n = arr.length;
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        int cost = 0;
        int start = 0;
        int maxArr = Integer.MIN_VALUE;
        int maxSorted = Integer.MIN_VALUE;
        boolean hasMismatch = false;
        for (int i = 0; i < n; i++) {
            maxArr = Math.max(maxArr, arr[i]);
            maxSorted = Math.max(maxSorted, sorted[i]);
            if (arr[i] != sorted[i]) {
                hasMismatch = true;
            }
            // valid independent chunk
            if (maxArr == maxSorted) {
                if (hasMismatch) {
                    int len = i - start + 1;
                    cost += len * len;
                }
                start = i + 1;
                hasMismatch = false;
            }
        }
        return cost;
    }
    public static void main(String[] args) {

        int[] arr = {2, 3, 1, 6, 4, 5};

        System.out.println(minimumCost(arr));
    }
}

using System;

class Program
{
    static int MinimumCost(int[] arr)
    {
        int n = arr.Length;
        int[] sorted = (int[])arr.Clone();
        Array.Sort(sorted);

        int cost = 0;
        int start = 0;
        int maxArr = int.MinValue;
        int maxSorted = int.MinValue;
        bool hasMismatch = false;

        for (int i = 0; i < n; i++)
        {
            maxArr = Math.Max(maxArr, arr[i]);
            maxSorted = Math.Max(maxSorted, sorted[i]);
            if (arr[i] != sorted[i])
            {
                hasMismatch = true;
            }
            // valid independent chunk
            if (maxArr == maxSorted)
            {
                if (hasMismatch)
                {
                    int len = i - start + 1;
                    cost += len * len;
                }
                start = i + 1;
                hasMismatch = false;
            }
        }
        return cost;
    }

    static void Main()
    {
        int[] arr = { 2, 3, 1, 6, 4, 5 };
        Console.WriteLine(MinimumCost(arr));
    }
}

def minimum_cost(arr):
    n = len(arr)
    sorted_arr = sorted(arr)

    cost = 0
    start = 0
    max_arr = float('-inf')
    max_sorted = float('-inf')
    has_mismatch = False

    for i in range(n):
        max_arr = max(max_arr, arr[i])
        max_sorted = max(max_sorted, sorted_arr[i])
        if arr[i] != sorted_arr[i]:
            has_mismatch = True
        # valid independent chunk
        if max_arr == max_sorted:
            if has_mismatch:
                length = i - start + 1
                cost += length * length
            start = i + 1
            has_mismatch = False

    return cost

arr = [2, 3, 1, 6, 4, 5]
print(minimum_cost(arr))

Time Complexity

• Sorting O(NlogN) Array Traversal O(N)
• Total: O(NlogN)

Space Complexity

• We store one extra sorted array. O(N)