I tried 2 patterns for minimum swaps2 of Hackerrank. One pattern faces the termination due to timeout. I wonder what the reason of the difference was.
#Pattern 1 Terminated due to timeout
def minimumSwaps1(arr):
count = 0
for i, v in enumerate(arr):
if v != i + 1:
idx = arr.index(i + 1)
arr[i], arr[idx] = arr[idx], arr[i]
count += 1
return count
#Pattern 2 Passed all test case
def minimumSwaps2(arr):
tmp = arr.copy()
for i, v in enumerate(arr):
tmp[v-1] = i
count = 0
for i in range(len(arr) - 1):
a = arr[i]
if a != i + 1:
arr[i] = i + 1
arr[tmp[i]] = a
tmp[a-1] = tmp[i]
count += 1
return count
I measured the 2 tests with time.perf_counter() and the result was below:
arr = list(reversed(list(range(1, 100001))))
start_time = time.perf_counter()
minimumSwaps1(arr)
print("Result1: ", time.perf_counter() - start_time)
Pattern1: 0.015803417
Pattern2: 0.044271668
Pattern1 is faster than Pattern2, but only Patter2 passed all test… I wonder why?