Problem: Global and Local Inversions

The problem asks to determine if the number of global inversions equals the number of local inversions in a given permutation array. A global inversion is a pair (i, j) where i < j and nums[i] > nums[j]. A local inversion is a pair (i, i+1) where nums[i] > nums[i+1].

Solution 1: Linear Scan

This solution cleverly avoids explicitly calculating global inversions. It leverages the fact that if a global inversion is not a local inversion, it must involve indices that are at least two positions apart.

Algorithm:

1. Initialize mx to 0. This variable will track the maximum value encountered so far, excluding the current and next elements.

2. Iterate through the array starting from the third element (index 2).

3. In each iteration, update mx to the maximum of mx and nums[i-2].

4. If mx > nums[i], it indicates a global inversion that's not local because it involves elements that are at least two positions apart. The function immediately returns false.

5. If the loop completes without finding such a case, it means all global inversions are local, and the function returns true.

Time Complexity: O(n), where n is the length of the input array. The solution iterates through the array once.

Space Complexity: O(1), as it uses only a constant amount of extra space.

Code (Python):

class Solution:
    def isIdealPermutation(self, nums: List[int]) -> bool:
        mx = 0
        for i in range(2, len(nums)):
            mx = max(mx, nums[i - 2])
            if mx > nums[i]:
                return False
        return True

Code (Java):

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int mx = 0;
        for (int i = 2; i < nums.length; ++i) {
            mx = Math.max(mx, nums[i - 2]);
            if (mx > nums[i]) {
                return false;
            }
        }
        return true;
    }
}

Code (C++):

class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int mx = 0;
        for (int i = 2; i < nums.size(); ++i) {
            mx = max(mx, nums[i - 2]);
            if (mx > nums[i]) return false;
        }
        return true;
    }
};

Code (Go):

func isIdealPermutation(nums []int) bool {
	mx := 0
	for i := 2; i < len(nums); i++ {
		mx = max(mx, nums[i-2])
		if mx > nums[i] {
			return false
		}
	}
	return true
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Solution 2: Binary Indexed Tree (Fenwick Tree)

This solution uses a Binary Indexed Tree (BIT) to efficiently count inversions. It directly addresses the condition of checking if the global and local inversions are equal.

Algorithm:

1. Create a Binary Indexed Tree (BIT) of size n+1 to store cumulative counts.

2. Initialize cnt to 0, which tracks the difference between global and local inversions.

3. Iterate through nums:

   • If a local inversion exists (nums[i] > nums[i+1]), increment cnt.
   • Subtract the number of elements less than nums[i] that have already been seen (using BIT.query(nums[i])) from i. This accounts for global inversions that are not local.
   • Update the BIT with nums[i] using BIT.update(nums[i] + 1, 1).

4. If at any point cnt becomes negative, it means there are more global inversions not accounted for as local inversions, and we return false.

5. Finally, we check if cnt is 0, indicating an equal number of global and local inversions.

Time Complexity: O(n log n), due to the use of the Binary Indexed Tree. BIT.update and BIT.query operations take O(log n) time.

Space Complexity: O(n) for the Binary Indexed Tree.

Code (Python): (Binary Indexed Tree implementation included)

class BinaryIndexedTree:
    # ... (implementation from above)
 
class Solution:
    # ... (implementation from above)

(Similar implementations for Java, C++, and Go are provided above, including the Binary Indexed Tree implementation.)

Note: Solution 1 is significantly more efficient than Solution 2. Solution 2 is provided for completeness and to demonstrate an alternative approach using a more advanced data structure, but it's not the optimal solution for this problem in terms of time complexity. For most cases, the linear-time solution is preferred.