LeetCode in Kotlin

493. Reverse Pairs

Hard

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example 1:

Input: nums = [1,3,2,3,1]

Output: 2

Explanation: The reverse pairs are:

(1, 4) –> nums[1] = 3, nums[4] = 1, 3 > 2 * 1

(3, 4) –> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1]

Output: 3

Explanation: The reverse pairs are:

(1, 4) –> nums[1] = 4, nums[4] = 1, 4 > 2 * 1

(2, 4) –> nums[2] = 3, nums[4] = 1, 3 > 2 * 1

(3, 4) –> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Constraints:

• 1 <= nums.length <= 5 * 104
• -231 <= nums[i] <= 231 - 1

Solution

class Solution {
    fun reversePairs(nums: IntArray): Int {
        return mergeSort(nums, 0, nums.size - 1)
    }

    private fun mergeSort(nums: IntArray, start: Int, end: Int): Int {
        if (start >= end) {
            return 0
        }
        val mid = start + (end - start) / 2
        var cnt = mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end)
        var j = mid + 1
        for (i in start..mid) {
            // it has to be 2.0 instead of 2, otherwise it's going to stack overflow, i.e. test3 is
            // going to fail
            while (j <= end && nums[i] > nums[j] * 2.0) {
                j++
            }
            cnt += j - (mid + 1)
        }
        nums.sort(start, end + 1)
        return cnt
    }
}

This site is open source. Improve this page.