Inversion is a strictly decreasing subsequence of length 3. More formally, given an array, p, an inversion in the array is any time some p[i] > p[j] > p[k] and i < j < k. Given an array of length n, find the number of inversions.
Example)
n = 5, arr = [5, 3, 4, 2, 1]
Array inversions are [5, 3, 2], [5,3,1], [5,4,2], [5,4,1], [5,2,1], [3,2,1], [4,2,1]
n = 4, arr = [4,2,2,1]
The only inversion is [4,2,1] and we do not count the duplicate inversion.
# duplicate is not allowed
class Solution:
def findInversions(self, arr):
result = set()
n = len(arr)
candidate = []
def backtrack(start):
if len(candidate) == 3:
result.add(tuple(candidate[:]))
return
for i in range(start, len(arr)):
if not candidate:
candidate.append(arr[i])
backtrack(i)
candidate.pop()
elif candidate and arr[i] < candidate[-1]:
candidate.append(arr[i])
backtrack(i)
candidate.pop()
for i in range(n):
backtrack(i)
print(result)
return len(set(result))
s = Solution()
# arr = [5, 3, 4, 2, 1]
# [5, 3, 2], [5,3,1], [5,4,2], [5,4,1], [5,2,1], [3,2,1], [4,2,1] result = 7
# arr = [4,2,2,1]
# result = 1
# arr = [4, 2, 3, 2, 1]
# [4,3,1] [4,2,1] [3,2,1] [4,3,2] result = 4
arr = [4,2,1,4,2,1]
# [4,2,1]
result = s.findInversions(arr)
print(result)Comments (8)