We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Global and Local Inversions

Number: 790

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array nums which is a permutation of [0, n - 1], count the number of global inversions (pairs (i, j) such that i < j and nums[i] > nums[j]) and local inversions (indices i such that nums[i] > nums[i+1]). Return true if they are equal; otherwise, false.

Key Insights

  • Every local inversion is a global inversion.
  • For the counts to be equal, all global inversions must be local inversions.
  • A global inversion that is not local exists if an element is placed more than one position away from its index.
  • It is sufficient to check if the element's value differs from its index by more than 1.

Space and Time Complexity

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

Solution

The idea is to iterate through the array and for each index check if the absolute difference between the element value and its index is more than one. If any element is displaced by more than one position, there exists a non-local global inversion and we return false. If no such element is found, return true. This approach leverages a simple linear scan and a constant extra space check, ensuring both optimal time and space complexity.

Code Solutions

# Function to check if global inversions are equal to local inversions
def isIdealPermutation(nums):
    # Iterate through the array
    for i in range(len(nums)):
        # Check if the absolute difference between current element and its index is greater than 1
        if abs(nums[i] - i) > 1:
            # If yes, then there exists a non-local inversion, return False.
            return False
    # If no such element is found, all inversions are local; return True.
    return True

# Example usage
nums = [1, 0, 2]
print(isIdealPermutation(nums))  # Expected output: True
← Back to All Questions