775. Global and Local Inversions

MediumArrayMath
Leetcode Link

Problem Description

You are provided with an integer array nums which is a permutation of all integers in the range [0, n - 1], where n is the length of nums. The concept of inversions in this array is split into two types: global inversions and local inversions.

  • Global inversions: These are the pairs (i, j) such that i < j and nums[i] > nums[j]. Essentially, a global inversion is any two elements that are out of order in the entire array.

  • Local inversions: These are the specific cases where nums[i] > nums[i + 1]. This means that each local inversion is a global inversion where the elements are adjacent to each other.

Your task is to determine whether the number of global inversions is exactly the same as the number of local inversions in the array. If they are equal, return true, otherwise return false.

Intuition

To solve this problem, we need to understand that all local inversions are also global inversions by definition, since adjacent out-of-order elements also count as a pair of out-of-order elements in the greater array.

However, not all global inversions are local; there can be non-adjacent elements that are out of order. For the numbers of local and global inversions to be equal, there must not be any global inversions that are not also local.

This constraint means that any element nums[i] must not be greater than nums[j] for j > i + 1. So instead of counting inversions which would take O(n^2) time, we can simply look for the presence of any such global inversion that is not local.

Given this understanding, the solution avoids a brute-force approach and cleverly checks for the condition that forbids equal global and local inversions. As we iterate through the array starting from the third element (index 2), we keep track of the maximum number we've seen up to two positions before the current index.

If at any point this maximum number is greater than the current number, mx > nums[i], then a non-local global inversion is found, and we immediately return false.

If we finish the loop without finding any non-local global inversions, then all global inversions must also be local inversions, and we return true.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Solution Approach

The Reference Solution Approach contains a thoughtfully written isIdealPermutation method which leverages the insight that in a permutation array where the number of global inversions is to be equal to the local inversions, no element can be out of order by more than one position. This is because any such displacement would constitute a global inversion that is not a local inversion, thereby invalidating our condition for equality between the two types of inversions.

Python Code Walkthrough

In the provided Python solution, we see a single for loop that starts at the third element of the array (i = 2), and at each step of the iteration, the loop does the following:

  1. Update the mx variable to hold the maximum value found so far in nums, but strictly considering elements up to two places before the current index i. This is accomplished with the expression (mx := max(mx, nums[i - 2])), which is using the walrus operator (:=) introduced in Python 3.8. This operator allows variable assignment within expressions.

  2. It then compares the maximum value mx found within the previous two elements with the current element nums[i]. If mx is found to be greater than nums[i], this indicates the presence of a non-local global inversion, and the function returns False immediately.

  3. If the loop completes without finding any such condition, it implies that there are no non-local global inversions and therefore all global inversions are indeed local. Hence, the function returns True.

This approach is efficient because it runs in O(n) time, where n is the length of nums. The use of the maximum value mx and the iteration from the third element is critical because it leverages the rule that elements cannot be out of place by more than one position for a permutation to have equal numbers of local and global inversions. This is a great example of how understanding the fundamental properties of a problem can lead to elegant and efficient solutions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's consider a small example to illustrate the solution approach using the array nums = [1, 0, 3, 2].

In this array:

  • The array has length n = 4.
  • The array is a permutation of integers [0, 1, 2, 3].

Following the solution approach:

  1. We start by initializing a variable mx which holds the maximum value up to two elements before the current index. Initially, mx does not have a value as we start checking from the third element.

  2. We now iterate through the array starting from index i = 2.

    • At i = 2, our current element is nums[2] = 3. The maximum value up to two elements before index 2 is max(nums[0], nums[1]) = max(1, 0) = 1. Since mx = 1 is not greater than nums[2] = 3, we continue to the next element.

    • At i = 3, our current element is nums[3] = 2. We update mx to the maximum value found in the window up to two indices before i = 3, which is now mx = max(mx, nums[1]) = max(1, 0) = 1. We compare mx with nums[3]. Here, mx = 1 is not greater than nums[3] = 2, so we continue.

  3. Since we did not find any case where mx > nums[i], we have confirmed that there are no global inversions that are not local. Therefore, our function isIdealPermutation will return True for this array.

This simple example confirms that for this particular permutation of nums, the number of global inversions is exactly the same as the number of local inversions, adhering to the solution approach described. The function correctly identifies this by checking if any element is displaced by more than one position from its original location, which in this case, it is not.

Solution Implementation

1from typing import List
2
3class Solution:
4    def isIdealPermutation(self, nums: List[int]) -> bool:
5        # Initialize a variable to keep track of the maximum number seen so far.
6        # Start with the first element as we will begin checking from the third element.
7        max_seen = 0
8
9        # Iterate over the array starting from the third element (index 2)
10        for i in range(2, len(nums)):
11            # Update the max_seen with the largest value among itself and
12            # the element two positions before the current one.
13            max_seen = max(max_seen, nums[i - 2])
14
15            # If the max_seen so far is greater than the current element,
16            # it is not an ideal permutation, so return False.
17            if max_seen > nums[i]:
18                return False
19
20        # If the loop completes without returning False,
21        # all local inversions are also global inversions, hence it's an ideal permutation.
22        return True
23
24# Example usage:
25# sol = Solution()
26# print(sol.isIdealPermutation([1, 0, 2])) # Should return True
27
1class Solution {
2
3    // This method checks if the number of global inversions is equal to the number of local inversions
4    // in the array, which is a condition for the array to be considered an ideal permutation.
5    public boolean isIdealPermutation(int[] nums) {
6        // Initialize the maximum value found to the left of the current position by two places.
7        // We start checking from the third element (at index 2), since we are interested in comparing
8        // it with the value at index 0 for any inversion that isn't local.
9        int maxToLeftByTwo = 0;
10
11        // Loop through the array starting from the third element.
12        // We don't need to check the first two elements because any inversion there is guaranteed to be local.
13        for (int i = 2; i < nums.length; ++i) {
14            // Update maxToLeftByTwo to the highest value found so far in nums,
15            // considering elements two positions to the left of the current index.
16            maxToLeftByTwo = Math.max(maxToLeftByTwo, nums[i - 2]);
17
18            // If the maximum value to the left (by two positions) is greater than the current element,
19            // it means there's a global inversion, and the array cannot be an ideal permutation.
20            if (maxToLeftByTwo > nums[i]) {
21                return false;
22            }
23        }
24
25        // If the loop completes without finding any global inversions other than local ones,
26        // the array is an ideal permutation.
27        return true;
28    }
29}
30
1#include <vector>
2#include <algorithm> // Include necessary headers
3
4class Solution {
5public:
6    // Check if the given permutation is an ideal permutation
7    bool isIdealPermutation(vector<int>& nums) {
8        // Initialize the maximum value found so far to the smallest possible integer
9        int maxVal = 0;
10
11        // Start iterating from the third element in the array
12        for (int i = 2; i < nums.size(); ++i) {
13            // Update the maximum value observed in the prefix of the array (till nums[i-2])
14            maxVal = max(maxVal, nums[i - 2]);
15
16            // If at any point the current maximum is greater than the current element,
17            // we don't have an ideal permutation, so return false
18            if (maxVal > nums[i]) return false;
19        }
20
21        // If the loop completes without returning false, it's an ideal permutation
22        return true;
23    }
24};
25
1// Import necessary functions from standard modules
2import { max } from 'lodash';
3
4// Check if the given permutation is an ideal permutation
5function isIdealPermutation(nums: number[]): boolean {
6    // Initialize the maximum value found so far to the first element
7    // or to the smallest possible integer if the array is empty.
8    let maxValue: number = nums.length > 0 ? nums[0] : Number.MIN_SAFE_INTEGER;
9
10    // Start iterating from the third element in the array
11    for (let i: number = 2; i < nums.length; i++) {
12        // Update the maximum value observed in the prefix of the array (up to nums[i - 2])
13        maxValue = max([maxValue, nums[i - 2]])!;
14
15        // If at any point the current maximum is greater than the current element,
16        // we don't have an ideal permutation, so return false
17        if (maxValue > nums[i]) {
18            return false;
19        }
20    }
21
22    // If the loop completes without returning false, it's an ideal permutation
23    return true;
24}
25
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because the for loop iterates from 2 to n, performing a constant amount of work for each element by updating the mx variable with the maximum value and comparing it with the current element.

Space Complexity

The space complexity of the code is O(1), which means it uses a constant amount of extra space. No additional data structures are used that grow with the input size; only the mx variable is used for keeping track of the maximum value seen so far, which does not depend on the size of nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫