775. Global and Local Inversions
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 thati < j
andnums[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.
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:
-
Update the
mx
variable to hold the maximum value found so far innums
, but strictly considering elements up to two places before the current indexi
. 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. -
It then compares the maximum value
mx
found within the previous two elements with the current elementnums[i]
. Ifmx
is found to be greater thannums[i]
, this indicates the presence of a non-local global inversion, and the function returnsFalse
immediately. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
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. -
We now iterate through the array starting from index
i = 2
.-
At
i = 2
, our current element isnums[2] = 3
. The maximum value up to two elements before index2
ismax(nums[0], nums[1]) = max(1, 0) = 1
. Sincemx = 1
is not greater thannums[2] = 3
, we continue to the next element. -
At
i = 3
, our current element isnums[3] = 2
. We updatemx
to the maximum value found in the window up to two indices beforei = 3
, which is nowmx = max(mx, nums[1]) = max(1, 0) = 1
. We comparemx
withnums[3]
. Here,mx = 1
is not greater thannums[3] = 2
, so we continue.
-
-
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 functionisIdealPermutation
will returnTrue
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
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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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