MediumNo. 0775
Global and Local Inversions — LeetCode 775 Python Solution
- Pattern
- Math and Number Theory
- Topics
- Array, Math
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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 nums[i] > nums[j] The number of local inversions is the number of indices i where: 0 <= i < n - 1 nums[i] > nums[i + 1] Return true if the number of global inversions is equal to the number of local inversions.
Example
- Input
- nums = [1,0,2]
- Output
- true
- Explanation
- There is 1 global inversion and 1 local inversion.
Python solution
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
mx = 0
for i in range(2, len(nums)):
if (mx := max(mx, nums[i - 2])) > nums[i]:
return False
return TrueComplexity
- Time
- O(n) or O(1)
- Space · auxiliary
- O(1)
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 775. Global and Local Inversions is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0048 | Rotate Image | Medium |
| 0066 | Plus One | Easy |
| 0189 | Rotate Array | Medium |
| 0204 | Count Primes | Medium |
| 0335 | Self Crossing | Hard |
| 0384 | Shuffle an Array | Medium |
Frequently asked questions
- How hard is LeetCode 775. Global and Local Inversions?
LeetCode 775. Global and Local Inversions is rated Medium on LeetCode.
- What topics does LeetCode 775. Global and Local Inversions cover?
LeetCode 775. Global and Local Inversions is tagged Array and Math on LeetCode.