Global and Local Inversions

Problem Statement

Given an integer array nums which has a length n and is a permutation of all integers within the range [0, n - 1], we are tasked with analyzing two types of inversion counts within this array:

1. Global Inversions: These are counted by determining the number of pairs (i, j) such that 0 <= i < j < n and nums[i] > nums[j]. This essentially tallies how many times a larger number appears before a smaller number throughout the entire array.

2. Local Inversions: This count focuses on immediate adjacencies within the array, specifically counting the instances where for a particular index i (where 0 <= i < n - 1), the element nums[i] is greater than the element directly following it, nums[i + 1].

The core question posed by the problem is to return true if and only if the number of global inversions exactly matches the number of local inversions.

Examples

Example 1

Input:

nums = [1,0,2]

Output:

true

Explanation:

There is 1 global inversion and 1 local inversion.

Example 2

Input:

nums = [1,2,0]

Output:

false

Explanation:

There are 2 global inversions and 1 local inversion.

Constraints

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] < n
• All the integers of nums are unique.
• nums is a permutation of all the numbers in the range [0, n - 1].

Approach and Intuition

To solve this problem, understanding the relationship and the distinction between global and local inversions is crucial:

• Every local inversion is inherently a global inversion since it involves a pair of consecutive elements where the previous is greater than the next. Therefore, any pair (i, i+1) contributing to local inversion also contributes to global inversion.

• However, not all global inversions are local. A global inversion involving non-consecutive elements (e.g., i and j where j > i + 1) is not counted in local inversions.

Given these relationships, the problem can be reduced to checking if there exists any global inversion that is not a local inversion. If such an inversion exists, then the number of global inversions would be greater than the number of local inversions, leading to a return of false. Conversely, if every global inversion is also a local inversion (hence no "non-local" global inversions exist), the array likely has some characteristics of a nearly sorted list where elements do not jump over each other by more than one position.

When examining example cases:

• For nums = [1,0,2], the only inversion is between the first two elements, which is both a local and a global inversion (total of one each), making the condition true.
• For nums = [1,2,0], besides the local inversion between the last two elements (2 > 0), there exists a non-local global inversion between the first and last elements (1 > 0), causing the total global inversions to exceed local inversions, thus returning false.

Understanding this, a strategic approach might be to parse through the list and ascertain that no element is out of place relative to another by more than one position. Otherwise, a more in-depth calculation of all pairs might be necessary, though likely inefficient given potential constraints.

Solutions

class Solution {
    public boolean checkPerfectPermutation(int[] nums) {
        for (int index = 0; index < nums.length; ++index)
            if (Math.abs(nums[index] - index) > 1)
                return false;
        return true;
    }
}