https://www.hackerrank.com/challenges/lilys-homework/problem

hackerrank-lilysHomework.py

#!/bin/python3

import math
import os
import random
import re
import sys

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

def lilysHomework(arr):
    asc_arr = list(sorted(arr))
    des_arr = list(reversed(asc_arr))
    
    # Write your code here
    min_cnt = len(arr)
    for correct_arr in [asc_arr, des_arr]:
        # copy original array, since we should not change original array
        arr_copy = arr.copy()
        # intermediate state checking
        intermediate_state = {arr_copy[i]: i for i in range(len(arr_copy))}
        cnt = 0
        for i in range(len(arr_copy)):
            current_value = arr_copy[i]
            answer_value = correct_arr[i]
            if current_value != answer_value:
                # find idx of answer_value in intermediate state
                answer_idx = intermediate_state[answer_value]
                # swap(update) intermediate state
                intermediate_state[current_value], intermediate_state[answer_value] = intermediate_state[answer_value], intermediate_state[current_value]
                arr_copy[i], arr_copy[answer_idx] = arr_copy[answer_idx], arr_copy[i]
                cnt += 1
        min_cnt = min(min_cnt, cnt)

    return min_cnt

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    result = lilysHomework(arr)

    fptr.write(str(result) + '\n')

    fptr.close()