Find Size 3 Inversions in a list
Description: (copied from https://leetcode.com/discuss/interview-question/777188/find-size-3-inversions-in-a-list)
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.
Solution Tips:
For every number x in arr, find numbers bigger than x in the left, numbers smaller than x in the right, and then multiply the two numbers.
First Solution:
Time Complexity: O(N^2)
Space Complexity: O(N)
def inversion(arr):
delete_duplicate = {}
ans = 0
for i in range(len(arr)):
# cur is the second number
cur = arr[i]
# filter number have already calculated, because when an number have already shown before cur number, it has already count the numbers after cur number
if delete_duplicate.get(cur) == None:
# count nums left to the cur number and bigger than cur number
count_left = len(set([x for x in arr[:i] if x > cur]))
# count nums right to the cur number and smaller than cur number
count_right = len(set([x for x in arr[i:] if x < cur]))
ans += count_left * count_right
delete_duplicate[cur] = True
return ansSecond Solution
Using binary search method, idea from https://leetcode.com/problems/count-good-triplets-in-an-array/discuss/?currentPage=1&orderBy=newest_to_oldest&query=, thanks @1mKnown offered!
Time Complexity: O(NlogN)
Space Complexity: O(N)
def inversion(arr):
# create array for no duplicate
A = [arr[0]]
# create map for check duplicate
num_map = {}
num_map[arr[0]] = True
pos_in_b, ans_list = SortedList([A[0]]), [0]
# count left part which over cur number
for a in arr[1:]:
if num_map.get(a) != None:
continue
A.append(a)
num_map[a] = True
pos_in_b.add(a)
ans_list.append(len(pos_in_b)-1 - bisect.bisect_left(pos_in_b, a))
# last index does not have right part, so it's zero
ans_list[-1] = 0
suf_in_b = SortedList([A[-1]])
# count right part which over cur number
for index in range(len(A)-2, -1, -1):
a = A[index]
ans_list[index] = ans_list[index] * (bisect.bisect(suf_in_b, a))
suf_in_b.add(a)
return sum(ans_list)