Skip to content

Instantly share code, notes, and snippets.

@sb8244
Last active February 1, 2016 02:45
Show Gist options
  • Save sb8244/eff21ba43b27e96a0b8e to your computer and use it in GitHub Desktop.
Save sb8244/eff21ba43b27e96a0b8e to your computer and use it in GitHub Desktop.
# First sort the input using an nlogn method
# Then iterate over the array, finding the index of each value in the sorted array
# The index of the value in the sorted array is the inversion count, because all items to the left are less
# Sum those up
# Be sure to use the most efficient searching and not build in. (nlogn sort and logn search)
def solution(a)
return 0 if a.empty?
sorted = a.sort
inversions = a.each_with_index.map do |val, index|
index_in_sorted = bin_search(sorted, val)
sorted.delete_at(index_in_sorted)
index_in_sorted
end.reduce(&:+)
inversions > 1_000_000_000 ? -1 : inversions
end
def bin_search(arr, val)
bin_search_r(arr, val, 0, arr.count - 1)
end
def bin_search_r(arr, val, min, max)
mid = (max+min)/2
if arr[mid] > val
bin_search_r(arr, val, min, mid - 1)
elsif arr[mid] < val
bin_search_r(arr, val, mid + 1, max)
else
found_index = mid
while(found_index > 0 && arr[found_index-1] == val)
found_index -= 1
end
found_index
end
end
@sb8244
Copy link
Author

sb8244 commented Feb 1, 2016

Second version is much more complex, but solves it in the space required. If this was going to be done on arrays < 10000, I would definitely opt for the first one.

Ruby 2.3 introduces Array#bsearch_index which would remove most of this code

@sb8244
Copy link
Author

sb8244 commented Feb 1, 2016

Credit to https://www.quora.com/How-can-the-number-of-inversions-between-two-arrays-be-calculated-in-O-N-log-N because I wouldn't have known that about inversion count.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment