****C++ Code

int lilysHomework(vector<int> arr) {
    vector<int> arr1(arr);
    unordered_map<int,int>mp;
    unordered_map<int,int>mp1;
    for(int i=0;i<arr.size();i++)
        mp[arr[i]]=i;
    for(int i=0;i<arr1.size();i++)
        mp1[arr1[i]]=i;
    vector<int> v(arr);
    vector<int> v1(arr1);
    sort(v.begin(),v.end());
    sort(v1.begin(),v1.end(),greater<int>());
    int c=0,c1=0;
    for(int i=0;i<arr.size();i++){
        if(arr[i]!=v[i]){
            c++;

            int t1=mp[v[i]];
            mp[arr[i]]=t1;
            swap(arr[i],arr[t1]);
        }
    }
     for(int i=0;i<arr1.size();i++){
        if(arr1[i]!=v1[i]){
            c1++;
            int t1=mp1[v1[i]];
            mp1[arr1[i]]=t1;
            swap(arr1[i],arr1[t1]);
        }
    }
    return min(c,c1);
}

I found that using swap sort just like problem state with dynamic programming is really fast. Just create a dict store indexes of all elements in array.

def swapSort(arr, n, reverse):
    result = 0
    index = {}
    for i in range(n):
        index[arr[i]] = i
    s = sorted(arr) if reverse == False else sorted(arr, reverse=True)
    cur = 0
    while cur < n:
        a, m = arr[cur], s[cur]
        if a != m:      
            x = index[m]
            arr[x] = a
            index[a] = x
            result += 1
        cur += 1
    return result


def lilysHomework(arr):
    n = len(arr)
    s, r = arr[:], arr[:]
    count1 = swapSort(s, n, reverse=False)
    count2 = swapSort(r, n, reverse=True)
    return min([count1, count2])


n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = lilysHomework(arr)
print(result)

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.function.; import java.util.regex.; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList;

class Result {

/*
 * Complete the 'lilysHomework' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

public static int lilysHomework(List<Integer> arr) {
// Write your code here
List<Integer> arr2 = new ArrayList<>(arr);  // it is used for decreasing order

List<Integer> sort_arr = new ArrayList<>(arr);
List<Integer> sort_arr_rev = new ArrayList<>(arr);
Collections.sort(sort_arr);
Collections.sort(sort_arr_rev, Collections.reverseOrder());

// System.out.println(sort_arr);
// System.out.println(arr);
int count = 0;
int rev = 0;

for(int i=0; i<arr.size(); i++){  // It is used to count the no. of swap for increasing order
    List<Integer> li = findMinMax_Index(arr, arr2, i, arr.size()-1);
    // System.out.println(li);
    // System.out.println("arr= "+arr);
    // System.out.println("arr2= "+arr2);

    int min_idx = li.get(0);

    if(arr.equals(sort_arr)==false && i != min_idx){
        Collections.swap(arr, i, min_idx);
        count++;
    }

    int max_idx = li.get(1); // It is used to count the no. of swap for decreasing order
    if(arr2.equals(sort_arr_rev)==false && i != max_idx){
        Collections.swap(arr2, max_idx, i);
        rev++;
    }

    if(arr.equals(sort_arr) && rev>count){
        break;
    }
    if(arr2.equals(sort_arr_rev) && count>rev){
        break;
    }

}


if(count < rev){
    return count;
}
else{
    return rev;
}

}

public static List<Integer> findMinMax_Index(List<Integer> arr, List<Integer> arr2, int start, int end){
    int min = Integer.MAX_VALUE;
    int min_idx = 0;

    int max = 0;
    int max_idx = 0;

    for(int i=start; i<=end; i++){
        if(arr.get(i) < min){
            min = arr.get(i);
            min_idx = i;
        }
         if(arr2.get(i) > max){
            max = arr2.get(i);
            max_idx = i;
        }
    }
    // System.out.println("arr= "+arr);
    // System.out.println("arr2= "+arr2);
    // System.out.println("min= "+min_idx+" max= "+max_idx);

    List<Integer> li_ans = new ArrayList<>();
    li_ans.add(min_idx);
    li_ans.add(max_idx);

    return li_ans;
}

}

public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int n = Integer.parseInt(bufferedReader.readLine().trim());

    List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
        .map(Integer::parseInt)
        .collect(toList());

    int result = Result.lilysHomework(arr);

    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    bufferedReader.close();
    bufferedWriter.close();
}

}

hii fellow coders below is my logic which i use to min swap (basically I initially comparing my first value to second and if my value is found big then I will traverse again the array to see there is a more less value which is present in the array or not if we found then we will swap . but somwhere Iam wrong please help me guys

int n=arr.size()-1; int count=0; for(int i=r;iarr.get(i+1)){ int min=i+1; int j=min; while(jarr.get(j)){ min=j; } j++; } if(arr.get(i)>arr.get(min)){ int temp=arr.get(i); arr.add(i, arr.get(min)); arr.add(min,temp); count++;
} }
} return count;
}

O(nlogn) graph solution using dfs with Chinese explanation

https://gist.github.com/Shuntw6096/ce7d0f2a2aa6ef784da493ff2e9755a3