MINIMUM COST TO SORT ARRAY II

Problem Statement

You are given an array of elements of size ’n’ containing integers from 1 to n. You can perform swaps between any two elements in the array, and each swap incurs a cost of 1. Your task is to determine the minimum cost to sort the array in a non-decreasing order.

Input Format

  • An array of integers: arr (1 ≤ arr ≤ 10^5), where arr is the number of elements in the array.
  • The elements of the array are unique integers from 1 to n.

Output Format

  • An integer representing the minimum cost to sort the array.

Constraints

  • 1 ≤ n ≤ 10^5
Sample Input
Sample Output

Solution

file_type_python minimum_cost_to_sort_array_ii.py 
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    arrI = [(l[i], i) for i in range(n)]
    arrI.sort()
    visited = [False]*n
    swaps = 0
    for i in range(n):
        if visited[i] or arrI[i][1] == i:
            continue
        cyc = 0
        j = i
        while not visited[j]:
            visited[j] = True
            j = arrI[j][1]
            cyc += 1
        if cyc > 0:
            swaps += cyc - 1
    print(swaps)

Comments

Load Comments