Global and Local Inversions

Problem Description

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1]. The number of global inversions is the number of the different pairs (i, j) where 0 <= i < j < n and nums[i] > nums[j]. The number of local inversions is the number of indices i where 0 <= i < n - 1 and nums[i] > nums[i + 1]. Return true if the number of global inversions is equal to the number of local inversions.

Key Insights

• A global inversion counts pairs (i, j) where elements are out of order, allowing for any distance between i and j.
• A local inversion counts only adjacent pairs, which are a subset of global inversions.
• If the number of global inversions equals the number of local inversions, it implies that there are no inversions more than one position apart.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To determine if the number of global inversions is equal to the number of local inversions, we can iterate through the array and check for any global inversions that are not local. Specifically, we just need to ensure that for every element nums[i], it is in the correct position relative to the next two elements nums[i+1] and nums[i+2]. If any element nums[i] is greater than nums[i+2], this indicates a global inversion that is not local.

Code Solutions